Euclidean Domains

Introduction

Euclidean Domains (EDs) are integral domains that have a division algorithm, making them particularly well-behaved and easy to work with. They are the most restrictive class in the hierarchy of domains.

Definition

Definition 10.4: An integral domain $R$ is a Euclidean Domain (ED) if there exists a function $N : R ∖ {0} \to Z_{\geq 0}$ (called a Euclidean norm) such that for any $a, b \in R$ with $b \neq 0$ , there exist $q, r \in R$ where $a = q b + r$ and either $r = 0$ or $N (r) < N (b)$ .

The existence of a division algorithm in Euclidean domains makes their structure particularly transparent.

Properties

Division Algorithm

The key property of Euclidean domains is the existence of a division algorithm, which allows for efficient computation of greatest common divisors using the Euclidean algorithm.

Principal Ideal Domains

Every Euclidean domain is a Principal Ideal Domain (PID), meaning every ideal is generated by a single element.

Unique Factorization

Since every ED is a PID, and every PID is a UFD, Euclidean domains have unique factorization.

Greatest Common Divisors

The Euclidean algorithm can be used to compute greatest common divisors efficiently in Euclidean domains.

Examples

Example 1: The Ring of Integers

The integers $Z$ form a Euclidean domain with the absolute value as the Euclidean norm: $N (a) = | a |$ .

Example 2: Polynomial Rings over Fields

For any field $F$ , the polynomial ring $F [x]$ is a Euclidean domain with the degree function as the Euclidean norm: $N (f) = \deg (f)$ .

Example 3: Gaussian Integers

The ring of Gaussian integers $Z [i] = {a + b i ∣ a, b \in Z}$ is a Euclidean domain with the norm $N (a + b i) = a^{2} + b^{2}$ .

Example 4: Eisenstein Integers

The ring $Z [ω]$ where $ω = e^{2 π i / 3}$ is a Euclidean domain.

Euclidean Algorithm

The Euclidean algorithm can be used to find the greatest common divisor of two elements in a Euclidean domain:

Given $a, b \in R$ with $b \neq 0$
Apply the division algorithm: $a = q_{1} b + r_{1}$ where $N (r_{1}) < N (b)$
If $r_{1} = 0$ , then $gcd (a, b) = b$
Otherwise, repeat with $b$ and $r_{1}$
Continue until a remainder of 0 is obtained

Relationship to Other Domains

Euclidean domains form the most restrictive class in the hierarchy:

Euclidean Domains ⟹ Principal Ideal Domains ⟹ Unique Factorization Domains

The implication is strict: there are PIDs that are not Euclidean domains, such as $Z [\frac{1 + \sqrt{- 19}}{2}]$ .

Applications

Application 1: Number Theory

Euclidean domains provide efficient algorithms for computing greatest common divisors and solving Diophantine equations.

Application 2: Polynomial Theory

The division algorithm in polynomial rings is fundamental for polynomial factorization and root finding.

Application 3: Linear Algebra

Euclidean domains are important in linear algebra for understanding the structure of matrices over these rings.

Application 4: Cryptography

The Euclidean algorithm is fundamental in many cryptographic protocols.

Extended Euclidean Algorithm

The extended Euclidean algorithm not only finds the greatest common divisor but also expresses it as a linear combination of the input elements. This is crucial for solving linear Diophantine equations and finding multiplicative inverses.