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)
$\displaystyle \gcd(a,b)=1$ $\displaystyle \Rightarrow$ $\displaystyle \exists\,r,s\in\mathbb{Z}$ with $\displaystyle ra+sb=1$.

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

$\displaystyle \therefore\ d$ divides 2 since $\displaystyle 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 $\displaystyle \gcd(a+b,ab) \ne 1$, and $\displaystyle p$ be a prime divisor of $\displaystyle a+b$ and $\displaystyle ab$. Then as $\displaystyle \gcd(a,b)=1$ $\displaystyle p|a$ and $\displaystyle p \not| b$ or $\displaystyle p \not |a$ and $\displaystyle p| b$.

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

RonL