Prove or give a counterexample:

For three positive integers , if then

Note: This is stronger than the condition that , since examples like prove false.

Printable View

- Apr 23rd 2009, 03:37 AMMedia_ManCoprime Theorem
Prove or give a counterexample:

For three positive integers , if then

Note: This is stronger than the condition that , since examples like prove false. - Apr 23rd 2009, 07:33 AMMedia_ManOkay, I think I've got it.
Let be nonzero integers

Lemma 1: If , then

Lemma 2: if and , then

Theorem: If are positive integers such that any two are coprime, then

Proof:

By (1), and

By (2),

By (2),

By (1),

WLOG, this means

Therefore, by (2), so

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, 09:39 AMPaulRS
Yes, both lemmas are correct.

For Lemma 1, just note that we have ( in fact, applying this repeatedly you can prove that given we have )

Since divides x and y, it divides and so it divides , thus . divides and , thus it divides also, and so it divides and thus

For Lemma 2. Suppose then there's a prime thus and and then by Euclid's Lemma or which in any case contradicts the fact that