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: Some proofs involving greatest common divisors

  1. Mar 10, 2009 #1
    Hey all, I'm an absolute noob to number theory stuff and I've got this assignment to do with a few proofs.

    1. The problem statement, all variables and given/known data

    Proove that:

    i) if gcd(a,b) = c then gcd(a,a+b) = c

    ii) if gcd(a,b) = c and a = a'c and b = b'c then gcd(a',b') = 1

    iii) if there exists r,s such that rx + sy = 1 then gcd(x,y) = 1

    2. Relevant equations

    3. The attempt at a solution

    i) pretty sure this is right, I used a contradiction thing at the end:

    prove that if gcd(a,b) = c then gcd(a,a+b) = c

    c|a and c|b
    a = a'c and b = b'c
    so a+b = a'c + b'c
    = (a' + b')c
    implies c|(a+b)

    suppose there exists d: gcd(a,a+b) = d, d>=c

    we know c|a and c|(a+b)
    and d|a and d|(a+b)

    thus d|c

    d cannot be greater than c

    so d = c


    ii) this one's a bit shaky:

    prove that if gcd(a,b) = c and a = a'c and b = b'c then gcd(a',b') = 1

    now c = ra + sb (r,s integers)
    so c = r(a'c) + s(b'c)
    = ra'c + sb'c
    = (ra' + sb')c

    dividing through by c gives:

    1 = ra' + sb'

    and doesn't this imply that gcd(a',b') = 1?

    I don't think this is the right way to prove it.

    iii) No idea where to start with this. I guess I would use a method as above, but I doubt the validity of it.

    Thanks for any help!
  2. jcsd
  3. Mar 10, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    The second one is very intuitive: if there were any number d dividing both a' and b', then it would also divide a and b and therefore should be a factor in the gcd (i.e. it is already in c). Perhaps you can use this in your proof (suppose that gcd(a', b') = d, not equal to 1, then c is not the gcd).

    For iii) I suggest writing d = gcd(x, y), x = x' d, y = y' d and showing that d must be 1.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook