the entire hw
21-127, Fall 2021, Carnegie Mellon University 21-127 Problem Sheet 4 The instructions for this problem sheet are on Canvas—please read them carefully. Solutions are due on Gradescope by 9:00pm ET on Thursday 7th October 2021. Q1–5 are worth 6 points each. To receive full credit, your solutions must be mathematically correct and complete, and should be written clearly enough that another student in the course would be able to easily and fully understand your arguments. 1. Prove that R2 \ [(−∞,0)2∪ (0,∞)2] = ((−∞,0]× [0,∞))∪ ([0,∞)× (−∞,0]) 2. Prove that there exists a family of sets {Xn | n ∈ N} that (simultaneously) satisfies the three conditions (i)–(iii) that follow: (i) ⋃ n∈N Xn = Z; (ii) For all m,n ∈ N with m 6= n, there exists a ∈ Z such that Xm∩Xn = {a}; and (iii) For all n ∈ N, the set Xn is infinite. 3. Prove each of the following claims about greatest common divisors: (a) gcd(a,1) = 1 for all a ∈ Z. (b) gcd(a,0) = |a| for all a ∈ Z. (c) gcd(a,a+1) = 1 for all a ∈ Z. (d) gcd(a2 +1,a+1) = gcd(a+1,2a) for all a ∈ Z. 4. For each of the following linear Diophantine equations, determine whether there exists an integer solution (x,y) and, if there does, find one using the extended Euclidean algorithm. (a) 252x+660y = 242 (b) 252x+660y = 240 5. We say that two integers a,b ∈ Z are coprime (or relatively prime) if gcd(a,b) = 1. (a) Let a,b ∈ Z. Prove that a and b are coprime if and only if, for all c ∈ Z, the linear Diophantine equation ax+by = c has a solution (x,y) ∈ Z×Z. (b) Prove that, for all a,b ∈ Z, the integers a gcd(a,b) and b gcd(a,b) are coprime. Q6 on the next page 21-127, Fall 2021, Carnegie Mellon University Q6 is worth 2 points. The purpose of this question is to help you to engage with the course content in ways other than just writing proofs. There is no single correct answer. To receive full credit, you should provide a thorough response demonstrating that you have given the prompt serious thought. 6. A mathematician is a person who does mathematics. One way that mathematics is done is proving theorems, which means that you are officially a mathematician. Welcome to the club! Choose a mathematician to ‘meet’ from the Meet a Mathematician channel on YouTube (linked from the Canvas assignment for this problem sheet, and at the bottom of this question). Watch their video and then respond to the following questions: (a) Briefly outline one thing they said they enjoy about mathematics, and one struggle they have encountered. (b) What aspects of being a mathematician have you enjoyed so far, and what struggles have you encountered? (c) What words of wisdom did they have for future mathematicians? How do you think these words of wisdom apply to you (if at all)? Link: https://www.youtube.com/channel/UC1FKSuppol83MsVKlDoyjZQ/videos https://www.youtube.com/channel/UC1FKSuppol83MsVKlDoyjZQ/videos