---
title: Euclidean Domains, PIDs, and UFDs
module: Factorization and Polynomial Rings
moduleNumber: 7
lessonNumber: 1
order: 701
summary: >
  Three classes of integral domain, ordered by how much of elementary
  arithmetic survives: Euclidean domains carry a division algorithm, principal
  ideal domains make every ideal a single multiple, and unique factorization
  domains factor every element into irreducibles in one way. We prove the chain
  ED implies PID implies UFD, the classes are separated by explicit
  counterexamples, and irreducible and prime coincide exactly in a UFD.
topics: [Factorization and Polynomial Rings]
sources:
  - book: Dummit & Foote
    ref: "Ch. 8 — Euclidean, Principal Ideal, and Unique Factorization Domains; §8.1 Euclidean Domains, §8.2 Principal Ideal Domains, §8.3 Unique Factorization Domains"
  - book: Judson
    ref: "Ch. 18 — Integral Domains; §18.2 Factorization in Integral Domains"
draft: false
---

The integers support two operations that most rings do not: long division with a
smaller remainder, and factorization into primes that is unique up to sign. Both
rest on the same fact, that $\mathbb{Z}$ is well-ordered, and both were used
without comment in
[modular arithmetic](/abstract-algebra/foundations/integers-and-modular-arithmetic).
Turning each property into a ring axiom and asking which rings satisfy it gives a
strict hierarchy — Euclidean domains inside principal ideal domains inside unique
factorization domains — and the counterexamples separating the three tiers are as
informative as the implications joining them.

Throughout, every ring is a commutative
[integral domain](/abstract-algebra/ring-theory/rings-definitions-and-examples):
commutative with $1 \neq 0$ and no zero divisors. That last condition is what
lets us cancel, and cancellation is used at nearly every step.

## Norms and the division algorithm

A division algorithm needs a notion of "size" so that a remainder can be
declared smaller than a divisor. The requirement on that measure is deliberately
weak.

> **Definition (Norm).** A **norm** on an integral domain $R$ is any function
> $N : R \to \mathbb{Z}_{\geq 0}$ with $N(0) = 0$. It is a **positive norm** if
> $N(a) > 0$ for every $a \neq 0$. A single domain may carry many different
> norms.

> **Definition (Euclidean domain).** An integral domain $R$ is a **Euclidean
> domain** if it admits a norm $N$ such that for all $a, b \in R$ with $b \neq
> 0$ there exist $q, r \in R$ with
> $$
> a = qb + r, \qquad r = 0 \ \text{ or } \ N(r) < N(b).
> $$
> The element $q$ is the **quotient** and $r$ the **remainder**. Neither is
> required to be unique.[^df81]

The definition requires only that _some_ pair $(q, r)$ exists with a strictly
smaller remainder; it says nothing about how to find it or whether it is one of
a kind. In $\mathbb{Z}$ with $N(a) = |a|$ the remainder is unique once we insist
$0 \le r < |b|$, but $5 = 2 \cdot 2 + 1 = 3 \cdot 2 - 1$ already shows two valid
outputs of the algorithm when the sign of $r$ is left free.

- **The integers.** $\mathbb{Z}$ with $N(a) = |a|$ is Euclidean; this is ordinary
  long division.
- **Polynomials over a field.** $F[x]$ with $N(p) = \deg p$ is Euclidean, proved
  for [polynomial rings over fields](/abstract-algebra/factorization-and-polynomials/polynomial-rings-over-fields).
  The coefficients must lie in a field so that leading coefficients can be
  inverted.
- **Fields.** Any field is trivially Euclidean: take $N(a) = 0$ throughout and
  write $a = (ab^{-1})b + 0$.
- **The Gaussian integers** $\mathbb{Z}[i] = \{a + bi : a, b \in \mathbb{Z}\}$
  with $N(a + bi) = a^2 + b^2$ is Euclidean, shown below.

