Euclidean domains, PIDs and UFDs

The integers and the polynomial rings \(F[x]\) share three properties: a division algorithm, the fact that every ideal is principal, and unique factorization into irreducibles. This lesson separates the three, shows that each implies the next, and studies the classic example beyond \(\mathbb{Z}\) and \(F[x]\), the Gaussian integers \(\mathbb{Z}[i]\). It ends with rings where unique factorization breaks down, the phenomenon that led Kummer and Dedekind to the theory of ideals.

Divisibility in a domain

Throughout, \(D\) is an integral domain. We say \(a\) divides \(b\), \(a \mid b\), if \(b = ac\) for some \(c \in D\). Elements \(a, b\) are associates if \(a = ub\) for a unit \(u\); associates divide each other and generate the same principal ideal. In \(\mathbb{Z}\) the associates of \(n\) are \(\pm n\); in \(\mathbb{Z}[i]\) they are \(n, -n, in, -in\); in \(F[x]\) they are the nonzero constant multiples.

There are two different ways to generalize a prime number, and in general rings they are not the same.

• A nonzero nonunit \(p\) is irreducible if whenever \(p = ab\), one of \(a, b\) is a unit.

• A nonzero nonunit \(p\) is prime if whenever \(p \mid ab\), \(p \mid a\) or \(p \mid b\). Equivalently, \((p)\) is a nonzero prime ideal.

Every prime is irreducible: if \(p = ab\), then \(p \mid ab\), so say \(p \mid a\), \(a = pc\), and \(p = pcb\) gives \(cb = 1\) by cancellation, so \(b\) is a unit. In \(\mathbb{Z}\) the converse is Euclid's lemma. In general it fails. In \(\mathbb{Z}[\sqrt{-5}]\), 2 is irreducible but not prime: \(2\) divides \(6 = (1 + \sqrt{-5})(1 - \sqrt{-5})\) but neither factor, since \(\frac{1 \pm \sqrt{-5}}{2} \notin \mathbb{Z}[\sqrt{-5}]\).

Three kinds of domain

Definition. An integral domain \(D\) is a Euclidean domain if there is a function \(N : D \setminus \{0\} \to \{0, 1, 2, \ldots\}\) such that for all \(a\) and all \(b \ne 0\) there are \(q, r\) with \(a = qb + r\) and either \(r = 0\) or \(N(r) < N(b)\).

Definition. \(D\) is a principal ideal domain (PID) if every ideal is principal.

Definition. \(D\) is a unique factorization domain (UFD) if every nonzero nonunit is a product of irreducibles, and the factorization is unique up to order and associates: if \(p_1\cdots p_r = q_1\cdots q_s\) then \(r = s\) and after reordering each \(q_i\) is an associate of \(p_i\).

Examples: \(\mathbb{Z}\) is Euclidean with \(N(a) = |a|\); \(F[x]\) is Euclidean with \(N(f) = \deg f\); \(\mathbb{Z}[i]\) is Euclidean with \(N(a + bi) = a^2 + b^2\), as we prove below. Every field is trivially Euclidean.

Theorem. Every Euclidean domain is a PID.

Proof: the argument of lesson 6 for \(F[x]\) works verbatim. A nonzero ideal \(I\) contains an element \(b\) of least norm, and for \(a \in I\), \(a = qb + r\) with \(r = a - qb \in I\); minimality forces \(r = 0\).

Theorem. Every PID is a UFD.

Proof sketch: two steps. Existence: if some element had no factorization into irreducibles, we could write it as a product of two nonunits, at least one without a factorization, and repeat, producing an infinite strictly increasing chain of principal ideals \((a_1) \subsetneq (a_2) \subsetneq \cdots\). In a PID the union of such a chain is an ideal, generated by some \(c\), and \(c\) lies in some \((a_k)\), so the chain stops at \(k\), a contradiction. Uniqueness: in a PID, an irreducible \(p\) generates a maximal ideal (if \((p) \subseteq (c)\) then \(p = cd\), and one of \(c, d\) is a unit), and maximal ideals are prime, so irreducibles are prime. Uniqueness then follows exactly as in \(\mathbb{Z}\): \(p_1\) divides some \(q_j\), they are associates, cancel, and induct.

