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: Proof using greatest common divisor.

  1. Dec 13, 2012 #1
    1. The problem statement, all variables and given/known data
    The problem went "If c|a and c|b then c|gcd(a,b) where cεN and a,bεZ"


    2. Relevant equations



    3. The attempt at a solution
    My proof went like this " Let a=cr and b=cs where r,sεZ. We want to show c|gcd(a,b). Lets
    start with cd=ax+by where d,x,yεZ since the gcd(a,b) can be rewritten as a linear combination.
    Substituting a and b we get cd=(cr)ax+(cs)ay <=> cd=c(rax+say) where rax+sayεZ. Hence
    c|gcd(a,b).

    is this right?
     
  2. jcsd
  3. Dec 13, 2012 #2

    Zondrina

    User Avatar
    Homework Helper

    Notice where I've bolded. You jumped out too far there. You're right to say that :

    It's also good that you realize the gcd is a linear combination, but that does not automatically imply what you've stated here.

    What you should say is suppose gcd(a,b) = d for some integer d. Then it follows that gcd(a,b) = d = ax + by for some integers x and y.

    Now using d = ax + by the rest of your proof will follow smoothly.
     
  4. Dec 13, 2012 #3

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper

    c is a common divisor of a and b so in particular it is equal to the gcd. This part is trivial. Assume now that c is a common divisor smaller (in modulus) than gcd. You need to show that there's x integer so that gcd = x c.

    Assume a = c alpha, b = c beta. What happens if (alpha,beta) =1, i.e. gcd(alpha,beta)=1 ? Who's c ?
     
  5. Dec 13, 2012 #4
    I agree the first part of my proof makes a leap but not a very big leap. So my proof should read like this " Let a=cr and b=cs where r,sεZ. We want to show c|gcd(a,b). Suppose gcd(a,b) = d for some integer d. Then it follows that gcd(a,b) = d = ax + by for some integers x and y. Thus ct=d for some tεZ which becomes ct=ax+by. Substituting a and b we get ct=(cr)ax+(cs)ay <=> ct=c(rax+say) where rax+sayεZ. Hence c|gcd(a,b).

    It makes the proof look cleaner but doesn't change much. I used the fact that gcd(a,b) by definition can be written as a linear combination of some multiples of integers a and b.
     
    Last edited: Dec 13, 2012
  6. Dec 13, 2012 #5

    Zondrina

    User Avatar
    Homework Helper

    Er what I was thinking was if :
    a=cr and b=cs

    d = ax + by
    d = crx + csy
    d = c(rx + sy)

    And hence c divides d. Making the substitution for d is redundant.
     
  7. Dec 13, 2012 #6
    oh I realize I made an error in my original proof. "Let a=cr and b=cs where r,sεZ. We want to show c|gcd(a,b). Suppose gcd(a,b) = d for some integer d. Then it follows that gcd(a,b) = d = ax + by for some integers x and y. Thus ct=d for some tεZ which becomes ct=ax+by. Substituting a and b we get ct=(cr)x+(cs)y <=> ct=c(rx+sy) (right here where I left a)where rx+syεZ. Hence c|gcd(a,b).

    Yeah its redundant. I wouldn't say its a bad thing as it can be fixed. But I just wanted to verify that the idea's in this proof are on the right track. Ill clean this proof up.
     
    Last edited: Dec 13, 2012
  8. Dec 13, 2012 #7

    Zondrina

    User Avatar
    Homework Helper

    Yes it's the right idea for sure. Just saying why do more work than you have to right ;)?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook