[proofplan] We prove both directions by translating zero divisors in $\mathbb{Z}/n\mathbb{Z}$ into divisibility statements in $\mathbb{Z}$. If $n$ is prime, Euclid's lemma forces any product congruent to $0$ modulo $n$ to have one factor congruent to $0$ modulo $n$. Conversely, if $n$ is not prime, a nontrivial factorization $n = ab$ produces two nonzero residue classes whose product is zero. [/proofplan] [step:Fix the quotient notation and verify the ambient ring conditions] Let \begin{align*} \pi_n: \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}, \quad a \mapsto [a]_n \end{align*} denote the quotient map, where $[a]_n$ is the residue class of $a \in \mathbb{Z}$ modulo $n$. Multiplication in $\mathbb{Z}/n\mathbb{Z}$ is given by \begin{align*} [a]_n[b]_n = [ab]_n \end{align*} for all $a,b \in \mathbb{Z}$. Since $\mathbb{Z}$ is a commutative ring with identity, the quotient $\mathbb{Z}/n\mathbb{Z}$ is a commutative ring with identity $[1]_n$. Because $n \ge 2$, the classes $[0]_n$ and $[1]_n$ are distinct, so $\mathbb{Z}/n\mathbb{Z}$ is not the zero ring. [/step] [step:Use Euclid's lemma to rule out zero divisors when $n$ is prime] Assume that $n$ is prime. Let $a,b \in \mathbb{Z}$ satisfy \begin{align*} [a]_n[b]_n = [0]_n. \end{align*} By the multiplication rule in the [quotient ring](/page/Quotient%20Ring), this means $[ab]_n = [0]_n$, equivalently $n \mid ab$. By Euclid's lemma for primes (citing a result not yet in the wiki: Euclid's lemma / prime divides a product), since $n$ is prime and $n \mid ab$, we have $n \mid a$ or $n \mid b$. Therefore $[a]_n = [0]_n$ or $[b]_n = [0]_n$. Thus $\mathbb{Z}/n\mathbb{Z}$ has no nonzero zero divisors. Together with the previous step, $\mathbb{Z}/n\mathbb{Z}$ is an [integral domain](/page/Integral%20Domain). [guided] Assume that $n$ is prime. To prove that $\mathbb{Z}/n\mathbb{Z}$ is an integral domain, the only remaining point after the first step is to prove that it has no nonzero zero divisors. So take arbitrary elements $[a]_n,[b]_n \in \mathbb{Z}/n\mathbb{Z}$ and suppose their product is zero: \begin{align*} [a]_n[b]_n = [0]_n. \end{align*} The multiplication rule in the quotient ring gives \begin{align*} [a]_n[b]_n = [ab]_n. \end{align*} Hence the displayed equality is equivalent to \begin{align*} [ab]_n = [0]_n. \end{align*} By the definition of congruence modulo $n$, this means exactly that $n$ divides $ab$. Now we use the primality of $n$. Euclid's lemma for primes says that if a prime integer divides a product of two integers, then it divides at least one of the two factors. Applying that lemma to the prime $n$ and the integers $a,b$, from $n \mid ab$ we obtain \begin{align*} n \mid a \quad \text{or} \quad n \mid b. \end{align*} This is precisely the statement that \begin{align*} [a]_n = [0]_n \quad \text{or} \quad [b]_n = [0]_n. \end{align*} Thus whenever a product in $\mathbb{Z}/n\mathbb{Z}$ is zero, one of its factors is zero. Therefore there are no nonzero zero divisors in $\mathbb{Z}/n\mathbb{Z}$. Since the first step already showed that $\mathbb{Z}/n\mathbb{Z}$ is a nonzero commutative ring with identity, it follows that $\mathbb{Z}/n\mathbb{Z}$ is an integral domain. [/guided] [/step] [step:Construct explicit zero divisors when $n$ is composite] Assume that $n$ is not prime. Since $n \ge 2$, there exists an integer $a \in \mathbb{Z}$ such that $a \mid n$ and \begin{align*} 1 < a < n. \end{align*} Define $b \in \mathbb{Z}$ by $n = ab$. Since $a \mid n$ and $1 < a < n$, the integer $b$ satisfies \begin{align*} 1 < b < n. \end{align*} The inequalities $1 < a < n$ and $1 < b < n$ imply that neither $a$ nor $b$ is divisible by $n$. Hence \begin{align*} [a]_n \ne [0]_n \quad \text{and} \quad [b]_n \ne [0]_n. \end{align*} But \begin{align*} [a]_n[b]_n = [ab]_n = [n]_n = [0]_n. \end{align*} Thus $\mathbb{Z}/n\mathbb{Z}$ contains two nonzero elements whose product is zero, so it is not an integral domain. [/step] [step:Combine the two implications] We have shown that if $n$ is prime, then $\mathbb{Z}/n\mathbb{Z}$ is an integral domain, and that if $n$ is not prime, then $\mathbb{Z}/n\mathbb{Z}$ is not an integral domain. Therefore $\mathbb{Z}/n\mathbb{Z}$ is an integral domain if and only if $n$ is prime. [/step]