# Congruent modulo and primes

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?

• b) can simply be proved with a counter-example – ghosts_in_the_code May 18 '16 at 14:33

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}$.