1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Gcd(a, b, c) = gcd(gcd(a,b), c)

  1. Jan 26, 2012 #1
    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.
  2. jcsd
  3. Jan 26, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    welcome to pf!

    hi ashwinb! welcome to pf! :wink:
    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? :smile:
  4. Jan 26, 2012 #3
    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)=∏ipmin(αiii). Likewise, gcd(gcd(a,b),c)=∏ipmin(min(αii),γi). These are equal since min(αiii)=min(min(αii),γi).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook