# Coprime Theorem

• Apr 23rd 2009, 02:37 AM
Media_Man
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.
• Apr 23rd 2009, 06:33 AM
Media_Man
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.
• Apr 23rd 2009, 08:39 AM
PaulRS
Quote:

Originally Posted by Media_Man
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\$