The chain condition used in the existence proof, that every increasing chain of ideals stabilizes, is the defining property of Noetherian rings, named for Emmy Noether, who made it the foundation of commutative algebra in 1921. The implications are strict. \(\mathbb{Z}[x]\) and \(F[x, y]\) are UFDs that are not PIDs, since \((2, x)\) and \((x, y)\) are not principal. A PID that is not Euclidean is harder to find: \(\mathbb{Z}[\frac{1 + \sqrt{-19}}{2}]\) is the standard example.

The Gaussian integers

Gauss introduced \(\mathbb{Z}[i] = \{a + bi : a, b \in \mathbb{Z}\}\) in 1832 to study biquadratic reciprocity. The key tool is the norm \(N(a + bi) = a^2 + b^2 = |a + bi|^2\), which is multiplicative, \(N(\alpha\beta) = N(\alpha)N(\beta)\), because absolute value is. So \(\alpha\) is a unit exactly when \(N(\alpha) = 1\), and if \(\alpha \mid \beta\) then \(N(\alpha) \mid N(\beta)\).

Theorem. \(\mathbb{Z}[i]\) is a Euclidean domain with respect to \(N\).

Proof: given \(\alpha\) and \(\beta \ne 0\), compute the exact quotient \(\alpha/\beta = x + yi\) in \(\mathbb{C}\), with \(x, y \in \mathbb{Q}\). Round each coordinate to a nearest integer, \(m\) and \(n\), so \(|x - m| \le \frac12\) and \(|y - n| \le \frac12\), and set \(q = m + ni\), \(r = \alpha - q\beta\). Then \(r = \beta((x - m) + (y - n)i)\), so \(N(r) = N(\beta)((x - m)^2 + (y - n)^2) \le N(\beta)(\frac14 + \frac14) < N(\beta)\).

Geometrically, the multiples of \(\beta\) form a square lattice, rotated and scaled by \(\beta\), and every point of the plane lies within \(\frac{1}{\sqrt 2}|\beta|\) of a lattice point. This geometric argument also works for \(\mathbb{Z}[\sqrt{-2}]\), where the fundamental cells are rectangles with sides 1 and \(\sqrt 2\), but fails for \(\mathbb{Z}[\sqrt{-5}]\), whose cells are too long.

The Gaussian primes are determined by the rational primes. Up to associates they are: \(1 + i\), whose norm is 2; for each prime \(p \equiv 1 \pmod 4\), the two conjugate factors \(a \pm bi\) of \(p = a^2 + b^2\); and each prime \(p \equiv 3 \pmod 4\), which remains prime. For example \(5 = (2 + i)(2 - i)\), \(13 = (3 + 2i)(3 - 2i)\), and 3, 7, 11 stay prime. This contains Fermat's two-squares theorem: an odd prime is a sum of two squares exactly when it is \(1 \bmod 4\). Euler gave the first published proof of that theorem in the 1750s; the Gaussian integers make it a consequence of unique factorization.

Computing in the Gaussian integers

The program implements division with remainder by rounding the exact quotient, the Euclidean algorithm, and a search for Gaussian primes. It factors a few rational primes and computes a gcd. Complex numbers are represented as pairs of integers to keep the arithmetic exact; Python's cmath appears only as a cross-check of the norm.

import cmath

def mul(a, b):
    return (a[0] * b[0] - a[1] * b[1], a[0] * b[1] + a[1] * b[0])

def norm(a):
    return a[0] ** 2 + a[1] ** 2

def rdiv(n, d):                       # nearest integer to n/d
    return (2 * n + d) // (2 * d)

def gdivmod(a, b):
    nb = norm(b)
    num = mul(a, (b[0], -b[1]))       # a * conj(b)
    q = (rdiv(num[0], nb), rdiv(num[1], nb))
    qb = mul(q, b)
    return q, (a[0] - qb[0], a[1] - qb[1])

def ggcd(a, b):
    while b != (0, 0):
        a, b = b, gdivmod(a, b)[1]
    return a

def fmt(z):
    a, b = z
    return f"{a}{'+' if b >= 0 else '-'}{abs(b)}i"

a, b = (11, 3), (1, 8)
q, r = gdivmod(a, b)
print(f"{fmt(a)} = ({fmt(q)})({fmt(b)}) + ({fmt(r)}),  N(r) = {norm(r)} < N(b) = {norm(b)}")
print("gcd(11+3i, 1+8i) =", fmt(ggcd(a, b)))
print("cmath check of N(1+8i):", round(abs(complex(1, 8)) ** 2))

