Euclidean Domains, PIDs, and UFDs

An integral domain $R$ is a Euclidean domain if there exists a function $\delta : R \setminus \{0\} \to \mathbb{N}_0$ such that for all $a, b \in R$ with $b \neq 0$:

1. There exist $q, r \in R$ with $a = bq + r$ and either $r = 0$ or $\delta(r) \lt \delta(b)$.

Example. $\mathbb{Z}$ is a Euclidean domain with $\delta(a) = |a|$.

Example. $F[x]$ is a Euclidean domain with $\delta(f) = \deg(f)$.

Example. $\mathbb{Z}[i]$ is a Euclidean domain with $\delta(a + bi) = a^2 + b^2$.

Example. $\mathbb{Z}[\omega]$ (Eisenstein integers, $\omega = e^{2\pi i/3}$) is a Euclidean domain with $\delta(a + b\omega) = a^2 - ab + b^2$.

An integral domain $R$ is a principal ideal domain (PID) if every ideal of $R$ is principal (generated by a single element).

Theorem 11.1. Every Euclidean domain is a PID.

Proof. Let $I$ be a non-zero ideal of the Euclidean domain $R$. Choose $d \in I \setminus \{0\}$ Minimising $\delta(d)$. We claim $I = (d)$. For any $a \in I$Write $a = qd + r$ with $r = 0$ or $\delta(r) \lt \delta(d)$. Since $r = a - qd \in I$Minimality of $\delta(d)$ Forces $r = 0$So $a = qd \in (d)$. $\blacksquare$

Corollary 11.2. $\mathbb{Z}$, $F[x]$And $\mathbb{Z}[i]$ are PIDs.

An integral domain $R$ is a unique factorization domain (UFD) if:

1. Every non-zero, non-unit element factors into irreducibles.
2. The factorization is unique up to ordering and associates.

Theorem 11.3. Every PID is a UFD.

The chain of implications is:

$\mathrm{Euclidean\ domain} \Rightarrow \mathrm{PID} \Rightarrow \mathrm{UFD}$

None of the reverse implications hold .

Example. $\mathbb{Z}[x]$ is a UFD but not a PID. (The ideal $(2, x)$ is not principal.)

Example. $\mathbb{Z}[\sqrt{-5}]$ is not a UFD: $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ Gives two distinct factorizations into irreducibles.

Problem. Show that $\mathbb{Z}[\sqrt{-5}]$ is not a UFD.

$\mathrm{Fields} \subset \mathrm{Euclidean\ domains} \subset \mathrm{PIDs} \subset \mathrm{UFDs} \subset \mathrm{Integral\ domains}$

• Assuming every PID is Euclidean. $\mathbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a PID but not Euclidean, showing the inclusion is strict.
• Thinking $\mathbb{Z}[x]$ is a PID. The ideal $(2, x)$ is not principal because any generator would have to divide both $2$ and $x$, forcing it to be $\pm 1$, which generates the whole ring.
• Confusing irreducibles with primes in non-UFDs. In $\mathbb{Z}[\sqrt{-5}]$, $2$ is irreducible but not prime: $2 \mid (1+\sqrt{-5})(1-\sqrt{-5})$ but $2 \nmid (1\pm\sqrt{-5})$.
• Forgetting that units and associates do not affect uniqueness of factorisation. The factorisation $6 = 2 \cdot 3 = (-2) \cdot (-3)$ is considered the same up to associates.

• Number theory: The Euclidean algorithm in $\mathbb{Z}$ computes gcds and is the foundation of modular arithmetic and RSA cryptography.
• Coding theory: Polynomial rings over finite fields $F_q[x]$ are Euclidean domains, enabling BCH and Reed-Solomon error-correcting codes.
• Computer algebra: The Euclidean algorithm in $\mathbb{Z}[i]$ solves Diophantine equations and factors Gaussian integers, used in lattice-based cryptography.
• Algebraic geometry: UFDs guarantee that irreducible algebraic varieties have well-defined coordinate rings, enabling unique factorisation of polynomial ideals.

Problem 1. Determine whether $\mathbb{Z}[\sqrt{2}]$ is a Euclidean domain.

Solution. The norm is $N(a + b\sqrt{2}) = |a^2 - 2b^2|$. For any $\alpha, \beta \in \mathbb{Z}[\sqrt{2}]$ with $\beta \neq 0$, write $\alpha/\beta = u + v\sqrt{2}$ with $u,v \in \mathbb{Q}$. Choose integers $p,q$ such that $|u - p| \leq 1/2$ and $|v - q| \leq 1/2$. Then $r = \alpha - \beta(p + q\sqrt{2})$ satisfies $N(r) = |(u-p)^2 - 2(v-q)^2| \cdot N(\beta) \leq (1/4 + 2/4)N(\beta) = (3/4)N(\beta) < N(\beta)$. Thus $\mathbb{Z}[\sqrt{2}]$ is a Euclidean domain. $\blacksquare$

Problem 2. Is $\mathbb{Z}[x]$ a PID? Justify.

Solution. No. Consider the ideal $I = (2, x) = \{2f(x) + xg(x) : f,g \in \mathbb{Z}[x]\}$. If $I = (h(x))$, then $h(x) \mid 2$ and $h(x) \mid x$, so $h(x)$ divides any combination. Since $h \mid 2$, $h$ is constant: $\pm 1$ or $\pm 2$. If $h = \pm 2$, then $x \in (2)$ is impossible since $x$ has coefficient $1$ for $x$. If $h = \pm 1$, then $(h) = \mathbb{Z}[x]$, but $I$ contains only polynomials with even constant term, so $1 \notin I$. Thus $I$ is not principal. $\blacksquare$