Suppose you want to divide numbers. In $\mathbb{Z}$, when you divide $17$ by $5$ you get a remainder of $2$: that is, $17 = 3 \cdot 5 + 2$ with $|2| < |5|$. This remainder is strictly smaller in size than the divisor, and the process terminates. The same works in $k[x]$: dividing $x^3 + 1$ by $x^2 - x + 1$ yields a quotient and a remainder of degree strictly less than $2$. In both settings, the ability to divide with a "smaller" remainder drives virtually all of the arithmetic — the Euclidean algorithm, unique factorization, the structure of ideals, and Bezout's identity all flow from this single property. A Euclidean domain is the exact class of integral domains where this division-with-remainder process makes sense. The condition is deceptively simple: there must be a way to measure the "size" of elements so that remainders are always smaller than divisors. But this single requirement is enough to bootstrap an entire arithmetic, recovering the familiar theorems from $\mathbb{Z}$ in complete generality. [example: Division in the Gaussian Integers] The Gaussian integers $\mathbb{Z}[i] = \{a + bi : a, b \in \mathbb{Z}\}$ form a ring under ordinary complex addition and multiplication. Can we divide $11 + 3i$ by $2 + i$? Compute the complex quotient: \begin{align*} \frac{11 + 3i}{2 + i} &= \frac{(11 + 3i)(2 - i)}{(2 + i)(2 - i)} = \frac{22 - 11i + 6i - 3i^2}{4 + 1} = \frac{22 + 3 - 5i}{5} = \frac{25 - 5i}{5} = 5 - i. \end{align*} Here $5 - i \in \mathbb{Z}[i]$, so the division is exact and the remainder is zero. But suppose instead we divide $7 + 2i$ by $3 + i$: \begin{align*} \frac{7 + 2i}{3 + i} &= \frac{(7 + 2i)(3 - i)}{(3 + i)(3 - i)} = \frac{21 - 7i + 6i - 2i^2}{9 + 1} = \frac{21 + 2 - i}{10} = \frac{23}{10} - \frac{1}{10}i. \end{align*} This quotient is not in $\mathbb{Z}[i]$, so we round to the nearest Gaussian integer: the nearest to $\frac{23}{10} - \frac{1}{10}i$ is $2 - 0i = 2$. Setting $q = 2$, the remainder is: \begin{align*} r &= (7 + 2i) - 2(3 + i) = 7 + 2i - 6 - 2i = 1. \end{align*} We have $7 + 2i = 2 \cdot (3 + i) + 1$. The norm of the remainder is $|1|^2 = 1$, while the norm of the divisor is $|3 + i|^2 = 10$. The remainder is indeed smaller — this is the division algorithm working in $\mathbb{Z}[i]$. [/example] <!-- illustration-needed: the Gaussian integer rounding argument — show the complex plane with the lattice Z[i] as a grid of points; mark the exact complex quotient 23/10 - i/10 as a non-lattice point inside the unit square whose corners are the four nearest Gaussian integers 0, 1, -i, 1-i; indicate the chosen nearest lattice point q=2 and the remainder r=1 with a short arrow from the quotient to q; label N(r)=1 and N(divisor)=10 to illustrate that the remainder is strictly smaller in norm --> The key feature in this example is the norm: the function $N(a + bi) = a^2 + b^2$ measures "size," and rounding to the nearest Gaussian integer always produces a remainder of strictly smaller norm. This is the essence of the Euclidean domain axiom. ## Definition To define a Euclidean domain precisely, we need to capture what it means for division to work. The idea is to assign a non-negative integer to each nonzero element — think of it as an abstract notion of "size" or "degree" — such that the division algorithm produces remainders that are smaller. [definition: Euclidean Domain] An integral domain $R$ is a **Euclidean domain** if there exists a function \begin{align*} N: R \setminus \{0\} &\to \mathbb{Z}_{\ge 0} \end{align*} called a **Euclidean norm** (or Euclidean valuation) on $R$, satisfying: for every $a \in R$ and every $b \in R \setminus \{0\}$, there exist $q, r \in R$ such that \begin{align*} a &= bq + r \end{align*} and either $r = 0$ or $N(r) < N(b)$. [/definition] A few aspects of this definition deserve comment. First, the norm convention: [remark: On the Norm Convention] Some authors additionally require $N(a) \le N(ab)$ for all nonzero $a, b \in R$, which says multiplication does not decrease norms. This is a convenient property but it is not needed for the main theorems. The definition above is the minimal one: only the division property is required. Different Euclidean norms may exist on the same domain, and some of them may satisfy the multiplicativity condition while others do not. [/remark] Second, the hypothesis that $R$ is an integral domain is not cosmetic — it is essential: [explanation: Why the Domain Condition Matters] The hypothesis that $R$ is an integral domain — meaning $R$ is commutative, unital, and has no zero divisors — is essential. Without it, the arithmetic falls apart. In $\mathbb{Z}/6\mathbb{Z}$, for example, $2 \cdot 3 = 0$ with neither $2$ nor $3$ equal to zero. No Euclidean norm can exist here, because the factorization structure is hopelessly broken: a norm should somehow measure "size" compatibly with multiplication, but zero divisors destroy any coherent notion of size. The commutativity requirement (built into "integral domain") matters too: in noncommutative rings, one must distinguish left and right division, leading to a more complicated theory. Euclidean domains are the commutative setting where the classical story works cleanly. [/explanation] The standard examples one should have in mind immediately are: - $\mathbb{Z}$ with $N(n) = |n|$, - $k[x]$ for any field $k$, with $N(f) = \deg f$, - $\mathbb{Z}[i]$ with $N(a + bi) = a^2 + b^2$, - $\mathbb{Z}[\omega]$ where $\omega = e^{2\pi i/3}$, the Eisenstein integers, again with $N(a + b\omega) = a^2 - ab + b^2$. Each of these carries a natural geometric or combinatorial notion of size, and in each case the rounding argument shows the division algorithm works. [example: Polynomial Division over a Field] Let $k = \mathbb{Q}$ and divide $f = x^4 - 3x^2 + 2$ by $g = x^2 - 1$ in $\mathbb{Q}[x]$. Perform polynomial long division: \begin{align*} x^4 - 3x^2 + 2 &= (x^2 - 1)(x^2) + (-2x^2 + 2) \\ &= (x^2 - 1)(x^2) + (x^2 - 1)(-2) + 0 \\ &= (x^2 - 1)(x^2 - 2). \end{align*} The remainder is $0$, so $g \mid f$ in $\mathbb{Q}[x]$. Now divide $h = x^3 + x + 1$ by $g = x^2 + 1$: \begin{align*} x^3 + x + 1 &= (x^2 + 1)(x) + (0 \cdot x + 1) = (x^2 + 1)(x) + 1. \end{align*} The remainder is $1$, which has degree $-\infty$ (equivalently, degree $0 < 2 = \deg(x^2 + 1)$ if we adopt the convention $N(c) = 0$ for nonzero constants). The Euclidean norm $N(f) = \deg f$ satisfies $N(r) = 0 < 2 = N(g)$, confirming the division algorithm. Note that the leading coefficient of $g$ must be a unit in $k$ for this to work. In $\mathbb{Z}[x]$, we cannot always divide by polynomials with leading coefficient $> 1$: trying to divide $x$ by $2x - 1$ over $\mathbb{Z}$ fails since $x = (2x-1) \cdot \frac{1}{2} + \frac{1}{2}$ requires fractions. This is why $\mathbb{Z}[x]$ is **not** a Euclidean domain — the Euclidean norm breaks down for divisors with non-unit leading coefficients. [/example] ## The Euclidean Algorithm and the GCD The classical Euclidean algorithm for computing $\gcd(a, b)$ in $\mathbb{Z}$ works by repeatedly dividing and taking remainders: \begin{align*} a &= b q_1 + r_1, \quad N(r_1) < N(b), \\ b &= r_1 q_2 + r_2, \quad N(r_2) < N(r_1), \\ &\vdots \end{align*} until the remainder is zero. The last nonzero remainder is the $\gcd$. This procedure terminates because $N(r_1) > N(r_2) > \cdots \ge 0$ is a strictly decreasing sequence of non-negative integers. The same argument works verbatim in any Euclidean domain. Before making this precise, we need the relevant algebraic language. The word "divisibility" is something we use every day in $\mathbb{Z}$, but to work in an arbitrary ring we need to pin down exactly what it means: one element divides another if the second is a multiple of the first. The greatest common divisor is then the "largest" common divisor in the sense of divisibility — the one that all others divide into. [definition: Divisibility in a Ring] Let $R$ be a commutative ring and $a, b \in R$. We say $b$ **divides** $a$, written $b \mid a$, if there exists $c \in R$ with $a = bc$. An element $d \in R$ is a **greatest common divisor** of $a$ and $b$, written $d = \gcd(a, b)$, if: 1. $d \mid a$ and $d \mid b$, 2. if $e \mid a$ and $e \mid b$, then $e \mid d$. [/definition] Notice that condition 2 says $e \mid d$, not $d \ge e$ — divisibility, not magnitude, is the ordering. This means GCDs are not quite unique: [remark: GCDs Are Unique Up to Units] If $d$ and $d'$ are both greatest common divisors of $a$ and $b$ in an integral domain, then $d \mid d'$ and $d' \mid d$, which means $d = ud'$ for some unit $u \in R^\times$. So GCDs are unique up to multiplication by units. In $\mathbb{Z}$, we normalize by requiring $d > 0$; in $k[x]$, by requiring $d$ to be monic. [/remark] The GCD language is useful, but to understand the full ideal-theoretic content of the Euclidean algorithm we need to name the class of rings it reaches. When the Euclidean algorithm terminates, it shows that every ideal in the ring is generated by a single element. Rings with this property are called principal ideal domains, and they are the natural home of Bezout-style arithmetic. [definition: Principal Ideal Domain] An integral domain $R$ is a **principal ideal domain (PID)** if every ideal $I \trianglelefteq R$ is principal, i.e., of the form $I = (a) = \{ar : r \in R\}$ for some $a \in R$. [/definition] Why introduce PIDs here? Because Euclidean domains are precisely the domains where the Euclidean algorithm works, and the Euclidean algorithm is exactly the tool that shows every ideal is principal. This is the key structural theorem: [theorem: Every Euclidean Domain is a PID] Let $R$ be a Euclidean domain with norm $N$. Then $R$ is a principal ideal domain. Consequently, every two elements $a, b \in R$ (not both zero) have a greatest common divisor, and there exist $s, t \in R$ such that \begin{align*} \gcd(a, b) &= sa + tb. \end{align*} [/theorem] The equation $\gcd(a,b) = sa + tb$ deserves its own formal statement, since it is one of the most-used consequences of the Euclidean structure: [remark: Bezout's Identity] If $R$ is a Euclidean domain and $a, b \in R$ are not both zero, there exist $s, t \in R$ such that \begin{align*} \gcd(a, b) &= sa + tb. \end{align*} This is **Bezout's identity**. It is the algebraic statement that the ideal $(a, b) = (a) + (b)$ is already principal, generated by $\gcd(a, b)$. The coefficients $s$ and $t$ are found by back-substituting through the Euclidean algorithm. [/remark] [explanation: Why the Euclidean Algorithm Proves the PID Property] The argument is elegant. Let $I \trianglelefteq R$ be a nonzero ideal and pick $b \in I \setminus \{0\}$ with $N(b)$ minimal (which exists since $\mathbb{Z}_{\ge 0}$ is well-ordered). We claim $I = (b)$. The inclusion $(b) \subset I$ holds because $b \in I$ and $I$ is an ideal, so all multiples of $b$ are in $I$. For the reverse, take any $a \in I$. By the division algorithm, $a = bq + r$ with $r = 0$ or $N(r) < N(b)$. Since $a, b \in I$ and $I$ is an ideal, $r = a - bq \in I$. But $N(b)$ was minimal, so $N(r) < N(b)$ is impossible. Hence $r = 0$, so $a = bq \in (b)$. Thus $I = (b)$. Bezout's identity then follows because $\gcd(a, b) \in (a, b) = (\gcd(a, b))$, so we can write $\gcd(a, b) = sa + tb$ for some $s, t \in R$. The Euclidean algorithm computes this: run the algorithm to find $\gcd(a, b) = r_n$, then back-substitute through the chain of divisions to express $r_n$ as a linear combination of $a$ and $b$. [/explanation] To see the Euclidean algorithm and Bezout's identity in action beyond $\mathbb{Z}$, consider the following computation in $\mathbb{Z}[i]$: [example: Bezout's Identity in the Gaussian Integers] Find $\gcd(11 + 7i, 3 - 2i)$ in $\mathbb{Z}[i]$ and express it as a linear combination. Compute norms: $N(11 + 7i) = 121 + 49 = 170$, $N(3 - 2i) = 9 + 4 = 13$. Step 1: Divide $11 + 7i$ by $3 - 2i$. \begin{align*} \frac{11 + 7i}{3 - 2i} &= \frac{(11 + 7i)(3 + 2i)}{(3 - 2i)(3 + 2i)} = \frac{33 + 22i + 21i + 14i^2}{13} = \frac{33 - 14 + 43i}{13} = \frac{19 + 43i}{13}. \end{align*} So the exact quotient is $\frac{19}{13} + \frac{43}{13}i \approx 1.46 + 3.31i$. Round to the nearest Gaussian integer: $q_1 = 1 + 3i$. Remainder: $r_1 = (11 + 7i) - (1 + 3i)(3 - 2i)$. \begin{align*} (1 + 3i)(3 - 2i) &= 3 - 2i + 9i - 6i^2 = 3 + 6 + 7i = 9 + 7i. \end{align*} \begin{align*} r_1 &= (11 + 7i) - (9 + 7i) = 2. \end{align*} Now $N(r_1) = N(2) = 4 < 13 = N(3 - 2i)$, so we continue. Step 2: Divide $3 - 2i$ by $2$. \begin{align*} \frac{3 - 2i}{2} &= \frac{3}{2} - i. \end{align*} Round to the nearest Gaussian integer: $q_2 = 2 - i$. Remainder: \begin{align*} r_2 &= (3 - 2i) - 2(2 - i) = (3 - 2i) - (4 - 2i) = -1. \end{align*} Now $N(r_2) = N(-1) = 1 < 4 = N(2)$. Continue. Step 3: Divide $2$ by $-1$: \begin{align*} 2 &= (-1)(-2) + 0. \end{align*} Remainder is $0$. The last nonzero remainder is $r_2 = -1$, so $\gcd(11 + 7i, 3 - 2i) = -1$, which is a unit. Therefore $11 + 7i$ and $3 - 2i$ are **coprime** in $\mathbb{Z}[i]$. Now back-substitute to express $-1$ as a linear combination. From Step 2: \begin{align*} -1 &= (3 - 2i) - 2 \cdot (2 - i). \end{align*} From Step 1, $2 = (11 + 7i) - (1 + 3i)(3 - 2i)$. Substituting: \begin{align*} -1 &= (3 - 2i) - \bigl[(11 + 7i) - (1 + 3i)(3 - 2i)\bigr](2 - i) \\ &= (3 - 2i) - (2 - i)(11 + 7i) + (2 - i)(1 + 3i)(3 - 2i) \\ &= \bigl[1 + (2 - i)(1 + 3i)\bigr](3 - 2i) + (-(2 - i))(11 + 7i). \end{align*} Compute the coefficients: $(2 - i)(1 + 3i) = 2 + 6i - i - 3i^2 = 2 + 5i + 3 = 5 + 5i$, so $1 + (2 - i)(1 + 3i) = 6 + 5i$ and $-(2 - i) = -2 + i$. Thus: \begin{align*} -1 &= (6 + 5i)(3 - 2i) + (-2 + i)(11 + 7i). \end{align*} Verify: $(6 + 5i)(3 - 2i) = 18 - 12i + 15i - 10i^2 = 18 + 10 + 3i = 28 + 3i$. And $(-2 + i)(11 + 7i) = -22 - 14i + 11i + 7i^2 = -22 - 7 - 3i = -29 - 3i$. Sum: $(28 + 3i) + (-29 - 3i) = -1$. The identity is confirmed. [/example] ## Unique Factorization One of the deepest consequences of having a Euclidean structure is unique factorization. In $\mathbb{Z}$, every integer greater than $1$ factors uniquely as a product of primes — this is the Fundamental Theorem of Arithmetic. The same holds in any Euclidean domain, and the proof proceeds through the PID structure. The key observation is that in a PID, the notions of irreducible and prime elements coincide. These two concepts, which in general integral domains can diverge dramatically, are brought into alignment by the principal ideal structure. To see why this matters — and why the distinction is real in the absence of the PID property — we need to state both definitions carefully. [definition: Irreducible and Prime Elements] Let $R$ be an integral domain and $p \in R$ with $p \ne 0$ and $p \notin R^\times$. - $p$ is **irreducible** if whenever $p = ab$ for $a, b \in R$, either $a \in R^\times$ or $b \in R^\times$. - $p$ is **prime** if whenever $p \mid ab$ for $a, b \in R$, either $p \mid a$ or $p \mid b$. [/definition] In familiar territory like $\mathbb{Z}$, there is no difference between these notions — but in general, primality is strictly stronger than irreducibility. The following example shows exactly where the gap lies: [explanation: The Difference Between Irreducible and Prime] In $\mathbb{Z}$, the number $5$ is both irreducible (it cannot be factored as a product of two non-units) and prime ($5 \mid ab$ implies $5 \mid a$ or $5 \mid b$). For general integral domains, however, these concepts diverge. Consider the ring $R = \mathbb{Z}[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b \in \mathbb{Z}\}$. The element $3$ is irreducible: if $3 = (a + b\sqrt{-5})(c + d\sqrt{-5})$, taking norms gives $9 = (a^2 + 5b^2)(c^2 + 5d^2)$, and the only solutions with both factors greater than $1$ require $a^2 + 5b^2 = 3$, which has no integer solutions. But $3$ is not prime: we have $3 \mid 9 = (2 + \sqrt{-5})(2 - \sqrt{-5})$, yet $3 \nmid (2 + \sqrt{-5})$ and $3 \nmid (2 - \sqrt{-5})$ in $R$. The failure of $3$ to be prime in $\mathbb{Z}[\sqrt{-5}]$ is exactly why factorization fails to be unique: $9 = 3 \cdot 3 = (2 + \sqrt{-5})(2 - \sqrt{-5})$ gives two genuinely different factorizations into irreducibles. And crucially, $\mathbb{Z}[\sqrt{-5}]$ is not a Euclidean domain (nor even a PID). In a PID — and hence in any Euclidean domain — irreducibles are always prime, and this is what forces unique factorization. [/explanation] Since irreducibles are always prime in a PID, and every Euclidean domain is a PID, the full factorization theorem follows: [theorem: Euclidean Domains Are Unique Factorization Domains] Every Euclidean domain is a unique factorization domain (UFD). That is, every nonzero non-unit element $a \in R$ can be written as \begin{align*} a &= p_1 p_2 \cdots p_k \end{align*} where each $p_i$ is irreducible, and this factorization is unique up to reordering and multiplication of each factor by a unit. [/theorem] The proof goes through the PID property: one shows first that every PID satisfies the ascending chain condition on principal ideals (which gives existence of factorizations), then that irreducibles are prime in a PID (which gives uniqueness). Since Euclidean domains are PIDs, the conclusion follows. [example: Factorization in the Gaussian Integers] Factor $10 \in \mathbb{Z}[i]$. In $\mathbb{Z}$, $10 = 2 \cdot 5$. But in $\mathbb{Z}[i]$, both $2$ and $5$ factor further. We have $2 = (1 + i)(1 - i)$, and $N(1 + i) = 2$, which is prime in $\mathbb{Z}$, so $1 + i$ has no non-trivial factorization in $\mathbb{Z}[i]$ — it is irreducible. Similarly $1 - i = \overline{(1+i)}$. Note $1 - i = -i(1 + i)$, so $1 - i$ and $1 + i$ are associates (they differ by the unit $-i$). For $5$: $5 = (2 + i)(2 - i)$, and $N(2 + i) = 5$, which is prime in $\mathbb{Z}$, so $2 + i$ is irreducible in $\mathbb{Z}[i]$. Therefore: \begin{align*} 10 &= 2 \cdot 5 = (1 + i)(1 - i)(2 + i)(2 - i). \end{align*} This is the unique factorization of $10$ into irreducibles in $\mathbb{Z}[i]$ (up to units and ordering). The rational prime $2$ splits as $(1+i)(1-i)$, while the rational prime $5$ splits as $(2+i)(2-i)$. The prime $3$, by contrast, remains irreducible in $\mathbb{Z}[i]$: $N(\alpha) = 3$ would require $a^2 + b^2 = 3$, which has no integer solutions, so no element of norm $3$ exists. [/example] ## Ideals and the Structure Theorem In a Euclidean domain, the ideal structure is completely transparent: every ideal is principal. This has a remarkable consequence for the quotient rings $R / (a)$ — they can be classified explicitly. Before stating the classification theorem, we need to name a basic equivalence relation that appears throughout the theory. Two elements that differ only by a unit — for instance $5$ and $-5$ in $\mathbb{Z}$, or $x^2 + 1$ and $3(x^2 + 1)$ in $\mathbb{Q}[x]$ — generate the same ideal and behave identically for all arithmetic purposes. Giving them a name makes it possible to state uniqueness cleanly: unique factorization is unique up to associates. [definition: Associate Elements] Two elements $a, b$ in an integral domain $R$ are **associates** if $a = ub$ for some unit $u \in R^\times$. [/definition] Equivalently, $(a) = (b)$ as ideals. We write $a \sim b$ for this relation. The associate relation is an equivalence relation, and unique factorization in a UFD is really unique up to these equivalence classes. When working in $\mathbb{Z}$, we pick the positive representative of each associate class; in $k[x]$, we pick monic polynomials. [theorem: Classification of Ideals in a Euclidean Domain] Let $R$ be a Euclidean domain. Every ideal $I$ of $R$ is of the form $I = (a)$ for a unique associate class of elements $a \in R$ (with $I = (0)$ corresponding to $a = 0$). In particular: 1. The maximal ideals of $R$ are exactly the ideals $(p)$ where $p$ is irreducible. 2. The prime ideals of $R$ are $(0)$ and the maximal ideals. 3. Every ideal $(a)$ contains $(b)$ if and only if $a \mid b$. [/theorem] The interplay between ideals and divisibility in a PID is worth spelling out, because it makes the ideal lattice completely explicit: [explanation: The Hierarchy of Ideal Containment] In a PID, ideal containment reverses divisibility: $(a) \supset (b)$ means $(a) \ni b$, i.e., $a \mid b$. So larger ideals correspond to "smaller" elements in the divisibility order. The zero ideal $(0)$ is the smallest ideal (contained in all others) and corresponds to the "largest" element — $0$, which is divisible by everything. The maximal ideals are the "atoms" of the ideal lattice, corresponding to irreducible elements. In $\mathbb{Z}$, these are $(2), (3), (5), (7), \ldots$ — the prime ideals. In $k[x]$, they are the ideals generated by irreducible polynomials. The quotient $R/(p)$ by a maximal ideal is a field: in $\mathbb{Z}$ this gives $\mathbb{Z}/p\mathbb{Z}$, and in $k[x]$ this gives a field extension of $k$. [/explanation] This ideal structure has concrete consequences for quotient rings. Since $(p)$ is maximal whenever $p$ is irreducible, the quotient $R/(p)$ is always a field — and in specific examples, we can compute exactly which field: [example: Quotient Rings of Euclidean Domains] Consider $\mathbb{Z}[i] / (1 + i)$. We have $N(1 + i) = 2$, so $(1 + i)$ is a maximal ideal and $\mathbb{Z}[i]/(1+i)$ is a field. What field? Every element of $\mathbb{Z}[i]$ reduces modulo $1 + i$. Since $i \equiv -1 \pmod{1+i}$ (because $i - (-1) = i + 1 = 1 + i$), every element $a + bi \equiv a + b(-1) = a - b \pmod{1+i}$. This is an integer. Moreover, $2 = (1+i)(1-i) \in (1+i)$, so $2 \equiv 0$. Therefore every element reduces to either $0$ or $1$ modulo $(1+i)$, giving: \begin{align*} \mathbb{Z}[i] / (1 + i) \cong \mathbb{Z}/2\mathbb{Z} = \mathbb{F}_2. \end{align*} Now consider $\mathbb{Z}[i]/(2 + i)$. Since $N(2+i) = 5$, the quotient is a field of order $5$, i.e., $\mathbb{F}_5$. Indeed, $i \equiv -2 \pmod{2+i}$ (since $i - (-2) = i + 2 = 2 + i$), and every $a + bi \equiv a - 2b \pmod{5}$, giving a surjection $\mathbb{Z}[i] \to \mathbb{Z}/5\mathbb{Z}$ with kernel $(2+i)$. [/example] ## The Norm and Arithmetic of Units The Euclidean norm also controls which elements are units. In $\mathbb{Z}[i]$, the units are exactly the elements of norm $1$: $\{\pm 1, \pm i\}$. In $k[x]$, the units are the nonzero constants, and the Euclidean norm (degree) satisfies $N(u) = 0$ for all units. This is not a coincidence. [theorem: Units and the Euclidean Norm] Let $R$ be a Euclidean domain with norm $N$. If $N$ additionally satisfies $N(ab) \ge N(a)$ for all nonzero $a, b \in R$ (that is, $N$ is submultiplicative from below), then an element $u \in R$ is a unit if and only if $N(u) = N(1_R)$. [/theorem] The proof relies on the submultiplicativity assumption, which the standard norms on $\mathbb{Z}$, $k[x]$, and $\mathbb{Z}[i]$ all satisfy: [explanation: Why Units Have Minimal Norm] If $u$ is a unit, then $u \cdot u^{-1} = 1$, and the norm condition gives $N(1) = N(u \cdot u^{-1}) \ge N(u)$ and $N(u) = N(1 \cdot u) \ge N(1)$. So $N(u) = N(1)$. Conversely, if $N(u) = N(1)$, write $1 = uq + r$ with $r = 0$ or $N(r) < N(u) = N(1)$. If $r \ne 0$, then writing $r = 1 - uq$ and applying the norm condition carefully leads to a contradiction (in rings where $N$ is well-behaved). For the standard norms on $\mathbb{Z}$ and $\mathbb{Z}[i]$, $N = 1$ forces $u \in \{\pm 1\}$ and $u \in \{\pm 1, \pm i\}$ respectively, and these are exactly the units. [/explanation] The Eisenstein integers provide a beautiful illustration of this principle, where the unit group turns out to be the sixth roots of unity: [example: Units in the Eisenstein Integers] The Eisenstein integers are $\mathbb{Z}[\omega]$ where $\omega = e^{2\pi i/3} = -\frac{1}{2} + \frac{\sqrt{3}}{2}i$. This is a Euclidean domain with norm $N(a + b\omega) = a^2 - ab + b^2$. The units are the elements with $N = 1$: \begin{align*} a^2 - ab + b^2 &= 1. \end{align*} Completing the square: $a^2 - ab + b^2 = (a - b/2)^2 + 3b^2/4$. For this to equal $1$ with integer $a, b$, we need $3b^2/4 \le 1$, so $b^2 \le 4/3$, giving $b \in \{-1, 0, 1\}$. - $b = 0$: $a^2 = 1$, so $a = \pm 1$. - $b = 1$: $a^2 - a + 1 = 1$, so $a(a-1) = 0$, giving $a \in \{0, 1\}$. - $b = -1$: $a^2 + a + 1 = 1$, so $a(a+1) = 0$, giving $a \in \{0, -1\}$. The six units are $\pm 1$, $\pm \omega$, $\pm \omega^2$ (since $\omega^2 = -1 - \omega$ in $\mathbb{Z}[\omega]$, corresponding to $(a,b) = (-1, -1)$, and indeed $N(-1 - \omega) = (-1)^2 - (-1)(-1) + (-1)^2 = 1 - 1 + 1 = 1$). So the Eisenstein integers have exactly $6$ units, matching the $6$ sixth roots of unity. [/example] ## Non-Examples and the Boundaries of the Theory Understanding what fails to be a Euclidean domain is as illuminating as the positive examples. The most instructive cases are rings that are PIDs but not Euclidean, and rings that fail to be PIDs at all. The class of rings strictly between Euclidean domains and arbitrary integral domains is not empty: there exist PIDs that are not Euclidean. [theorem: A PID That Is Not Euclidean] The ring $\mathbb{Z}\!\left[\frac{1 + \sqrt{-19}}{2}\right]$ is a principal ideal domain but is not a Euclidean domain with respect to any norm. In particular, the implications \begin{align*} \text{Euclidean domain} &\implies \text{PID} \implies \text{UFD} \end{align*} are strict. [/theorem] The first implication was proved above. The strictness of the second — that not every UFD is a PID — will appear in the non-example below. For the first, the ring $\mathbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is the standard example: its proof requires techniques from algebraic number theory (specifically, computing the class number). The strictness of the chain is also visible in the factorization failures that arise when we leave the Euclidean world: [explanation: Why $\mathbb{Z}[\sqrt{-5}]$ Fails to Be a UFD] We already saw that $9 = 3 \cdot 3 = (2 + \sqrt{-5})(2 - \sqrt{-5})$ gives two factorizations in $\mathbb{Z}[\sqrt{-5}]$. Since UFD implies PID implies Euclidean (in reverse), the failure of unique factorization shows $\mathbb{Z}[\sqrt{-5}]$ is not a UFD, not a PID, and not Euclidean — all at once. Checking that $3$ and $2 \pm \sqrt{-5}$ are irreducible: $N(a + b\sqrt{-5}) = a^2 + 5b^2$. The norm is multiplicative: $N(\alpha \beta) = N(\alpha)N(\beta)$. So $N(3) = 9$, and a factorization $3 = \alpha\beta$ requires $N(\alpha)N(\beta) = 9$. The possible values of $a^2 + 5b^2$ are $1, 4, 5, 6, 9, \ldots$ — but $3$ is not achieved (since $a^2 + 5b^2 = 3$ has no integer solution: $b = 0$ gives $a^2 = 3$, impossible; $|b| \ge 1$ gives $5b^2 \ge 5 > 3$). So neither factor can have norm $3$, and both must have norm $1$ or $9$ — one is a unit and one has norm $9$. This shows $3$ is irreducible. Now consider $2 + \sqrt{-5}$. Its norm is $N(2 + \sqrt{-5}) = 2^2 + 5 \cdot 1^2 = 9$. A factorization $2 + \sqrt{-5} = \alpha\beta$ requires $N(\alpha)N(\beta) = 9$, so the norms are either $(1, 9)$ or $(3, 3)$. The $(1,9)$ case means one factor is a unit, so the factorization is trivial. For the $(3, 3)$ case, we would need an element $\alpha = a + b\sqrt{-5} \in \mathbb{Z}[\sqrt{-5}]$ with $N(\alpha) = a^2 + 5b^2 = 3$. But $b = 0$ gives $a^2 = 3$, which has no integer solution, and $|b| \ge 1$ gives $a^2 + 5b^2 \ge 5 > 3$. So no element of norm $3$ exists in $\mathbb{Z}[\sqrt{-5}]$, and the $(3,3)$ case is impossible. Hence $2 + \sqrt{-5}$ is irreducible, and by the same computation so is $2 - \sqrt{-5}$ (since $N(2 - \sqrt{-5}) = 4 + 5 = 9$ as well). With two distinct factorizations of $9$ into irreducibles, the ring $\mathbb{Z}[\sqrt{-5}]$ is definitively not a UFD. [/explanation] At the other end of the spectrum, a ring can be a UFD without being a PID — and therefore without being Euclidean. The polynomial ring $\mathbb{Z}[x]$ is the standard example: [example: Why $\mathbb{Z}[x]$ Is Not a Euclidean Domain] The ring $\mathbb{Z}[x]$ is a UFD (by Gauss's theorem) but not a PID, and therefore not Euclidean. The ideal $(2, x) = \{2f + xg : f, g \in \mathbb{Z}[x]\}$ is not principal: if $(2, x) = (h)$ for some $h \in \mathbb{Z}[x]$, then $h \mid 2$ (so $h$ is a constant $\pm 1$ or $\pm 2$) and $h \mid x$ (so $h = \pm 1$). But $(1) = \mathbb{Z}[x] \ne (2, x)$ — the ideal $(2, x)$ consists of polynomials whose constant term is even, and $1 \notin (2,x)$ since $2f(0) + x \cdot g(0)|_{x=0} = 2f(0)$ is always even. This contradiction shows $(2, x)$ is not principal. Hence $\mathbb{Z}[x]$ is not a PID and cannot be Euclidean. [/example] ## References - David S. Dummit and Richard M. Foote, *Abstract Algebra* (3rd ed., 2004). - Serge Lang, *Algebra* (3rd ed., 2002). - Michael Artin, *Algebra* (2nd ed., 2011). - Harold M. Edwards, *Essays in Constructive Mathematics* (2005). - Pierre Samuel, "About Euclidean Rings," *Journal of Algebra* (1971).