Results 1 to 3 of 3

Math Help - 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 u_1<u_2<u_3, if gcd(u_2,u_3)=gcd(u_1,u_3)=gcd(u_1,u_2)=1 then gcd(u_1u_2u_3,u_2u_3+u_1u_3+u_1u_2)=1

    Note: This is stronger than the condition that gcd(u_1,u_2,u_3)=1, since examples like (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 a,b,c be nonzero integers
    Lemma 1: If (a,b)=1, then (a,a+b)=1
    Lemma 2: if (a,b)=1 and (a,c)=1, then (a,bc)=1

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

    Proof:

    (a,b)=1
    By (1), (a,a+b)=1 and (b,a+b)=1
    By (2), (ab,a+b)=1
    (ab,c)=1
    By (2), (ab, c(a+b))=(ab,ac+bc)=1
    By (1), (ab,ab+ac+bc)=1
    WLOG, this means (ab,ab+ac+bc)= (bc,ab+ac+bc)= (ac,ab+ac+bc)=1
    Therefore, by (2), (a^2b^2c^2,ab+ac+bc)=1 so (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 a,b,c be nonzero integers
    Lemma 1: If (a,b)=1, then (a,a+b)=1
    Lemma 2: if (a,b)=1 and (a,c)=1, then (a,bc)=1

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

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

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

    For Lemma 2. Suppose (a, bc)>1 then there's a prime p|(a,bc) thus p|a and p|(bc) and then by Euclid's Lemma p|b or p|c which in any case contradicts the fact that (a,b)=(a,c)=1
    Last edited by PaulRS; April 23rd 2009 at 01: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: January 14th 2011, 05:00 AM
  2. coprime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 13th 2009, 05:45 AM
  3. Coprime Theorem II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 7th 2009, 07:27 PM
  4. Coprime
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 11:32 AM
  5. More on coprime integers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2009, 06:30 PM

Search Tags


/mathhelpforum @mathhelpforum