The Gaussian case is the first that is not obvious. Given $\alpha, \beta \in \mathbb{Z}[i]$ with $\beta \neq 0$, form the exact
quotient $\alpha/\beta = r + si$ in the fraction field $\mathbb{Q}(i)$, where
$r, s \in \mathbb{Q}$. Round each coordinate to a nearest integer: choose
$p, q \in \mathbb{Z}$ with $|r - p| \le \tfrac{1}{2}$ and $|s - q| \le
\tfrac{1}{2}$. Set the quotient to $p + qi$ and the remainder to
$\gamma = \alpha - (p + qi)\beta$. Then

$$
N(\gamma) = N\big((r - p) + (s - q)i\big)\, N(\beta)
\;\le\; \Big(\tfrac{1}{4} + \tfrac{1}{4}\Big) N(\beta) = \tfrac{1}{2} N(\beta)
\;<\; N(\beta),
$$

using multiplicativity $N(zw) = N(z)N(w)$ of the norm. The remainder is strictly
smaller, so $\mathbb{Z}[i]$ is Euclidean. Geometrically, every complex number
lies within distance $\tfrac{1}{\sqrt 2}$ of a lattice point, so rounding always
lands close enough.

$$
% caption: Division in $\mathbb{Z}[i]$: the exact quotient $\alpha/\beta$ (open
% dot) lands in some unit cell of the integer lattice, and rounding moves it to
% the nearest corner (filled). No point of a cell is farther than half a
% diagonal, $\tfrac{1}{\sqrt 2}$, from a corner (dashed worst case), so the
% remainder always has norm smaller than $N(\beta)$.
\begin{tikzpicture}[scale=1.15, >=stealth, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
% lattice dots
\foreach \x in {1,2,3,4} \foreach \y in {0,1,2,3}
  \fill[black] (\x,\y) circle (1.4pt);
% the unit cell containing the quotient
\fill[acc!12] (2,1) rectangle (3,2);
\draw[black] (2,1) rectangle (3,2);
% redraw the cell's corner dots above the fill so the cell reads as a lattice cell
\foreach \p in {(2,1),(2,2),(3,1),(3,2)} \fill[black] \p circle (1.6pt);
% worst case: the cell center is half a diagonal from every corner
\draw[black, dashed] (2.5,1.5) -- (2,1);
% exact quotient and the rounding step to its nearest corner
\node[draw, circle, fill=white, inner sep=1.3pt] (Q) at (2.68,1.70) {};
\draw[->, acc, thick] (2.74,1.76) -- (2.94,1.94);
\fill[acc] (3,2) circle (2.2pt);
\node[anchor=north, inner sep=5pt] at (2.68,1.70) {exact quotient};
\node[acc, anchor=south west, inner sep=3pt] at (3.04,2.02) {nearest lattice point};
% scale
\draw[<->, black] (2,0.62) -- (3,0.62);
\node[anchor=north] at (2.5,0.58) {one unit};
\end{tikzpicture}
$$

> **Worked example.** Compute a gcd of $\alpha = 1 + 5i$ and $\beta = 3 + i$ in
> $\mathbb{Z}[i]$; each division rounds the exact quotient to a nearest lattice
> point. Dividing $\alpha$ by $\beta$,
> $$
> \frac{\alpha}{\beta} = \frac{(1 + 5i)(3 - i)}{10} = \frac{8 + 14i}{10}
> = 0.8 + 1.4i,
> $$
> which rounds to $1 + i$, leaving remainder $\alpha - (1 + i)\beta = -1 + i$ with
> $N(-1 + i) = 2 < 10 = N(\beta)$. Divide $\beta$ by that remainder:
> $$
> \frac{3 + i}{-1 + i} = \frac{(3 + i)(-1 - i)}{2} = -1 - 2i,
> $$
> an exact quotient, so the next remainder is $0$. The last nonzero remainder
> $-1 + i$ is a gcd; times the unit $i$ it becomes $1 + i$, matching the common
> factor in $\alpha = (1 + i)(3 + 2i)$ and $\beta = (1 + i)(2 - i)$.

## From a division algorithm to principal ideals

The first consequence of a division algorithm is structural rather than
computational: every ideal is generated by one element.

> **Proposition (Euclidean implies principal).** Every ideal in a Euclidean
> domain $R$ is principal. Precisely, a nonzero ideal $I$ equals $(d)$ for any
> nonzero $d \in I$ of minimum norm.[^df81]

The proof is the argument that classifies subgroups of $\mathbb{Z}$, transposed
to ideals. Pick $d \in I$ nonzero of least norm — possible because norms are
nonnegative integers and $\mathbb{Z}$ is well-ordered. Certainly $(d) \subseteq
I$. For the reverse, take any $a \in I$ and divide: $a = qd + r$ with $r = 0$ or
$N(r) < N(d)$. Since $r = a - qd \in I$, a nonzero $r$ would beat $d$'s
minimality, so $r = 0$ and $a \in (d)$. Hence $I = (d)$.

The **greatest common divisor** is defined so that it makes sense in any
commutative ring, computable or not.

> **Definition (GCD).** A **greatest common divisor** of $a, b \in R$ is a
> nonzero $d$ with (i) $d \mid a$ and $d \mid b$, and (ii) every common divisor
> $d'$ of $a$ and $b$ divides $d$. Any two gcds differ by a unit.

The divisibility $b \mid a$ says exactly $(a) \subseteq (b)$, so translating the
two conditions into ideals shows a gcd of $a$ and $b$ is a generator of the
smallest principal ideal containing both. In a Euclidean domain the ideal
$(a, b)$ is already principal by the proposition, so a gcd exists and, better,
is produced by iterating the division algorithm.

> **Theorem (Euclidean algorithm).** Let $R$ be Euclidean and $a, b$ nonzero.
> The last nonzero remainder $d = r_n$ in the repeated divisions
> $$
> a = q_0 b + r_0,\quad b = q_1 r_0 + r_1,\quad r_0 = q_2 r_1 + r_2,\ \dots
> $$
> is a gcd of $a$ and $b$, and $(d) = (a, b)$. In particular there are
> $x, y \in R$ with $d = ax + by$ (**Bézout**).[^df81]

The remainders satisfy $N(b) > N(r_0) > N(r_1) > \cdots$, a strictly decreasing
sequence of nonnegative integers, so the process halts. Tracking divisibility
upward from the last equation shows $d$ divides every earlier remainder and
finally $a$ and $b$; back-substituting expresses $d = ax + by$.

> **Worked example.** Run the algorithm on $a = 2210$, $b = 1131$ in
> $\mathbb{Z}$:
> $$
> \begin{aligned}
> 2210 &= 1 \cdot 1131 + 1079, & 1079 &= 20 \cdot 52 + 39, \\
> 1131 &= 1 \cdot 1079 + 52, & 52 &= 1 \cdot 39 + 13, \\
> & & 39 &= 3 \cdot 13.
> \end{aligned}
> $$
> The last nonzero remainder is $\gcd(2210, 1131) = 13$. Back-substitution
> collects the intermediate remainders into a Bézout relation,
> $$
> 13 = 21 \cdot 52 - 1079 = 21 \cdot 1131 - 22 \cdot 1079
> = (-22) \cdot 2210 + 43 \cdot 1131.
> $$

$$
% caption: The Euclidean algorithm as a ladder: each remainder becomes the next
% divisor, norms strictly decrease, and the last nonzero remainder is the gcd.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=15mm, minimum height=8mm, align=center}]
\definecolor{acc}{HTML}{4A6FA5}
\node[cell] (a) at (0,0) {2210};
\node[cell] (b) at (2.3,0) {1131};
\node[cell] (r0) at (4.6,0) {1079};
\node[cell] (r1) at (6.9,0) {52};
\node[cell] (r2) at (9.2,0) {39};
\node[cell, draw=acc, text=acc, thick] (r3) at (11.5,0) {13};
\draw[->, acc] (a) -- (b);
\draw[->, acc] (b) -- (r0);
\draw[->, acc] (r0) -- (r1);
\draw[->, acc] (r1) -- (r2);
\draw[->, acc] (r2) -- (r3);
\node[anchor=north, black] at (5.75,-0.55) {each step: divide, keep the remainder};
\node[acc, anchor=south] at (11.5,0.55) {gcd};
\end{tikzpicture}
$$

