Euclidean domain

A Euclidean domain is an integral domain R equipped with a function d: R \setminus \{0\} \to \mathbb{N} \cup \{0\}, called a Euclidean function or norm, satisfying two properties: for all nonzero a, b \in R, d(a) \leq d(ab), and for all a, b \in R with b \neq 0, there exist q, r \in R such that a = bq + r where either r = 0 or d(r) < d(b).^[1] This structure generalizes the division algorithm from the integers \mathbb{Z} and polynomial rings, enabling the Euclidean algorithm for computing greatest common divisors.^[2] Every Euclidean domain is a principal ideal domain (PID), meaning every ideal is generated by a single element, and thus also a unique factorization domain (UFD), where every nonzero nonunit element factors uniquely into irreducibles up to units and order.^[1] The Euclidean function measures "size" in a way that ensures remainders decrease, facilitating proofs of these properties via the well-ordering principle on the image of d.^[3] Notable examples include the ring of integers \mathbb{Z} with d(n) = |n|, the polynomial ring F over a field F with d(f) = \deg f, and the Gaussian integers \mathbb{Z} with d(a + bi) = a^2 + b^2.^[2] Other quadratic integer rings, such as \mathbb{Z}[\sqrt{-2}], are also Euclidean under suitable norms, though not all PIDs are Euclidean.^[1]

Definition and Core Concepts

Formal Definition

A Euclidean domain is an integral domain equipped with a Euclidean function that satisfies a division algorithm property. An integral domain is a commutative ring with multiplicative identity and no zero divisors.^[1] Formally, let R be an integral domain. A function f: R \setminus \{0\} \to \mathbb{N} \cup \{0\} is a Euclidean function on R if for every a, b \in R with b \neq 0, there exist q, r \in R such that

a = bq + r

where either r = 0 or f(r) < f(b). The pair (R, f) is then called a Euclidean domain.^[1] Some definitions of Euclidean domain additionally require that the Euclidean function f satisfy the inequality f(a) \leq f(ab) for all nonzero a, b \in R. This multiplicativity condition, while convenient for certain proofs such as factorization into irreducibles without relying on abstract methods, is not essential for establishing that every ideal in a Euclidean domain is principal or that the Euclidean algorithm terminates to compute greatest common divisors.^[1]

Euclidean Function

In a Euclidean domain R, the Euclidean function f is a map from the nonzero elements R \setminus \{0\} to the non-negative integers \mathbb{N}_0, assigning to each nonzero element a measure of "size" that facilitates a division algorithm analogous to that in the integers.^[1] This function must satisfy the key division property: for any a, b \in R with b \neq 0, there exist q, r \in R such that a = bq + r and either r = 0 or f(r) < f(b).^[1] The strict inequality f(r) < f(b) ensures that repeated applications of the division process terminate, preventing infinite descending chains of remainders, much like the Euclidean algorithm in \mathbb{Z}.^[4] The function is undefined on zero because division by zero is meaningless in the ring, and zero lacks a positive size that would fit the ordering required for the algorithm; including it could violate the strict decrease in remainders.^[1] A single Euclidean domain may admit multiple distinct Euclidean functions, highlighting the flexibility of the concept. For example, in the integers [\mathbb{Z}](/page/Z), both f(n) = [|n|](/page/Absolute_value) and f(n) = n^2 qualify as Euclidean functions.^[1] The absolute value function works straightforwardly, as remainders satisfy |r| < |b|, but the squaring function also succeeds because if |r| < |b|, then r^2 < b^2 holds for |b| \geq 2, and when |b| = 1 (a unit), the remainder must be zero to avoid a nonzero r with f(r) = 1 = f(b).^[1] Weaker functions, such as those that are less refined in measuring size, can still qualify a domain as Euclidean so long as the strict inequality in the division condition is met, though stronger functions like norms often provide additional algebraic benefits.^[4] The Euclidean function induces a partial order on the nonzero elements of R, typically through an additional property that f(a) \leq f(ab) for all nonzero a, b \in R, which ensures that multiplication by nonzero elements does not decrease the size.^[1] This ordering makes the nonzero elements of R "well-structured" for division, as units achieve the minimal value f(u) = f(1), and there are no infinite strictly decreasing sequences under f, guaranteeing termination in algorithmic processes.^[1] Such a structure positions R as well-ordered in a divisibility sense, underpinning its Euclidean nature without requiring a total order like the natural numbers.^[4]

