Prove that (a , b) = 1 if and only if (a + b , ab) = 1.

Any help would be great!

Thanks

Printable View

- February 2nd 2009, 07:22 PMwrighchrEuclidean Proof
Prove that (a , b) = 1 if and only if (a + b , ab) = 1.

Any help would be great!

Thanks - February 2nd 2009, 07:43 PMThePerfectHacker
- February 2nd 2009, 08:43 PMYendor
Or if you don't want to use primes and the FTA at all...

Suppose gcd(a,b)=1, let d=gcd(a+b,ab). Since d|ab and gcd(a,b)=1, then d|a or d|b (but not both, unless d=1). Assume (WOLG) d|a. Now since d|a and d|a+b then d|b. But gcd(a,b)=1, so d=1.

Conversely, suppose gcd(a+b,ab)=1. Then there exists x,y such that (a+b)x+aby=1=ax+bx+aby=ax+b(x+ay)=ax+by'. Since there exists x,y' such that ax+by'=1, then gcd(a,b)|1. But this means gcd(a,b)=1. - February 2nd 2009, 09:19 PMThePerfectHacker
- February 2nd 2009, 09:43 PMYendor