def is_rational_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))

def split(p):
    for x in range(1, int(p ** 0.5) + 1):
        y2 = p - x * x
        y = int(round(y2 ** 0.5))
        if y * y == y2 and y > 0:
            return f"{p} = ({x}+{y}i)({x}-{y}i)"
    return f"{p} stays prime"

for p in (2, 3, 5, 7, 13, 29, 31, 37):
    print(f"  p = {p} (mod 4 = {p % 4}):", split(p))

def gaussian_prime(z):
    a, b = abs(z[0]), abs(z[1])
    if a == 0 or b == 0:
        m = a + b
        return is_rational_prime(m) and m % 4 == 3
    return is_rational_prime(a * a + b * b)

count = sum(gaussian_prime((a, b)) for a in range(-6, 7) for b in range(-6, 7))
print("Gaussian primes with |a|, |b| <= 6:", count)

11+3i = (1-1i)(1+8i) + (2-4i),  N(r) = 20 < N(b) = 65
gcd(11+3i, 1+8i) = -1+2i
cmath check of N(1+8i): 65
  p = 2 (mod 4 = 2): 2 = (1+1i)(1-1i)
  p = 3 (mod 4 = 3): 3 stays prime
  p = 5 (mod 4 = 1): 5 = (1+2i)(1-2i)
  p = 7 (mod 4 = 3): 7 stays prime
  p = 13 (mod 4 = 1): 13 = (2+3i)(2-3i)
  p = 29 (mod 4 = 1): 29 = (2+5i)(2-5i)
  p = 31 (mod 4 = 3): 31 stays prime
  p = 37 (mod 4 = 1): 37 = (1+6i)(1-6i)
Gaussian primes with |a|, |b| <= 6: 64

The division step rounds \(\frac{11 + 3i}{1 + 8i} = \frac{(11 + 3i)(1 - 8i)}{65} = \frac{35 - 85i}{65}\) to \(1 - i\), leaving the remainder \(2 - 4i\) of norm 20, well below 65. The Euclidean algorithm then finishes in a few steps with the gcd \(-1 + 2i\), of norm 5; it divides both numbers, whose norms 130 and 65 are multiples of 5. The splitting pattern of the rational primes matches the rule: 2 ramifies as \(-i(1 + i)^2\), primes \(1 \bmod 4\) split into conjugates, and primes \(3 \bmod 4\) stay prime.

The same ideas apply to the Eisenstein integers \(\mathbb{Z}[\omega]\), where \(\omega = \frac{-1 + \sqrt{-3}}{2}\) is a primitive cube root of unity, with norm \(N(a + b\omega) = a^2 - ab + b^2\). Their multiples of a fixed element form a triangular lattice, and the rounding argument shows this ring is Euclidean as well. Its unique factorization is what makes Euler's treatment of Fermat's last theorem for exponent 3 work, once the gap in his argument is filled: in \(\mathbb{Z}[\omega]\), \(x^3 + y^3 = (x + y)(x + \omega y)(x + \omega^2y)\).

When unique factorization fails

In \(\mathbb{Z}[\sqrt{-5}]\), with norm \(N(a + b\sqrt{-5}) = a^2 + 5b^2\), the number 6 has two factorizations, \(6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})\). All four factors are irreducible: their norms are 4, 9, 6 and 6, and there is no element of norm 2 or 3, since \(a^2 + 5b^2 \in \{2, 3\}\) has no integer solution, so none of them splits further. And they are not associates, since the only units are \(\pm 1\). So \(\mathbb{Z}[\sqrt{-5}]\) is not a UFD, and therefore not a PID: the ideal \((2, 1 + \sqrt{-5})\) is not principal.

Dedekind's insight was that the ideals restore what the elements lose. With \(P = (2, 1 + \sqrt{-5})\), \(Q = (3, 1 + \sqrt{-5})\) and \(\bar Q = (3, 1 - \sqrt{-5})\), one checks that \((2) = P^2\), \((3) = Q\bar Q\), \((1 + \sqrt{-5}) = PQ\) and \((1 - \sqrt{-5}) = P\bar Q\). The two factorizations of 6 are two groupings of the same product of prime ideals, \(P^2Q\bar Q\). In every ring of algebraic integers, nonzero ideals factor uniquely into prime ideals; these rings are now called Dedekind domains.