Prove: There are zero divisors in $\Bbb Z_n$ if and only if $n$ is not prime.

Question

I need to prove there are zero divisors in $\mathbb{Z}_n$ if and only if $n$ is not prime. What should I consider first?

Answer 1

Hint: If $n$ is not prime, then either $n=1$ (in which case this is trivial) or there are some integers $k,m\in\{2,...,n-1\}$ such that $n=km$ (as you've correctly deduced). What can we conclude from there about certain elements of $\Bbb Z_n$?

If $n$ is prime, and $[km]=[k][m]=[0]$ for some $[k],[m]\in\Bbb Z_n,$ then $n\mid km,$ and so...what?

Answer 2

Here's a slightly different way to go about this: to prove that $\mathbb Z_n$ has zero divisors if and only if $n$ is not prime, is the same as showing that $\mathbb Z_n$ has no zero divisors if and only if $n$ is prime. Here, $\mathbb Z_n = \{0,1,2,...,n-1\}$.

1. Suppose $\mathbb Z_n$ has no zero divisors. Then, if $a,b\in\mathbb Z_n$, $a\ne 0$, $b\ne 0$, we must have $ab\ne 0$. Suppose $n$ is not prime. Then, $n = pq$ for some integers $p,q$ such that $p < n$ and $q < n$ where $p,q\ne 0$. However, $pq \equiv 0 \bmod n$. This is a contradiction, so $n$ must be prime.

2. Suppose $n$ is prime. Suppose there exist $a,b\in\mathbb Z_n$ such that $ab = 0$ (same as saying $ab \equiv 0 \bmod n$) where $a\ne 0$ and $b\ne 0$. So, $n | ab$. Since $n$ is prime, $n|ab \implies n|a$ or $n|b$. None of these can happen, since $a < n$ and $b < n$. So, $\mathbb Z_n$ has no zero divisors.

Done!