I have the integer $m \geq 2$ and the statement

$(*)$ For all integers $a$ and $b$, if $ab \equiv 0 \ (\text{mod } m)$, then $a \equiv 0 \ (\text{mod } m)$ or $b \equiv 0 \ (\text{mod } m)$

I need to show:

a) $(*)$ is true if $m$ is a prime number.

b) $(*)$ is not true when $m$ is not a prime.

All I know and understand is that if $ab \equiv 0 \ (\text{mod } m)$, then $m \ \vert \ ab - 0$, which means $ab = mk$ for some unknown integer $k$. Im aware of prime factorization and composite numbers. But I don't really know how to show this. Is there any easy way?

  • $\begingroup$ b) can simply be proved with a counter-example $\endgroup$ Commented May 18, 2016 at 14:33

1 Answer 1


For a), we can appeal to Euclid's Lemma: If $p$ is a prime and $p\mid ab$, then $p\mid a$ or $p\mid b$.

For b), suppose $m=ab$, where $1<a,b<m$. Then, $a,b\not \equiv 0\pmod{m}$ even though $ab\equiv m\equiv 0\pmod{m}$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .