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 co
ect
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 linea
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
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 co
ect 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