# Congruence relationships.

I need to prove (or disprove but I don't think that's the case) that:

if $ab \equiv 0$ (mod $n$), then $a\equiv 0$ (mod $n$) or $b\equiv0$ (mod $n$)

I know that $ab\equiv 0$ (mod $n$) $\Longleftrightarrow n|ab$, so if that's true then n must divide either a or b but I don't know how to prove it.

Any assistance is much appreciated.

-
What about $a=2$, $b=3$, $n=6$? –  Hagen von Eitzen Feb 10 '13 at 17:50

Your claim holds if and only if $n$ is prime. Otherwise, $n=ab$ for some $a,b$ with $n\not\mid a$ and $n\not\mid b$, so $a,b\not\equiv 0$, but $ab=n\equiv 0$.

-

Its not true (except for $n$ prime)take the the case $4|2\times 6$ but 4 does not divide 6 or 2.

I think this disproves the fact.

-