For any integers $a$ and $b$, $ab = 0$ implies $a = 0$ or $b = 0$. Prove that this remains true mod prime numbers but not true mod a composite number.

Question

I roughly understand modular arithmetic but I am having trouble starting the problem. I can prove it for just integers but I can't seem to relate it to mod primes and composites?

By definition, a composite number $q$ is the product of two smaller integers. What is that product modulo $q$? — eyeballfrog, Sep 27 '19 at 07:15

score 1 · Answer 1 · answered Sep 27 '19 at 07:20

Here are two strategies that will work:

Start with a single example. Is the statement true in the integers modulo $6$? Why not, exactly? How does your argument generalize to other composite numbers?
Start by writing out definitions. What does it mean for a modulus $n$ to be a composite number? What does it mean for an integer to be congruent to $0$ modulo $n$? Can you find a way to plug these definitions into the problem you're trying to solve?

score 0 · Answer 2 · answered Sep 27 '19 at 08:25

Well, in the residue class ring ${\Bbb Z}_m$, $m\geq 2$, each element $a\ne 0$ is either a unit or a zero divisor. An element $a\ne 0$ is a unit if $\gcd(a,m)=1$, otherwise a zero divisor.

The implication $ab=0\rightarrow a=0\vee b=0$ holds iff $a$ or $b$ is not a zero divisor.

For any integers $a$ and $b$, $ab = 0$ implies $a = 0$ or $b = 0$. Prove that this remains true mod prime numbers but not true mod a composite number.

2 Answers2