Coprime Theorem

Printable View

April 23rd 2009, 02:37 AM
Media_Man

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.
April 23rd 2009, 06:33 AM
Media_Man

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.
April 23rd 2009, 08:39 AM
PaulRS

Quote:

Originally Posted by Media_Man

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$