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!

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




Similar Discussions: Proof using greatest common divisor.
  1. Maximum common divisor (Replies: 5)

Loading...