Number Theory: Prove gcd(a,b,c) = gcd(gcd(a,b),c)

[Jamers328]

I have to prove this:

gcd(a,b,c) = gcd(gcd(a,b),c)

I think this makes perfect sense. If you take the gcd of two variables and then take that answer and the third variable, and find that gcd... it would be the same as taking the gcd of all three variables. I just need some assistance in writing the proof out...

Thanks in advance.

 

[stapel]

Chase the definitions: What is the definition of the greatest common divisor of two numbers? Of three numbers? Comparing the results, what do you find? And so forth.

Please reply showing what you've tried so far. Thank you!

Eliz.

 

[Jamers328]

Thanks for the reply.

I have tried examples, is that what you mean? The gcd(35, 20, 14)=1 regardless of the gcd between just two of them... like the gcd(35,20)=5, which is why I know the original problem makes so much sense. Cause then you can just take the gcd(5,14) and get 1.

 

[daon]

The gcd(a,b,c) is by definition the largest divisor of a, b and c. We know it exisist since the set of common divisors is finite and non-empty (since 1 is in there) and any finite subset of the positive integers has a greatest element.

Let d be the GCD(a,b,c). We get d|a, d|b, d|c and for any d' with the same property d'|d.

Now let e = GCD(a,b) and f=GCD(GCD(a,b),c)=GCD(e,c)

Try to show that d|f and that f|d. Since f and d are positive integers, it means f=d.

 

[Jamers328]

Thank you!

 

[stapel]

I have tried examples, is that what you mean?

No; by "definitions", I meant "definitions". :roll:

The post by daon demonstrates the sort of thing I'd recommended.

Eliz.