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

flowchart TD
    A[11_Euclidean Domains Pids And Ufds] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

The hierarchy Euclidean domain, PID, UFD captures a fundamental question: how well does division work in a ring? A Euclidean domain lets you divide with remainder, like the integers, and this guarantees every ideal is principal and every element factors uniquely. A PID drops the division algorithm but keeps the consequence: every ideal is generated by a single element. A UFD only requires unique factorisation into irreducibles, the weakest condition that still gives meaningful arithmetic. The classic failure, Z[square root of -5], shows that without unique factorisation, even basic number theory breaks down.

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

• Polynomial Rings — The polynomial ring $F[x]$ is a key example of a Euclidean domain; irreducibility in $F[x]$ connects to the UFD structure here.

• Worked Examples — The worked examples use Euclidean division and factorisation arguments that depend on the ring classifications in this chapter.

• Common Pitfalls — The pitfalls section warns against confusing irreducibility with primality and assuming PIDs are always Euclidean.

• Classical Mechanics

• Electromagnetism

This section provides detailed coverage of advanced concepts, including full derivations, proofs, and extended examples.

Complete mathematical derivations and proofs are provided where appropriate. Each step is explained to ensure understanding of the underlying reasoning.

Advanced examples demonstrate the application of concepts to complex problems. These examples go beyond standard exam questions to develop deeper understanding.

This material connects to current research and advanced applications in the field. Understanding these connections provides context for the study material.

Ensure you have mastered the prerequisite material before attempting this advanced content.