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

[ashwinb]

Help please!
I basically have to prove that gcd(a, b, c) = gcd(gcd(a,b), c).
So I know that if I just need to prove that the sets {a, b, c} and {gcd(a,b), c} have the same sets of divisors.

 

[tiny-tim]

welcome to pf!

hi ashwinb! welcome to pf!

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

you usually do this sort of thing by proving separately:
i] gcd(a, b, c) ≤ gcd(gcd(a,b), c)
ii] gcd(a, b, c) ≥ gcd(gcd(a,b), c)

how far have you got? ​

 

[A. Bahat]

A straightforward way of proving this is to use the prime factorizations of a, b, and c, that is, write a=∏_ip^α_i, b=∏_ip^β_i, and c=∏_ip^γ_i. Then gcd(a,b,c)=∏_ip^{min(α_i,β_i,γ_i)}. Likewise, gcd(gcd(a,b),c)=∏_ip^{min(min(α_i,β_i),γ_i)}. These are equal since min(α_i,β_i,γ_i)=min(min(α_i,β_i),γ_i).