What is the zero-divisor problem in modular arithmetic, and why doesn't factoring work the same as with real numbers?

In modular arithmetic, $a \cdot b \equiv 0 \mod N$ does NOT mean that $a = 0$ or $b = 0$ — there can be "zero divisors," which is fundamentally different from real numbers.

For real numbers: $a \cdot b = 0 \Leftrightarrow a = 0$ or $b = 0$ (zero-product property)

For modular arithmetic: only the easy direction holds — $a = 0$ or $b = 0 \Rightarrow a \cdot b \equiv 0 \mod N$. The reverse ("$\Leftarrow$") does NOT: a product can be $\equiv 0$ even when neither factor is. Such non-zero $a, b$ with $a \cdot b \equiv 0$ are called zero divisors.

Examples:

• $5 \cdot 4 \equiv 20 \equiv 0 \mod 10$, but neither 5 nor 4 is 0
• $2 \cdot 3 \equiv 6 \equiv 0 \mod 6$, but neither 2 nor 3 is 0
• $4 \cdot 6 \equiv 24 \equiv 0 \mod 8$, but neither 4 nor 6 is 0

When does this happen? When N is composite and the factors of a and b combine to produce a multiple of N.

When is it NOT a problem? When N is prime — then $\mathbb{Z}_p$ has no zero divisors. This is one reason prime moduli are preferred in cryptography.

Go deeper:

• Zero divisor (Wikipedia) — why composite moduli break the zero-product property that primes preserve.