Prove or give a counterexample:
For three positive integers , if then
Note: This is stronger than the condition that , since examples like prove false.
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.
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