1. ## GCD Proof

I had two questions I can't figure out...

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

2) let gcd(a,b) = 1. prove that d= gcd(a+b, a-b) = 1 or 2
(hint: prove d<2)

Thanks!

2. Originally Posted by tips0517
I had two questions I can't figure out...

1) prove that if gcd(a,b) = 1 then gcd(a+b,a*b) = 1
Let d=gcd(a+b,a*b)

Then d divides (a+b)x+(a*b)y, where x and y can be any integers.

If you let x=a and y=-1, you get : a²+ab-ab=a². Thus d divides a²

If you let x=b and y=-1, you get : ab+b²-ab=b². Thus d divides b²

---> d=1.

2) let gcd(a,b) = 1. prove that d= gcd(a+b, a-b) = 1 or 2
(hint: prove d<2)

Thanks!
d divides (a+b) and (a-b) and thus divides (a+b)+(a-b)=2a and (a+b)-(a-b)=2b.
So d divides 2 or d divides a. If it doesn't divide 2, it divides a and b. Then...

If it divides 2, then...

3. Originally Posted by Moo
d divides … 2a …
So d divides 2 or d divides a.
That would only be true if d = 1 or a prime. It is not true for general integers d.

Originally Posted by tips0517
2) let gcd(a,b) = 1. prove that d= gcd(a+b, a-b) = 1 or 2
(hint: prove d<2)
$\gcd(a,b)=1$ $\Rightarrow$ $\exists\,r,s\in\mathbb{Z}$ with $ra+sb=1$.

Hence $r\left[(a+b)+(a-b)\right]+s\left[(a+b)-(a-b)\right]$ $=$ $2(ra+sb)$ $=$ 2.

$\therefore\ d$ divides 2 since $d$ divides the LHS.

4. Originally Posted by tips0517
I

1) prove that if gcd(a,b) = 1 then gcd(a+b,a*b) = 1
Suppose $\gcd(a+b,ab) \ne 1$, and $p$ be a prime divisor of $a+b$ and $ab$. Then as $\gcd(a,b)=1$ $p|a$ and $p \not| b$ or $p \not |a$ and $p| b$.

Without loss of generality suppose the first of these is the case. Then $p \not| (a+b)$, a contradiction so no such prime can exist and $\gcd(a+b, ab)=1$.

RonL