Euclidean Domains — Algebra (Dummit & Foote)

• Euclidean Domains
  • Definition and Basic Properties
  • The Euclidean Algorithm
  • Properties of Euclidean Domains
  • Examples and Non-Examples

📐 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.

⚡ fundamentals@zeuspay.com