Examples

Classical Euclidean Domains

The ring of integers \mathbb{Z} is the prototypical example of a Euclidean domain, equipped with the Euclidean function f(n) = |n| for n \neq 0.^[1]^[5] For any a, b \in \mathbb{Z} with b \neq 0, the division algorithm guarantees unique integers q and r such that a = bq + r and $0 \leq r < |b|, ensuring f(r) < f(b) if r \neq 0.^[1] This structure underpins the classical Euclidean algorithm for computing greatest common divisors.^[5] Polynomial rings F over any field F form another fundamental class of Euclidean domains, using the Euclidean function f(p) = \deg(p) for nonzero polynomials p \in F.^[1]^[5] The division algorithm here states that for a, b \in F with b \neq 0, there exist unique q, r \in F such that a = bq + r and either r = 0 or \deg(r) < \deg(b); uniqueness relies on normalizing leading coefficients to 1 in F, which is possible since F is a field.^[1] The ring of Gaussian integers \mathbb{Z} = \{a + bi \mid a, b \in \mathbb{Z}\} is a Euclidean domain with the Euclidean function f(\alpha) = N(\alpha) = a^2 + b^2 for \alpha = a + bi \neq 0, where N is the multiplicative norm.^[1]^[6]^[5] For \alpha, \beta \in \mathbb{Z} with \beta \neq 0, division proceeds by computing the complex quotient \alpha / \beta and selecting q \in \mathbb{Z} as the Gaussian integer closest to this value (rounding real and imaginary parts to nearest integers), yielding r = \alpha - \beta q with either r = 0 or N(r) < N(\beta); this ensures the remainder norm is at most half the divisor norm.^[6] All fields are trivially Euclidean domains, as one can define f(x) = 1 (or any constant) for all nonzero x, since division yields exact quotients with zero remainder.^[1]

Advanced and Non-Standard Examples

The Eisenstein integers form the ring \mathbb{Z}[\omega], where \omega is a primitive cube root of unity satisfying \omega^2 + \omega + 1 = 0. This ring is an integral domain equipped with the Euclidean function f(a + b\omega) = a^2 - ab + b^2 for a, b \in \mathbb{Z}, which corresponds to the square of the usual complex modulus and satisfies the necessary properties for the division algorithm.^[7] As a result, \mathbb{Z}[\omega] admits unique factorization into irreducibles, extending the arithmetic of rational integers to this cyclotomic setting.^[8] The ring of formal power series k[] over a field k provides another advanced example, where elements are infinite series \sum_{n=0}^\infty a_n x^n with a_n \in k. It is Euclidean with respect to the function f(P) = the order of P, defined as the smallest integer n such that the coefficient of x^n in P is nonzero (and f(0) = \infty). This valuation-based function ensures that for any nonzero P, Q \in k[], there exist R, S \in k[] such that P = QR + S with either S = 0 or f(S) < f(Q), mirroring the degree function in polynomial rings but adapted to infinite expansions.^[9] Such rings are crucial in algebraic geometry and p-adic analysis, where they model completions of local rings. For a non-standard quadratic example, the ring of integers \mathbb{Z}\left[\frac{1 + \sqrt{69}}{2}\right] in \mathbb{Q}(\sqrt{69}) is Euclidean but relies on a specific non-norm Euclidean function constructed in the proof, ensuring the division property holds although the usual field norm does not. This was the first confirmed instance of a principal ideal domain that is Euclidean without admitting the usual norm as its function, resolving long-standing questions in algebraic number theory.^[10] As a non-example, the ring \mathbb{Z}[\sqrt{-5}] is an integral domain but fails to be a principal ideal domain, as the ideal generated by 2 and $1 + \sqrt{-5} is non-principal, and it lacks unique factorization since $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}) with the factors irreducible and non-associate. Consequently, it cannot be Euclidean.^[1]

