Euclidean Proof

Printable View

February 2nd 2009, 07:22 PM
wrighchr

Euclidean 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 PM
ThePerfectHacker

Quote:

Originally Posted by wrighchr

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

Any help would be great!
Thanks

I start you out. Say there is a prime $p$ dividing both $a+b$ and $ab$ . Now $p|ab$ means $p|a$ or $p|b$ . WLOG say $p|a$ . However, $p|(a+b) \implies p|b$ . And so there is a prime dividing $a\text{ and }b$ which contradicts that $(a,b)=1$ .
February 2nd 2009, 08:43 PM
Yendor

Quote:

Originally Posted by ThePerfectHacker

I start you out. Say there is a prime $p$ dividing both $a+b$ and $ab$ . Now $p|ab$ means $p|a$ or $p|b$ . WLOG say $p|a$ . However, $p|(a+b) \implies p|b$ . And so there is a prime dividing $a\text{ and }b$ which contradicts that $(a,b)=1$ .

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 PM
ThePerfectHacker

Quote:

Originally Posted by Yendor

Since d|ab and gcd(a,b)=1, then d|a or d|b

Let $d=15$ and $a=3,b=5$ .
Notice that $(a,b)=1$ and $d|ab$ but $d\not |a \text{ and }d\not |b$ .
February 2nd 2009, 09:43 PM
Yendor

Quote:

Originally Posted by ThePerfectHacker

Let $d=15$ and $a=3,b=5$ .
Notice that $(a,b)=1$ and $d|ab$ but $d\not |a \text{ and }d\not |b$ .

Your right I did it in the wrong order. My bad. Here's the correct version of that part.

Suppose $gcd(a,b)=1$ , let $d=gcd(a+b,ab).$

$d|a+b, gcd(a,b)=1 \implies d\not{|} a \ \ AND\ \ d \not{|}b\ \ OR \ \ d=1.$ Suppose $d\not{|} a \ \ AND \ \ d \not{|}b$ . Then $d\not{|}ab$ . But that's impossible, since $gcd(a+b,ab)=d.$ Thus $d=1.$