Converse of Euclid's Lemma does not Hold

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$