Algebraic Properties

Division Algorithm and GCD Computation

In a Euclidean domain R equipped with a Euclidean function f: R \setminus \{0\} \to \mathbb{N} \cup \{0\}, the division algorithm states that for any a, b \in R with b \neq 0, there exist q, r \in R such that a = bq + r and either r = 0 or f(r) < f(b).^[1] The quotient q is typically chosen to minimize f(r), ensuring the remainder is "smaller" than the divisor under the function f.^[11] For example, in the integers \mathbb{Z} with f(n) = |n|, this recovers the standard division where $0 \leq r < |b|.^[12] The Euclidean algorithm generalizes to any Euclidean domain by iteratively applying the division algorithm to compute the greatest common divisor (GCD) of two elements a, b \in R with b \neq 0: replace a with b and b with the remainder r, yielding \gcd(a, b) = \gcd(b, r), and continue until the remainder is zero, at which point the last non-zero remainder is a GCD of a and b.^[1] This process terminates in finitely many steps because the sequence of remainders produces strictly decreasing values under f, and \mathbb{N} \cup \{0\} is well-ordered.^[11] The GCD d in a Euclidean domain is unique up to multiplication by units of R, meaning if d' is another GCD, then d = ud' for some unit u \in R^\times.^[12] An extended version of the Euclidean algorithm back-substitutes through the division steps to express the GCD as a linear combination: there exist s, t \in R such that d = sa + tb, known as Bézout coefficients. This follows directly from the iterative divisions, where each remainder is rewritten in terms of the previous pair.^[12] Euclidean domains support efficient GCD computation due to the finite termination guaranteed by the decreasing Euclidean function, making them ideal for algorithmic applications in computer algebra systems, where operations like polynomial GCDs or integer factorization rely on these steps for polynomial-time performance in many cases.^[1] In such contexts, every non-zero element admits a content (GCD with a fixed basis) or primitive part (quotient by content), facilitating normalization in computations.^[11]

Relation to Principal Ideal Domains and Unique Factorization

A fundamental property of Euclidean domains is that they are principal ideal domains (PIDs). To see this, consider a Euclidean domain R with Euclidean function f: R \setminus \{0\} \to \mathbb{N} \cup \{0\}. Let I be a nonzero ideal in R. Among the nonzero elements of I, select b \in I such that f(b) is minimal. For any a \in I, apply the division algorithm: a = qb + r with either r = 0 or f(r) < f(b). Since r = a - qb \in I and f(b) is minimal, it follows that r = 0, so a \in (b). Thus, I = (b), proving R is a PID.^[1] Every PID is a unique factorization domain (UFD), meaning every nonzero nonunit element factors into irreducibles uniquely up to order and units. In a PID R, the existence of factorization follows from the ascending chain condition on principal ideals, and uniqueness arises because if a = p_1 \cdots p_m = q_1 \cdots q_n with irreducibles p_i, q_j, then each p_i divides some q_j, implying equality up to units by prime element properties in PIDs. Therefore, every Euclidean domain is a UFD.^[13] In any Euclidean domain R that is not a field, there exists a universal side divisor: a nonunit d \in R such that for every x \in R, there is y \in R with x = dy + u where u is a unit or zero. To construct such a d, take a nonunit of minimal f-value; the division algorithm then ensures it divides every element up to units.^[1] The converse—that every PID is Euclidean—does not hold, as shown by T. Motzkin in 1949, who constructed principal ideal rings without a Euclidean algorithm. A concrete example is the ring of integers \mathbb{Z}\left[\frac{1 + \sqrt{-19}}{2}\right] in \mathbb{Q}(\sqrt{-19}), which is a PID but not Euclidean with respect to any norm.^[14]

Special Classes and Characterizations

Norm-Euclidean Domains

