[proofplan] We first use the classification of ideals in $\mathbb{Z}$ to write every ideal as $(d)$ for a unique integer $d \ge 0$. The zero ideal is prime because $\mathbb{Z}$ is an [integral domain](/page/Integral%20Domain). For a nonzero prime ideal $(d)$, primality forces $d$ to be a positive prime integer; conversely, if $p$ is prime, a Bezout-type argument inside the ideal $(p,a)$ proves Euclid's divisibility property and hence shows $(p)$ is prime. The same argument constructs inverses for all nonzero residue classes modulo $p$, proving that $\mathbb{Z}/p\mathbb{Z}$ is a finite field. [/proofplan] [step:Reduce an arbitrary ideal of $\mathbb{Z}$ to a principal ideal with nonnegative generator] Let $P \trianglelefteq \mathbb{Z}$ be a prime ideal. By [citetheorem:9703], there exists a unique integer $d \ge 0$ such that \begin{align*} P = (d). \end{align*} Since a prime ideal is proper, $P \ne \mathbb{Z}$. Because $(1)=\mathbb{Z}$, this implies $d \ne 1$. Thus every prime ideal of $\mathbb{Z}$ has the form $(0)$ or $(d)$ for some integer $d \ge 2$. [/step] [step:Show that the zero ideal is prime] The ideal $(0)$ is proper because $1 \notin (0)$. Let $a,b \in \mathbb{Z}$ and suppose \begin{align*} ab \in (0). \end{align*} Then $ab=0$. By [citetheorem:9704], $\mathbb{Z}$ is an integral domain, so $a=0$ or $b=0$. Equivalently, \begin{align*} a \in (0) \quad \text{or} \quad b \in (0). \end{align*} Therefore $(0)$ is a prime ideal. [/step] [step:Prove that a nonzero prime ideal has prime generator] Let $(d)$ be a prime ideal with $d \ge 2$. We prove that $d$ is a positive prime integer. Suppose, for contradiction, that $d$ is composite. Then there exist integers $a,b \in \mathbb{Z}$ such that \begin{align*} 1 < a < d, \qquad 1 < b < d, \qquad d=ab. \end{align*} Since $ab=d$, we have \begin{align*} ab \in (d). \end{align*} Because $(d)$ is prime, this implies $a \in (d)$ or $b \in (d)$. If $a \in (d)$, then $a=dk$ for some $k \in \mathbb{Z}$. The inequalities $1<a<d$ make this impossible: if $k \le 0$, then $dk \le 0$, while if $k \ge 1$, then $dk \ge d$. Hence $a \notin (d)$. The same argument gives $b \notin (d)$. This contradicts the primality of $(d)$. Therefore $d$ is not composite. Since $d \ge 2$, $d$ is a positive prime integer. [guided] We start with a prime ideal already written as $(d)$, where $d \ge 2$. To prove that $d$ is a prime integer, we use the contrapositive: if $d$ factors nontrivially, then $(d)$ cannot be a prime ideal. Assume that $d$ is composite. Then there are integers $a,b \in \mathbb{Z}$ satisfying \begin{align*} 1 < a < d, \qquad 1 < b < d, \qquad d=ab. \end{align*} The equality $d=ab$ says exactly that $ab$ is a multiple of $d$, so \begin{align*} ab \in (d). \end{align*} Now apply the definition of prime ideal to $(d)$. Since $(d)$ is prime and $ab \in (d)$, primality requires \begin{align*} a \in (d) \quad \text{or} \quad b \in (d). \end{align*} But neither membership is possible. If $a \in (d)$, then $a=dk$ for some $k \in \mathbb{Z}$. If $k \le 0$, then $dk \le 0$, contradicting $a>1$. If $k \ge 1$, then $dk \ge d$, contradicting $a<d$. Thus $a \notin (d)$. The same argument, using $1<b<d$, gives $b \notin (d)$. We have found elements $a,b \notin (d)$ whose product lies in $(d)$, contradicting the defining property of a prime ideal. Therefore $d$ cannot be composite. Since $d \ge 2$, it follows that $d$ is a positive prime integer. [/guided] [/step] [step:Prove that $(p)$ is prime when $p$ is a positive prime integer] Let $p \in \mathbb{Z}$ be a positive prime integer. The ideal $(p)$ is proper because $p \ne \pm 1$. Let $a,b \in \mathbb{Z}$ and suppose \begin{align*} ab \in (p). \end{align*} Equivalently, $p$ divides $ab$. We prove that $a \in (p)$ or $b \in (p)$. Assume $a \notin (p)$. Define the ideal \begin{align*} J := (p,a)=\{mp+na : m,n \in \mathbb{Z}\}. \end{align*} By [citetheorem:9703], there exists a unique integer $e \ge 0$ such that \begin{align*} J=(e). \end{align*} Since $p \in J=(e)$, there exists $r \in \mathbb{Z}$ such that $p=er$, so $e$ divides $p$. Since $p$ is a positive prime integer, $e \in \{1,p\}$. If $e=p$, then $J=(p)$, and because $a \in J$, we get $a \in (p)$, contradicting the assumption. Hence $e=1$, so $J=(1)=\mathbb{Z}$. Therefore $1 \in J$, and there exist integers $m,n \in \mathbb{Z}$ such that \begin{align*} 1=mp+na. \end{align*} Multiplying by $b$ gives \begin{align*} b=mpb+nab. \end{align*} The term $mpb$ lies in $(p)$, and $nab$ lies in $(p)$ because $ab \in (p)$. Since $(p)$ is an additive subgroup of $\mathbb{Z}$, it follows that $b \in (p)$. Thus whenever $ab \in (p)$, either $a \in (p)$ or $b \in (p)$. Hence $(p)$ is a prime ideal. [/step] [step:Show that $\mathbb{Z}/p\mathbb{Z}$ has exactly $p$ elements] Let $p \in \mathbb{Z}$ be a positive prime integer. Define the quotient map \begin{align*} \pi: \mathbb{Z} &\to \mathbb{Z}/p\mathbb{Z} \end{align*} by sending each integer $n$ to its residue class \begin{align*} \pi(n)=n+p\mathbb{Z}. \end{align*} Every integer $n \in \mathbb{Z}$ has a unique residue $r \in \{0,1,\dots,p-1\}$ modulo $p$, so \begin{align*} \mathbb{Z}/p\mathbb{Z}=\{\pi(0),\pi(1),\dots,\pi(p-1)\}. \end{align*} These $p$ residue classes are distinct: if $\pi(r)=\pi(s)$ with $0 \le r,s \le p-1$, then $p$ divides $r-s$. Since \begin{align*} -(p-1) \le r-s \le p-1, \end{align*} the only multiple of $p$ in this interval is $0$, so $r=s$. Therefore $\mathbb{Z}/p\mathbb{Z}$ has exactly $p$ elements. [/step] [step:Construct inverses for nonzero residue classes modulo $p$] Let $\alpha \in \mathbb{Z}/p\mathbb{Z}$ be nonzero. Choose an integer $a \in \mathbb{Z}$ such that \begin{align*} \alpha=\pi(a). \end{align*} Since $\alpha \ne 0$, we have $a \notin (p)$. Define the ideal \begin{align*} J := (p,a)=\{mp+na : m,n \in \mathbb{Z}\}. \end{align*} As in the previous argument, [citetheorem:9703] gives $J=(e)$ for some $e \ge 0$; since $p \in J$, the integer $e$ divides $p$; and since $a \in J$ while $a \notin (p)$, one cannot have $e=p$. Thus $e=1$, so there exist integers $m,n \in \mathbb{Z}$ satisfying \begin{align*} 1=mp+na. \end{align*} Applying the quotient map $\pi$ gives \begin{align*} \pi(1)=\pi(m)\pi(p)+\pi(n)\pi(a)=0+\pi(n)\alpha. \end{align*} Thus $\pi(n)\alpha=\pi(1)$, so $\alpha$ has a multiplicative inverse in $\mathbb{Z}/p\mathbb{Z}$. The quotient $\mathbb{Z}/p\mathbb{Z}$ is a commutative unital ring, and every nonzero element has a multiplicative inverse. Hence $\mathbb{Z}/p\mathbb{Z}$ is a field. Together with the preceding step, it is a finite field with exactly $p$ elements. [/step] [step:Combine the classification and the quotient conclusion] The preceding steps show that $(0)$ is prime, that every nonzero prime ideal of $\mathbb{Z}$ is of the form $(p)$ for a positive prime integer $p$, and that every ideal $(p)$ with $p$ a positive prime integer is prime. Hence the prime ideals of $\mathbb{Z}$ are precisely \begin{align*} (0) \quad \text{and} \quad (p) \text{ for positive prime integers } p. \end{align*} For each such $p$, the [quotient ring](/page/Quotient%20Ring) $\mathbb{Z}/p\mathbb{Z}$ is a finite field with exactly $p$ elements. This proves the theorem. [/step]