## Principal ideal domains

Dropping the algorithm but keeping its consequence gives a strictly larger
class.

> **Definition (PID).** A **principal ideal domain** is an integral domain in
> which every ideal is principal.

Every Euclidean domain is a PID by the proposition above, so every theorem about
PIDs applies to $\mathbb{Z}$, $F[x]$, and $\mathbb{Z}[i]$ automatically. Two
facts about PIDs are used constantly, and both fail in general rings.

> **Proposition (Bézout in a PID).** In a PID, a generator $d$ of $(a, b)$ is a
> gcd of $a$ and $b$, is expressible as $d = ax + by$, and is unique up to a
> unit. The existence is the same as in a Euclidean domain; only the _algorithm_
> for finding $d$ is lost.[^df82]

> **Proposition (nonzero primes are maximal).** In a PID every nonzero
> [prime ideal](/abstract-algebra/ring-theory/ideals-quotients-and-homomorphisms)
> is maximal.[^df82]

For the second, let $(p)$ be a nonzero prime and $(m) \supseteq (p)$ an ideal
containing it. Then $p = rm$, and since $(p)$ is prime either $m \in (p)$ (giving
$(m) = (p)$) or $r \in (p)$, say $r = ps$, whence $p = psm$ forces $sm = 1$ and
$m$ a unit, so $(m) = R$. There is nothing between $(p)$ and $R$.

