Converse of Euclid's Lemma does not Hold
Jump to navigation
Jump to search
Lemma
Let $n \in Z_{>0}$ be a positive composite number
Let $a b \equiv 0 \pmod n$.
Then it is not necessarily the case that either $a \equiv 0 \pmod n$ or $b \equiv 0 \pmod n$.
Proof
Let $n = 6$.
We have that:
- $6 \equiv 0 \pmod 6$
but:
- $2 \equiv 2 \pmod 6$
- $3 \equiv 3 \pmod 6$
Hence the result by Proof by Counterexample.
$\blacksquare$
Sources
- 1965: J.A. Green: Sets and Groups ... (previous) ... (next): Chapter $2$. Equivalence Relations: Exercise $7$