Results 1 to 3 of 3

Thread: Coprime Theorem

  1. #1
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Coprime Theorem

    Prove or give a counterexample:

    For three positive integers $\displaystyle u_1<u_2<u_3$, if $\displaystyle gcd(u_2,u_3)=gcd(u_1,u_3)=gcd(u_1,u_2)=1$ then $\displaystyle gcd(u_1u_2u_3,u_2u_3+u_1u_3+u_1u_2)=1$

    Note: This is stronger than the condition that $\displaystyle gcd(u_1,u_2,u_3)=1$, since examples like $\displaystyle (1,3,6)$ prove false.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Okay, I think I've got it.

    Let $\displaystyle a,b,c$ be nonzero integers
    Lemma 1: If $\displaystyle (a,b)=1$, then $\displaystyle (a,a+b)=1$
    Lemma 2: if $\displaystyle (a,b)=1$ and $\displaystyle (a,c)=1$, then $\displaystyle (a,bc)=1$

    Theorem: If $\displaystyle a<b<c$ are positive integers such that any two are coprime, then $\displaystyle gcd(abc , bc+ac+ab)=1$

    Proof:

    $\displaystyle (a,b)=1$
    By (1), $\displaystyle (a,a+b)=1$ and $\displaystyle (b,a+b)=1$
    By (2), $\displaystyle (ab,a+b)=1$
    $\displaystyle (ab,c)=1$
    By (2), $\displaystyle (ab, c(a+b))=(ab,ac+bc)=1$
    By (1), $\displaystyle (ab,ab+ac+bc)=1$
    WLOG, this means $\displaystyle (ab,ab+ac+bc)= (bc,ab+ac+bc)= (ac,ab+ac+bc)=1$
    Therefore, by (2), $\displaystyle (a^2b^2c^2,ab+ac+bc)=1$ so $\displaystyle (abc,ab+ac+bc)=1$
    Q.E.D.

    Can someone verify these two lemmas? I am not completely well versed in number theory just yet. I believe these are very easily correct, but I do not know a formal proof.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Media_Man View Post
    Let $\displaystyle a,b,c$ be nonzero integers
    Lemma 1: If $\displaystyle (a,b)=1$, then $\displaystyle (a,a+b)=1$
    Lemma 2: if $\displaystyle (a,b)=1$ and $\displaystyle (a,c)=1$, then $\displaystyle (a,bc)=1$

    Can someone verify these two lemmas?
    Yes, both lemmas are correct.

    For Lemma 1, just note that we have $\displaystyle (x,y)=(x,y-x)$ ( in fact, applying this repeatedly you can prove that given $\displaystyle y>x>0$ we have $\displaystyle (x,y)=(x,y \bmod.x)$ )

    Since $\displaystyle (x,y)$ divides x and y, it divides $\displaystyle y-x$ and so it divides $\displaystyle (x,y-x)$, thus $\displaystyle (x,y-x)\geq{(x,y)}$. $\displaystyle (x,y-x)$ divides $\displaystyle x$ and $\displaystyle y-x$, thus it divides $\displaystyle y$ also, and so it divides $\displaystyle (x,y)$ and thus $\displaystyle (x,y)\geq{(x,y-x)}$

    For Lemma 2. Suppose $\displaystyle (a, bc)>1$ then there's a prime $\displaystyle p|(a,bc)$ thus $\displaystyle p|a$ and $\displaystyle p|(bc)$ and then by Euclid's Lemma $\displaystyle p|b$ or $\displaystyle p|c$ which in any case contradicts the fact that $\displaystyle (a,b)=(a,c)=1$
    Last edited by PaulRS; Apr 23rd 2009 at 12:29 PM. Reason: Typo
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Coprime elements
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 14th 2011, 04:00 AM
  2. coprime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 13th 2009, 04:45 AM
  3. Coprime Theorem II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 7th 2009, 06:27 PM
  4. Coprime
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 19th 2009, 10:32 AM
  5. More on coprime integers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 1st 2009, 05:30 PM

Search Tags


/mathhelpforum @mathhelpforum