The advantage of a Euclidean domain over a general PID is the algorithm itself:
gcds exist in both, but only a Euclidean domain provides a procedure to compute
one. This matters when the
[structure theorem for modules over a PID](/abstract-algebra/modules-over-pids/structure-theorem-over-pids)
is applied to concrete examples.

## Irreducibles, primes, and unique factorization

Factorization needs two kinds of atom, and their relationship decides whether
factorization is unique.

> **Definition (irreducible, prime, associate).** Let $r \in R$ be nonzero and
> not a unit.
> - $r$ is **irreducible** if $r = ab$ forces $a$ or $b$ to be a unit.
> - $r$ is **prime** if $(r)$ is a prime ideal: $r \mid ab$ implies $r \mid a$
>   or $r \mid b$.
> - $a$ and $b$ are **associate** if $a = ub$ for some unit $u$.

One implication holds in every integral domain.

> **Proposition.** A prime element is irreducible.[^df83]

If $p$ is prime and $p = ab$, then $ab \in (p)$, so (say) $a = pr$; substituting,
$p = prb$ gives $rb = 1$, so $b$ is a unit. The converse fails. In
$\mathbb{Z}[\sqrt{-5}]$ the element $3$ is irreducible, yet $3 \mid (2 +
\sqrt{-5})(2 - \sqrt{-5}) = 9$ while $3$ divides neither factor, so $3$ is not
prime. The gap between irreducible and prime is precisely the failure of unique
factorization.

$$
% caption: In a general integral domain every prime is irreducible but not
% conversely; the two notions coincide exactly in a UFD (and hence in a PID).
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
% general domain: prime inside irreducible
\draw[black] (0,0) ellipse (2.2 and 1.4);
\draw[acc, thick, fill=acc!10] (-0.5,0) ellipse (1.2 and 0.95);
\node[acc] at (-0.5,0) {prime};
\node[black, anchor=west] at (0.8,0.55) {irreducible};
\node[anchor=north, black] at (0,-1.55) {general integral domain};
% UFD: equal
\begin{scope}[xshift=6.2cm]
\draw[acc, thick, fill=acc!10] (0,0) ellipse (1.5 and 1.15);
\node[acc] at (0,0.18) {prime};
\node[acc] at (0,-0.3) {$=$ irreducible};
\node[anchor=north, black] at (0,-1.55) {UFD};
\end{scope}
\end{tikzpicture}
$$

> **Definition (UFD).** A **unique factorization domain** is an integral domain
> $R$ in which every nonzero nonunit $r$ satisfies:
> - **(existence)** $r = p_1 p_2 \cdots p_n$ is a finite product of
>   irreducibles, and
> - **(uniqueness)** if also $r = q_1 \cdots q_m$ with each $q_j$ irreducible,
>   then $m = n$ and, after renumbering, $p_i$ is associate to $q_i$ for every
>   $i$.[^df83]

