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: GCD relative prime question

  1. Feb 19, 2015 #1
    1. The problem statement, all variables and given/known data
    Let a and b be relatively prime. Show that gcd(a+b,ab) = 1

    2. Relevant equations
    ax+by = 1 for some integers x and y

    3. The attempt at a solution
    I set gcd(a+b,ab) = d. I'm now trying to show that d = 1 using elementary algebra techniques.
    a+b = rd
    ab = sd
    ax + by = 1

    I'm kind of stuck here.. am I on the right track? Do I just need to aggresively rearrange stuff until I can express (a+b) and (ab) as a linear combination that equals one? or perhaps arrange them in such away that I show d divides both a and b individually and therefore it must be one since they are relatively prime? any hints?


    a+b = rd ---> b = rd -a

    ab = a(rd-a) = (ard)-(a^2) = sd
    dividing both sides by d...

    ar - (a^2 / d) = s
    ar is an integer and s is an integer, so a^2 / d must be an integer, therefore d|a^2.

    I employed a similar argument to show that d|b^2. Since d|a^2 and d|b^2 and gcd(a,b) = 1, we can use the fact that gcd(a^2,b^2) = 1 to conclude that d = 1.

    Is this a solid argument?
    Last edited: Feb 19, 2015
  2. jcsd
  3. Feb 20, 2015 #2


    User Avatar
    Gold Member

    Your argument looks perfectly sound to me. You can make it a little more elegant by going : ## ard-a^2=rd \implies a^2=(ar-r)d \implies d|a^2 ## , but it's really the same thing.
    Note however that this is not the method suggested in the formulation of the problem : you didn't make use of ## ax+by=1 ##. If you want to try that as well, do you know where that equation comes from ?
    Last edited: Feb 20, 2015
  4. Feb 20, 2015 #3
    Oh wow, didn't even notice that I didn't use the relatively prime information, haha. Yeah, I know about the equation. Thanks for the post yo!
  5. Feb 20, 2015 #4


    User Avatar
    Gold Member

    No problem. I can see you don't like going by the book, you tackle the problem your own way, which is cool : )
  6. Feb 20, 2015 #5
    Thanks ^_^ I appreciate it. I'm pretty new to this math thing but I want to learn it's mysteries so I appreciate the complement :D
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted