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: Number Theory. If d=gcd(a,b,c) then d is a linear combination of a,b, and c

  1. Sep 5, 2012 #1
    1. The problem statement, all variables and given/known data
    Several of us claimed that if d=gcd(a,b,c) then d is a linear combination of a,b and c, i.e. that d=sa+tb+uc for some integers s,t, and u. That is true, but we only proved the analogous claim for the greatest common divisor of two numbers, i.e. when d=gcd(a,b). We need three.

    2. Relevant equations

    3. The attempt at a solution
    I know that gcd(a,b,c)=gcd(gcd(a,b)c). Can I use this to prove? If so, I'm not sure how.
  2. jcsd
  3. Sep 5, 2012 #2


    User Avatar
    Science Advisor

    Sure. If you know that gcd(x, y)= px+ qy, then gcd(gcd(a,b), c)= p(gcd(a,b))+ qc.
    And gcd(a, b)= sa+ tb so gcd(gcd(a,b), c)= p(sa+ tb)+ qc= (ps)a+ (pt)b+ qc and ps, pt, and q are integers.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook