Thread: simple gcd proofs

(a) prove that gcd(a,b,c) = gcd(a,gcd(b,c))
(b) a,b,c N, with gcd(a,b) = gcd(a,c) = gcd(b,c). prove that gcd(a,b,c) = 1
(c) find a,b,c N with gcd(a,b,c) = 1 but gcd(a,b), gcd(a,c), gcd(b,c) all > 1

i thought i would put them all in the same thread seeing as they may relate to each other

Originally Posted by wik_chick88

(a) prove that gcd(a,b,c) = gcd(a,gcd(b,c))
(b) a,b,c N, with gcd(a,b) = gcd(a,c) = gcd(b,c). prove that gcd(a,b,c) = 1
(c) find a,b,c N with gcd(a,b,c) = 1 but gcd(a,b), gcd(a,c), gcd(b,c) all > 1

i thought i would put them all in the same thread seeing as they may relate to each other

show some working for part (a).

a) Let x = GCD(a,b,c). Let y = GCD(a, GCD(b,c)). Then, by definition of GCD, y divides a.

Also, y divides GCD(b,c). Therefore y divides b and y divides c.

Thus, y divides a, b, and c. This implies that y divides GCD(a,b,c) = x since any common divisor divides the GCD.

On the other hand, x divides a, b, and c. In particular, since x divides b and c, x divides GCD(b,c). Thus, since x divides a and x divides GCD(b,c), it follows that x divides GCD(a, GCD(b,c)) = y.

We have shown y divides x and we have also shown x divides y. Thus, x = y. IOW, GCD(a,b,c) = GCD(a, GCD(b,c)).

b) This claim is actually false. Counterexample: Let a = 10, let b = 15, let c = 25.
Then GCD(10,15) = 5, GCD(15,25) = 5, GCD(25,10) = 5, and GCD(10,15,25) = 5.

So, you might have transcribed the problem statement incorrectly. Otherwise, it's a typo in the source textbook or whatever.

c) Let a = 6, b = 15, c = 10.

Then GCD(6,15,10) = 1, yet GCD(6,15) = 3, GCD(15,10) = 5, GCD(10,6) = 2.


More generally, we can find such numbers by first selecting 3 distinct prime numbers p1, p2, and p3. The next step would be to let a = p1*p2, b = p2*p3, and c = p3*p1.

Originally Posted by Solvoid

b) This claim is actually false. Counterexample: Let a = 10, let b = 15, let c = 25.
Then GCD(10,15) = 5, GCD(15,25) = 5, GCD(25,10) = 5, and GCD(10,15,25) = 5.

So, you might have transcribed the problem statement incorrectly. Otherwise, it's a typo in the source textbook or whatever.

i did type it down properly sorry! i meant that gcd(a,b)=gcd(a,c)=gcd(b,c)=1
prove that gcd(a,b,c)=1
is there a quicker way to do this than proof by contradiction?

Originally Posted by wik_chick88

i did type it down properly sorry! i meant that gcd(a,b)=gcd(a,c)=gcd(b,c)=1
prove that gcd(a,b,c)=1
is there a quicker way to do this than proof by contradiction?

Yes, there definitely is!

By part (a), GCD(a,b,c) = GCD(a, GCD(b,c)) = GCD(a, 1) = 1.