Euclidean Domains — Algebra (Dummit & Foote)
📐 Today’s Lesson: Euclidean Domains From: Algebra (Dummit & Foote) — Section 40
Euclidean Domains
Euclidean domains are integral domains equipped with a division algorithm, generalizing the familiar properties of the integers. In a Euclidean domain, we can perform division with remainder, leading to the Euclidean algorithm for computing greatest common divisors and many other computational conveniences.
Definition and Basic Properties
📖 Definition — Euclidean Domain
An integral domain R is a Euclidean domain if there exists a function N: R {0} → ℤ_≥_ ₀ (called a Euclidean function or norm) such that:
For all a, b ∈ R with b ≠ 0, there exist q, r ∈ R with
a = bq + r
where either r = 0 or N(r) < N(b).
✏️ Example — The Integers
ℤ is a Euclidean domain with norm N(a) = |a|.
The division algorithm: for a, b ∈ ℤ with b ≠ 0, there exist unique q (quotient) and r (remainder) with a = bq + r and 0 ≤ r < |b|.
✏️ Example — Polynomial Rings over Fields
If F is a field, then F[x] is a Euclidean domain with norm N(f) = (f).
For example, in ℚ[x], dividing x³ + 1 by x - 1:
x³ + 1 = (x - 1)(x² + x + 1) + 2
Here q = x² + x + 1 and r = 2, with (2) = 0 < 1 = (x - 1).
✏️ Example — Gaussian Integers
The ring ℤ[i] = {a + bi : a, b ∈ ℤ} is a Euclidean domain with norm N(a + bi) = a² + b².
This norm is multiplicative: N(zw) = N(z)N(w).
For example, dividing 7 + 2i by 3 + i: In ℚ[i], (7 + 2i)/(3 + i) = ((7+2i)(3-i))/((3+i)(3-i)) = (23 - i)/10 = 2.3 - 0.1i. Rounding to 2 + 0i = 2, the remainder is (7+2i) - 2(3+i) = 1.
The Euclidean Algorithm
📐 Theorem — Euclidean Algorithm
By the Euclidean property, we can write a = bq₁ + r₁. If r₁ ≠ 0, then N(r₁) < N(b).
Continuing: b = r₁ q₂ + r₂, etc. The sequence N(b) > N(r₁) > N(r₂) > ⋯ is a strictly decreasing sequence of non-negative integers, so it must terminate at 0.
If rₙ₊₁ = 0, then (a, b) = rₙ (or b if r₁ = 0).
In a Euclidean domain, the Euclidean algorithm computes the greatest common divisor of any two elements in finitely many steps.
Moreover, we can express (a, b) as a linear combination (a, b) = sa + tb (Bezout’s identity).
✏️ Example — GCD in Z[i]
Find (11 + 7i, 18 - i) in ℤ[i]:
Step 1: Divide 18 - i by 11 + 7i.
(18 - i)/(11 + 7i) = ((18-i)(11-7i))/((11+7i)(11-7i)) = (191 - 137i)/170 ≈ 1.12 - 0.81i
Round to 1 - i. Then r = (18 - i) - (1-i)(11+7i) = (18-i) - (18-4i) = 3i.
Step 2: Divide 11 + 7i by 3i. (11+7i)/3i = (7 - 11i)/(3i · (-i/i)) = (7-11i)/(-3) · (-1) = (7-11i)/3… This gives 2 - 4i with remainder 11 + 7i - 3i(2-4i) = 11 + 7i - 6i - 12 = -1 + i.
Continuing eventually gives = 1 + 2i (up to units).
Properties of Euclidean Domains
📐 Theorem — Euclidean Domains are PIDs
Let I be a nonzero ideal of R. Among all nonzero elements of I, choose d with minimal norm N(d).
We claim I = (d). Clearly (d) ⊆ I. For the reverse, let a ∈ I. By the Euclidean property, a = dq + r with r = 0 or N(r) < N(d).
Since r = a - dq ∈ I, minimality of N(d) forces r = 0. Thus a = dq ∈ (d).
Every Euclidean domain is a Principal Ideal Domain (PID).
Converse is False: Not every PID is a Euclidean domain. A famous example is ℤ[(1 + √(-19))/2], which is a PID but admits no Euclidean function.
Examples and Non-Examples
✏️ Example — More Euclidean Domains
The following are Euclidean domains:
• ℤ with N(a) = |a| • F[x] for any field F, with N(f) = (f) • ℤ[i] (Gaussian integers) with N(a+bi) = a² + b² • ℤ[ω] where ω = e²^π^ ⁱ^/³ (Eisenstein integers) • ℤ[√(-2)] with N(a + b√(-2)) = a² + 2b²
✏️ Example — Units in Euclidean Domains
In a Euclidean domain, the units are often related to the norm function.
In ℤ[i]: u is a unit iff N(u) = 1, so the units are {1, -1, i, -i}.
In F[x]: units are nonzero constants (degree 0 polynomials), which are F^×.
📖 Definition — Associates
Elements a, b in an integral domain are associates if a = ub for some unit u.
Associates differ only by unit factors and generate the same principal ideal: (a) = (b).
✏️ Example — Associates in Z and Z[i]
In ℤ: 3 and -3 are associates.
In ℤ[i]: 2 + i, -2 - i, 1 - 2i, and -1 + 2i are all associates (differing by factors of 1, -1, i, -i).
Computational Significance: The existence of a Euclidean algorithm makes many computations practical: finding GCDs, computing inverses modulo an ideal, solving linear Diophantine equations, and more. This is why Euclidean domains are particularly important in computational algebra.
Summary: A Euclidean domain is an integral domain with a norm function enabling division with remainder. The Euclidean algorithm computes GCDs and expresses them as linear combinations. Key examples include ℤ, F[x], and ℤ[i]. Every Euclidean domain is a PID, making ideals particularly tractable.
🔗 Interactive version: https://magicinternetmath.com
🏴☠️ Subscribe to the Pioneers Club — free courses from high school algebra to elliptic curve cryptography.
Write a comment