A norm-Euclidean domain is an integral domain equipped with a Euclidean function derived from the absolute value of the field norm, specifically where the function f(\alpha) = |N_{K/\mathbb{Q}}(\alpha)| for \alpha in the ring of integers \mathcal{O}_K of a number field K, and N_{K/\mathbb{Q}} denotes the field norm.^[15] The field norm N_{K/\mathbb{Q}}(\alpha) is defined as the determinant of the \mathbb{Q}-linear multiplication-by-\alpha map on K viewed as a vector space over \mathbb{Q}.^[16] For this function to serve as a Euclidean norm, the division algorithm must hold: for any a, b \in \mathcal{O}_K with b \neq 0, there exist q, r \in \mathcal{O}_K such that a = bq + r and either r = 0 or |N_{K/\mathbb{Q}}(r)| < |N_{K/\mathbb{Q}}(b)|.^[1] The field norm possesses key multiplicative properties that facilitate its use as a Euclidean function: specifically, N_{K/\mathbb{Q}}(\alpha \beta) = N_{K/\mathbb{Q}}(\alpha) N_{K/\mathbb{Q}}(\beta) for all \alpha, \beta \in K, which ensures that the norm respects multiplication and supports the well-ordering required for the Euclidean algorithm to terminate.^[16] This multiplicativity implies that units in \mathcal{O}_K have norm \pm 1, and it aids in proving that norm-Euclidean domains are principal ideal domains, as every ideal can be generated by a single element via repeated application of the division algorithm.^[1] Additionally, the norm's homogeneity under Galois action—where conjugates of \alpha yield the same absolute norm—provides a natural measure of "size" in the ring, independent of the choice of embedding.^[15] In applications, norm-Euclidean domains enable explicit constructions of the division algorithm within rings of algebraic integers, allowing efficient computation of greatest common divisors and factorization via the Euclidean algorithm, much like in the integers \mathbb{Z}.^[1] For instance, this framework is crucial for verifying unique factorization in specific number fields, such as quadratic fields where the norm explicitly bounds remainders.^[15] However, while norm-Euclideanity implies that the ideal class group of \mathcal{O}_K is trivial (i.e., class number 1, making \mathcal{O}_K a principal ideal domain), the converse does not hold: there exist number fields with class number 1 that are Euclidean but not norm-Euclidean.^[15] This distinction highlights that norm-Euclideanity is a stronger condition, sufficient for but not equivalent to principal ideal structure in algebraic number theory.^[1]

Non-Euclidean Principal Ideal Domains

While every Euclidean domain is a principal ideal domain, the converse does not hold. This was first demonstrated by Motzkin in 1949, who constructed an explicit example: the ring of integers \mathcal{O}_{\mathbb{Q}(\sqrt{-19})} = \mathbb{Z}\left[\frac{1 + \sqrt{-19}}{2}\right] is a PID but admits no Euclidean function.^[17] Motzkin's proof shows that no function \phi: \mathcal{O}_{\mathbb{Q}(\sqrt{-19})} \setminus \{0\} \to \mathbb{N} \cup \{0\} satisfies the division property required for a Euclidean domain.^[1] The imaginary quadratic fields provide a complete classification of such counterexamples among quadratic number fields. There are exactly nine imaginary quadratic fields \mathbb{Q}(\sqrt{d}) with d < 0 square-free whose rings of integers are PIDs, corresponding to d = -1, -2, -3, -7, -11, -19, -43, -67, -163; this list was conjectured by Gauss and proven by Heegner, Baker, and Stark.^[18] Among these, the rings for d = -1, -2, -3, -7, -11 are norm-Euclidean (hence Euclidean).^[1] In contrast, the rings for d = -19, -43, -67, -163 are PIDs but not Euclidean; the case d = -19 follows from Motzkin, while the others were established by subsequent proofs showing the absence of any suitable Euclidean function.^[17]^[19]^[1] For real quadratic fields, the situation differs markedly. All known PIDs among their rings of integers are Euclidean, though typically not norm-Euclidean; a seminal example is \mathbb{Q}(\sqrt{69}), whose ring \mathbb{Z}\left[\frac{1 + \sqrt{69}}{2}\right] admits a Euclidean function distinct from the norm.^[10] It remains an open problem whether every real quadratic PID is Euclidean, with results showing that all but finitely many real quadratic fields of class number one are Euclidean.^[1]