# GCD relative prime question

1. Feb 19, 2015

### PsychonautQQ

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?

Update:

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. Feb 20, 2015

### wabbit

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
3. Feb 20, 2015

### PsychonautQQ

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!

4. Feb 20, 2015

### wabbit

No problem. I can see you don't like going by the book, you tackle the problem your own way, which is cool : )

5. Feb 20, 2015

### PsychonautQQ

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