Zero Divisors in Z/nZ

# Zero Divisors in Z/nZ

Recall from the Zero Divisors in Rings page that if $(R, +, *)$ is a ring and the identity for $+$ is $0$ then an element $a \in R \setminus \{ 0 \}$ is called a zero divisor of $R$ if there exists an element $b \in R \setminus \{ 0 \}$ such that $a * b = 0$ or $b * a = 0$.

Also recall from The Ring of Z/nZ page that for $n \in \{2, 3, ... \}$ we define the set $\mathbb{Z} / n\mathbb{Z}$ to be the set of sets:

(1)
\begin{align} \quad \mathbb{Z} / n \mathbb{Z} = \{ _n, _n, ..., [n-1]_n \} \end{align}

For each $k \in \{ 0, 1, 2, ..., n-1 \}$ we define:

(2)
\begin{align} \quad [k]_n = \{ z \in \mathbb{Z} : z \equiv k \pmod n \} \end{align}

We will now look at a rather interesting theorem which states that if $n$ is not prime then $\mathbb{Z} / n \mathbb{Z}$ contains a zero divisor.

 Theorem 1: If $n > 2$ is a composite number then the ring $(\mathbb{Z} / n\mathbb{Z}, +, *)$ where for $k, j \in \{0, 1, 2, ... \}$ we define the operation $+$ by $[k]_n + [j]_n = [k + j]_n$ and we define the operation $*$ by $[k]_n * [j]_n = [k \cdot j]_n$ has a zero divisor.
• Proof: Suppose that $n > 2$ and that $n$ is a composite number. Then $n$ has a nonnegative divisor $d$ such that $1 < d < n$. There are two cases to consider.
• Case 1: Suppose that $d$ is the only divisor of $n$ such that $d \neq 1$ and $d \neq n$. Then we must have that $d^2 = n$. Therefore for $[d]_n \neq _n$ we have that:
(3)
\begin{align} \quad [d]_n * [d]_n = [d \cdot d]_n = [d^2]_n = [n]_n = _n \end{align}
• Therefore $[d]_n$ is a zero divisor of $\mathbb{Z} / n\mathbb{Z}$.
• Case 2: Suppose that $d$ is not the only divisor of $n$ such that $d \neq 1$ and $d \neq n$. Then there must exist another divisor $k$ such that $k \neq 1$ and $k \neq n$ where $d \cdot k = n$. Therefore for $[d]_n, [k]_n \neq _n$ we have that:
(4)
\begin{align} \quad [d]_n * [k]_n = [d * k ]_n = [n]_n = _n \end{align}
• Therefore $[d]_n$ and $[k]_n$ are zero divisors of $\mathbb{Z} / n\mathbb{Z}$.
• Thus, if $n > 2$ is composite then $\mathbb{Z} / n\mathbb{Z}$ has a zero divisor. $\blacksquare$