Euclidean Domains, PIDs, and UFDs

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. 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: commutative with $1\ne 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.

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)=\mathrm{deg}p$ is Euclidean, proved for 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=(a{b}^{-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 \ne 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 \frac{1}{2}$ and $|s-q|\le \frac{1}{2}$. Set the quotient to $p+qi$ and the remainder to $\gamma =\alpha -(p+qi)\beta$. Then

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 $\frac{1}{\sqrt{2}}$ of a lattice point, so rounding always lands close enough.

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.

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.

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.

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$.

Principal ideal domains

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

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.

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 is applied to concrete examples.

Irreducibles, primes, and unique factorization

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

One implication holds in every integral domain.

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.

Unique factorization repairs the irreducible/prime gap.

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

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

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)⊊(r_1)$. Repeating produces an infinite strictly ascending chain $(r)⊊(r_1)⊊(r_{11})⊊\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.

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.

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.

• (A) A PID that is not Euclidean. The quadratic integer ring $R=\mathbb{Z}\left[\frac{1+\sqrt{-19}}{2}\right]$ 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.²
• (B) A UFD that is not a PID. The ring $\mathbb{Z}[x]$ is a UFD (proved in Gauss's lemma) 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})$.⁴

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(\mathrm{mod}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(\mathrm{mod}4)$, together with $p=2$, splits as $p=(a+bi)(a-bi)=a^2+b^2$.

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(\mathrm{mod}4)$. It rests on a lemma: an odd prime $p$ divides some $n^2+1$ precisely when $p\equiv 1(\mathrm{mod}4)$, because that is when $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ — a cyclic group of order $p-1$, developed in cyclic groups — has an element of order $4$. If $p\equiv 1(\mathrm{mod}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.³