Unique factorization repairs the irreducible/prime gap.

> **Proposition.** In a UFD, an element is prime if and only if it is
> irreducible.[^df83]

Given an irreducible $p$ dividing $ab$, write $ab = pc$ and factor $a$, $b$, $c$
into irreducibles; uniqueness of the factorization of $ab$ forces $p$ to be
associate to one of the irreducibles of $a$ or of $b$, hence $p \mid a$ or $p
\mid b$. This is why the failure of primality for $3$ in $\mathbb{Z}[\sqrt{-5}]$
is a certificate that the ring is _not_ a UFD: there $6 = 2 \cdot 3 = (1 +
\sqrt{-5})(1 - \sqrt{-5})$ are two genuinely different factorizations into
irreducibles.

## PID implies UFD

> **Theorem.** Every principal ideal domain is a unique factorization domain.
> Hence every Euclidean domain is a UFD as well.[^df83]

The proof has two halves. The first needs a finiteness principle.

> **Lemma (ascending chain condition).** In a PID, any ascending chain of ideals
> $I_1 \subseteq I_2 \subseteq \cdots$ eventually stabilizes: $I_k = I_n$ for all
> $k \geq n$.

Take the union $I = \bigcup_i I_i$, which is an ideal. In a PID $I = (a)$ for
some $a$, and $a$ lies in some $I_n$; then $I_n \subseteq I = (a) \subseteq I_n$,
so the chain is constant from $I_n$ on.

**Existence of a factorization.** Suppose some nonzero nonunit $r$ had no
factorization into irreducibles. Then $r$ is not irreducible, so $r = r_1 r_2$
with both nonunits, and at least one factor — say $r_1$ — again has no
factorization, giving a proper inclusion $(r) \subsetneq (r_1)$. Repeating
produces an infinite strictly ascending chain $(r) \subsetneq (r_1) \subsetneq
(r_{11}) \subsetneq \cdots$, contradicting the ascending chain condition. So
every $r$ factors.

**Uniqueness.** Induct on the number $n$ of irreducible factors of $r$. If two
factorizations $p_1 \cdots p_n = q_1 \cdots q_m$ are given, then $p_1$ is prime
(irreducible equals prime in a PID, via the maximal-ideal proposition), so $p_1$
divides some $q_j$; after renumbering $p_1 \mid q_1$, and since $q_1$ is
irreducible, $q_1 = p_1 u$ with $u$ a unit — the two are associate. Cancel $p_1$
and apply the inductive hypothesis. The two factorizations match up to
associates and order.

$$
% caption: The factorization tree of an element: branch until every leaf is
% irreducible; the ascending chain condition guarantees the tree is finite, and
% primality of irreducibles makes the multiset of leaves unique up to units.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize,
  nd/.style={draw, circle, minimum size=7mm, inner sep=0pt},
  lf/.style={draw, circle, minimum size=7mm, inner sep=0pt, fill=acc!12}]
\definecolor{acc}{HTML}{4A6FA5}
\node[nd] (r) at (0,2.4) {$r$};
\node[nd] (a) at (-2,1.2) {$r_1$};
\node[nd] (b) at (2,1.2) {$r_2$};
\node[lf] (p1) at (-3,0) {$p_1$};
\node[lf] (p2) at (-1,0) {$p_2$};
\node[lf] (p3) at (1,0) {$p_3$};
\node[nd] (c) at (3,0) {$r_{21}$};
\node[lf] (p4) at (2.2,-1.2) {$p_4$};
\node[lf] (p5) at (3.8,-1.2) {$p_5$};
\draw[acc] (r) -- (a); \draw[acc] (r) -- (b);
\draw[acc] (a) -- (p1); \draw[acc] (a) -- (p2);
\draw[acc] (b) -- (p3); \draw[acc] (b) -- (c);
\draw[acc] (c) -- (p4); \draw[acc] (c) -- (p5);
\node[anchor=west, black] at (4.6,0.6) {shaded leaves};
\node[anchor=west, black] at (4.6,0.1) {are irreducible};
\end{tikzpicture}
$$

Specializing to $\mathbb{Z}$, which is Euclidean, recovers the **fundamental
theorem of arithmetic** as a corollary. The same argument, applied to $F[x]$,
gives unique factorization of
[polynomials over a field](/abstract-algebra/factorization-and-polynomials/polynomial-rings-over-fields).

## The hierarchy is strict

Each implication $\text{ED} \Rightarrow \text{PID} \Rightarrow \text{UFD}
\Rightarrow \text{domain}$ is one-way. Explicit rings occupy each gap.

$$
% caption: The four classes as nested regions; each annulus is nonempty, witnessed
% by a ring that satisfies the outer property but not the inner one.
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black, fill=acc!4] (0,0) ellipse (4.6 and 3.1);
\draw[black, fill=acc!7] (0,0) ellipse (3.6 and 2.5);
\draw[black, fill=acc!10] (0,0) ellipse (2.5 and 1.85);
\draw[acc, thick, fill=acc!14] (0,0) ellipse (1.4 and 1.1);
\node[acc] at (0,0.15) {Euclidean};
\node[acc] at (0,-0.28) {domains};
\node at (0,1.45) {PID};
\node at (0,2.15) {UFD};
\node at (0,2.78) {integral domains};
\node[black!70] at (0,-0.72) {$\mathbb{Z}$, $F[x]$, $\mathbb{Z}[i]$};
\fill[black] (0,1.15) circle (1.6pt);
\node[black!70, anchor=south, font=\scriptsize] at (0,1.2) {(A)};
\node[black!70] at (0,1.78) {$\mathbb{Z}[x]$};
\fill[black] (0,2.45) circle (1.6pt);
\node[black!70, anchor=south, font=\scriptsize] at (0,2.5) {(B)};
\end{tikzpicture}
$$

- **(A) A PID that is not Euclidean.** The quadratic integer ring $R =
  \mathbb{Z}\big[\tfrac{1 + \sqrt{-19}}{2}\big]$ is a PID but admits no norm
  making it Euclidean. It has no _universal side divisor_, a weaker feature that
  every non-field Euclidean domain must possess, so it cannot be Euclidean; its
  field norm nonetheless satisfies the weaker Dedekind–Hasse condition, which is
  equivalent to being a PID.[^df82]
- **(B) A UFD that is not a PID.** The ring $\mathbb{Z}[x]$ is a UFD (proved in
  [Gauss's lemma](/abstract-algebra/factorization-and-polynomials/gauss-lemma-and-unique-factorization))
  but the ideal $(2, x)$ needs two generators and is not principal, so it is not
  a PID.
- **An integral domain that is not a UFD.** In $\mathbb{Z}[\sqrt{-5}]$ the number
  $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ factors two ways into
  irreducibles. Judson runs the parallel example in $\mathbb{Z}[\sqrt{-3}]$,
  where $4 = 2 \cdot 2 = (1 + \sqrt{-3})(1 - \sqrt{-3})$.[^ju182]

> **Worked example.** Verify non-unique factorization in $\mathbb{Z}[\sqrt{-5}]$
> with norms. The norm $N(a + b\sqrt{-5}) = a^2 + 5b^2$ is multiplicative, and
> $a^2 + 5b^2 = m$ has no integer solution for $m = 2$ or $m = 3$, so no element
> has norm $2$ or $3$. In
> $$
> 6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}),
> $$
> the factors have norms $N(2) = 4$, $N(3) = 9$, and $N(1 \pm \sqrt{-5}) = 6$.
> A nontrivial factor of $2$ would have norm $2$, which is impossible, so $2$ is
> irreducible; the same count makes $3$, $1 + \sqrt{-5}$, and $1 - \sqrt{-5}$
> irreducible. The units are $\pm 1$ (the only elements of norm $1$), so $2$ is
> not associate to $1 \pm \sqrt{-5}$. The two factorizations of $6$ are genuinely
> different, and $\mathbb{Z}[\sqrt{-5}]$ is not a UFD.

