# Suppose $ab\equiv 0 \pmod{n}$, and that $a$ and $b$ are positive integers both less than $n$. Does it follow that either $a | n$ or $b | n$?

Suppose $ab\equiv 0 \pmod{n}$, and that $a$ and $b$ are positive integers both less than $n$. Does it follow that either $a | n$ or $b | n$? If it does follow, give a proof. If it doesn’t, then give an example.

I can't possibly think of an example for this, but unsure about any possible proof otherwise.

• ab\equiv 0 \pmod{n} . Formatting tips here. – Em. Jul 3 '16 at 3:22
• Hint: consider $n = 4$. – Ben E Jul 3 '16 at 3:22
• Could you elaborate? I feel like I'm making a mistake, but don't know what. – Crazed Jul 3 '16 at 3:24
• But $a$ and $b$ are positive integers less than $n$? – Crazed Jul 3 '16 at 3:33

A counterexample would be $a=6$, $b=6$, and $n=9$.
Now $0<a,b< n$ and $ab=36=4\cdot 9\equiv 0\pmod 9$, but $a\nmid n$ and $b\nmid n$.
No. $a=12, b=20, n=30...$ Or $a=p^2 q,\; b=p^2r, \;n=pqr$ with $p,q,r$ primes with $p<q<r.$