Results 1 to 5 of 5

Thread: 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
    10
    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 $\displaystyle p$ dividing both $\displaystyle a+b$ and $\displaystyle ab$. Now $\displaystyle p|ab$ means $\displaystyle p|a$ or $\displaystyle p|b$. WLOG say $\displaystyle p|a$. However, $\displaystyle p|(a+b) \implies p|b$. And so there is a prime dividing $\displaystyle a\text{ and }b$ which contradicts that $\displaystyle (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 $\displaystyle p$ dividing both $\displaystyle a+b$ and $\displaystyle ab$. Now $\displaystyle p|ab$ means $\displaystyle p|a$ or $\displaystyle p|b$. WLOG say $\displaystyle p|a$. However, $\displaystyle p|(a+b) \implies p|b$. And so there is a prime dividing $\displaystyle a\text{ and }b$ which contradicts that $\displaystyle (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
    10
    Quote Originally Posted by Yendor View Post
    Since d|ab and gcd(a,b)=1, then d|a or d|b
    Let $\displaystyle d=15$ and $\displaystyle a=3,b=5$.
    Notice that $\displaystyle (a,b)=1$ and $\displaystyle d|ab$ but $\displaystyle 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 $\displaystyle d=15$ and $\displaystyle a=3,b=5$.
    Notice that $\displaystyle (a,b)=1$ and $\displaystyle d|ab$ but $\displaystyle 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 $\displaystyle gcd(a,b)=1$, let $\displaystyle d=gcd(a+b,ab).$

    $\displaystyle d|a+b, gcd(a,b)=1 \implies d\not{|} a \ \ AND\ \ d \not{|}b\ \ OR \ \ d=1.$ Suppose $\displaystyle d\not{|} a \ \ AND \ \ d \not{|}b$. Then $\displaystyle d\not{|}ab$. But that's impossible, since $\displaystyle gcd(a+b,ab)=d.$ Thus $\displaystyle 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: Oct 11th 2010, 04:16 AM
  2. Euclidean algorithm proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Nov 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: Nov 7th 2007, 04:17 PM
  5. non-Euclidean -help on proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jul 15th 2006, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum