- #1
Math100
- 770
- 219
- Homework Statement
- Assuming that gcd(a, b)=1, prove the following:
(a) gcd(a+b, a-b)=1 or 2.
[Hint: Let d=gcd(a+b, a-b) and show that d##\mid## 2a, d##\mid##2b, and thus that d##\leq##gcd(2a, 2b)=2 gcd(a, b).]
(b) gcd(2a+b, a+2b)=1 or 3.
(c) gcd(a+b, a^{2}+b^{2})=1 or 2.
[Hint: a^{2}+b^{2}=(a+b)(a-b)+2b^{2}.]
(d) gcd(a+b, a^{2}-ab+b^{2})=1 or 3.
[Hint: a^{2}-ab+b^{2}=(a+b)^{2}-3ab.]
- Relevant Equations
- None.
Proof: (a) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a-b).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a-b).
This means d##\mid##[(a+b)+(a-b)] and d##\mid##[(a+b)-(a-b)],
so we have d##\mid##2a and d##\mid##2b.
Note that d##\leq##gcd(2a, 2b)=2 gcd(a, b).
Since gcd(a, b)=1, it follows that 2 gcd(a, b)=2(1)=2.
Thus, d##\mid##2, which implies that d=1 or d=2.
Therefore, gcd(a+b, a-b)=1 or 2.
(b) Suppose that gcd(a, b)=1.
Let d=gcd(2a+b, a+2b).
By definition of the greatest common divisor,
we have that d##\mid##(2a+b) and d##\mid##(a+2b).
This means d##\mid##[2(2a+b)-(a+2b)] and d##\mid##[-(2a+b)+2(a+2b)],
so we have d##\mid##3a and d##\mid##3b.
Note that d##\leq##gcd(3a, 3b)=3 gcd(a, b).
Since gcd(a, b)=1, it follows that 3 gcd(a, b)=3(1)=3.
Thus, d##\mid##3, which implies that d=1 or d=3.
Therefore, gcd(2a+b, a+2b)=1 or 3.
(c) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}+b^{2}).
This means d##\mid##[(a^{2}+b^{2})+(a^{2}-b^{2})] and d##\mid##[(a^{2}+b^{2})-(a^{2}-b^{2})],
so we have d##\mid##2a^{2} and d##\mid##2b^{2}.
Note that d##\leq##gcd(2a^{2}, 2b^{2})=2 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 2 gcd(a^{2}, b^{2})=2(1)=2, and so d##\mid##2,
which implies that d=1 or d=2.
Therefore, gcd(a+b, a^{2}+b^{2})=1 or 2.
(d) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}-ab+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}-ab+b^{2}).
This means d##\mid##[(a+b)^{2}-(a^{2}-ab+b^{2})], so we have d##\mid##3ab.
Note that each prime divisor k of d must divide either 3, a or b.
Thus, we have that d##\mid##[3a(a+b)-3ab] and d##\mid##[3b(a+b)-3ab],
so d##\mid##3a^{2} and d##\mid##3b^{2}.
Then we get d##\leq##gcd(3a^{2}, 3b^{2})=3 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 3 gcd(a^{2}, b^{2})=3(1)=3, and so d##\mid##3,
which implies that d=1 or d=3.
Therefore, gcd(a+b, a^{2}-ab+b^{2})=1 or 3.
Let d=gcd(a+b, a-b).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a-b).
This means d##\mid##[(a+b)+(a-b)] and d##\mid##[(a+b)-(a-b)],
so we have d##\mid##2a and d##\mid##2b.
Note that d##\leq##gcd(2a, 2b)=2 gcd(a, b).
Since gcd(a, b)=1, it follows that 2 gcd(a, b)=2(1)=2.
Thus, d##\mid##2, which implies that d=1 or d=2.
Therefore, gcd(a+b, a-b)=1 or 2.
(b) Suppose that gcd(a, b)=1.
Let d=gcd(2a+b, a+2b).
By definition of the greatest common divisor,
we have that d##\mid##(2a+b) and d##\mid##(a+2b).
This means d##\mid##[2(2a+b)-(a+2b)] and d##\mid##[-(2a+b)+2(a+2b)],
so we have d##\mid##3a and d##\mid##3b.
Note that d##\leq##gcd(3a, 3b)=3 gcd(a, b).
Since gcd(a, b)=1, it follows that 3 gcd(a, b)=3(1)=3.
Thus, d##\mid##3, which implies that d=1 or d=3.
Therefore, gcd(2a+b, a+2b)=1 or 3.
(c) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}+b^{2}).
This means d##\mid##[(a^{2}+b^{2})+(a^{2}-b^{2})] and d##\mid##[(a^{2}+b^{2})-(a^{2}-b^{2})],
so we have d##\mid##2a^{2} and d##\mid##2b^{2}.
Note that d##\leq##gcd(2a^{2}, 2b^{2})=2 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 2 gcd(a^{2}, b^{2})=2(1)=2, and so d##\mid##2,
which implies that d=1 or d=2.
Therefore, gcd(a+b, a^{2}+b^{2})=1 or 2.
(d) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}-ab+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}-ab+b^{2}).
This means d##\mid##[(a+b)^{2}-(a^{2}-ab+b^{2})], so we have d##\mid##3ab.
Note that each prime divisor k of d must divide either 3, a or b.
Thus, we have that d##\mid##[3a(a+b)-3ab] and d##\mid##[3b(a+b)-3ab],
so d##\mid##3a^{2} and d##\mid##3b^{2}.
Then we get d##\leq##gcd(3a^{2}, 3b^{2})=3 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 3 gcd(a^{2}, b^{2})=3(1)=3, and so d##\mid##3,
which implies that d=1 or d=3.
Therefore, gcd(a+b, a^{2}-ab+b^{2})=1 or 3.