| Class | Defining property | gcd exists? | irreducible $=$ prime? | Separating example |
| --- | --- | --- | --- | --- |
| Euclidean domain | division algorithm w.r.t. a norm | yes, **computable** | yes | $\mathbb{Z}$, $F[x]$, $\mathbb{Z}[i]$ |
| PID | every ideal principal | yes | yes | $\mathbb{Z}\big[\tfrac{1+\sqrt{-19}}{2}\big]$ (PID, not ED) |
| UFD | unique factorization into irreducibles | yes | yes | $\mathbb{Z}[x]$ (UFD, not PID) |
| Integral domain | no zero divisors | not always | no | $\mathbb{Z}[\sqrt{-5}]$ (not a UFD) |

## Primes in the Gaussian integers

Because $\mathbb{Z}[i]$ is a UFD, its irreducibles _are_ its primes, and knowing
them settles a classical question in number theory. A rational prime $p$ can
behave in three ways inside $\mathbb{Z}[i]$.

- If $N(\alpha)$ is a rational prime, then $\alpha$ is irreducible in
  $\mathbb{Z}[i]$, since a factorization $\alpha = \beta\gamma$ would split the
  prime $N(\alpha) = N(\beta)N(\gamma)$.
- A rational prime $p \equiv 3 \pmod 4$ stays irreducible in $\mathbb{Z}[i]$ (it
  is not a sum of two squares, so no element has norm $p$).
- A rational prime $p \equiv 1 \pmod 4$, together with $p = 2$, splits as
  $p = (a + bi)(a - bi) = a^2 + b^2$.

> **Worked example.** Classify the small rational primes in $\mathbb{Z}[i]$. The
> prime $2 = -i(1 + i)^2$ ramifies. The prime $5 \equiv 1 \pmod 4$ splits as
> $5 = (2 + i)(2 - i)$, and $13 \equiv 1 \pmod 4$ splits as
> $13 = (3 + 2i)(3 - 2i)$; each factor is irreducible because its norm ($5$ and
> $13$) is a rational prime. The prime $7 \equiv 3 \pmod 4$ stays irreducible:
> $a^2 + b^2 = 7$ has no integer solution, so nothing in $\mathbb{Z}[i]$ has norm
> $7$, and a factorization would split $N(7) = 49$ into two norm-$7$ pieces.

The split case is **Fermat's theorem on sums of two squares**: $p$ is a sum of
two integer squares exactly when $p = 2$ or $p \equiv 1 \pmod 4$. It rests on a
lemma: an odd prime $p$ divides some $n^2 + 1$ precisely when $p \equiv 1 \pmod
4$, because that is when $(\mathbb{Z}/p\mathbb{Z})^\times$ — a cyclic group of
order $p - 1$, developed in
[cyclic groups](/abstract-algebra/subgroups-and-quotients/cyclic-groups) — has
an element of order $4$. If $p \equiv 1 \pmod 4$ were irreducible in
$\mathbb{Z}[i]$ it would divide $n + i$ or $n - i$, hence both (being real) and
their difference $2i$, which is false. So $p$ splits.[^df83]

[^df81]: **Dummit & Foote**, _Abstract Algebra_, §8.1 — Euclidean Domains: the norm and division-algorithm definitions, the proof that every ideal of a Euclidean domain is principal, and the Euclidean algorithm producing a gcd as an $R$-linear combination.
[^df82]: **Dummit & Foote**, _Abstract Algebra_, §8.2 — Principal Ideal Domains: gcds and Bézout in a PID, nonzero primes are maximal, and the Dedekind–Hasse norm characterization used to show $\mathbb{Z}[(1+\sqrt{-19})/2]$ is a PID that is not Euclidean.
[^df83]: **Dummit & Foote**, _Abstract Algebra_, §8.3 — Unique Factorization Domains: irreducible versus prime, the definition of a UFD, the theorem that every PID is a UFD via the ascending chain condition, and the description of the Gaussian primes with Fermat's two-squares theorem.
[^ju182]: **Judson**, _Abstract Algebra: Theory and Applications_, §18.2 — Factorization in Integral Domains: the UFD definition, the non-unique factorization $4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3})$ in $\mathbb{Z}[\sqrt{-3}]$, and the theorem that every PID is a UFD.