- #1

Math100

- 756

- 204

- 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.