1. Not finding help here? Sign up for a free 30min 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!

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

    tiny-tim

    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook