Results 1 to 5 of 5

Math Help - Euclidean Proof

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    2

    Euclidean Proof

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

    Any help would be great!
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by wrighchr View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2009
    Posts
    4
    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Yendor View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2009
    Posts
    4
    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 11th 2010, 04:16 AM
  2. Euclidean algorithm proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 28th 2009, 07:03 PM
  3. non-Euclidean Geometry Proof
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 2nd 2008, 03:20 PM
  4. Fibonacci/Euclidean Algorithmn proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 7th 2007, 04:17 PM
  5. non-Euclidean -help on proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 15th 2006, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum