Euclidean Domains

Euclidean domains are integral domains equipped with a division algorithm, providing the most computationally accessible class of rings with unique factorization.

Definition

Definition6.3Euclidean domain

An integral domain $R$ is a Euclidean domain if there exists a function $\varphi: R \setminus \{0\} \to \mathbb{N}_0$ (the Euclidean function or norm) such that for all $a, b \in R$ with $b \neq 0$ , there exist $q, r \in R$ with:

$a = bq + r, \quad \text{where } r = 0 \text{ or } \varphi(r) < \varphi(b).$

ExampleExamples of Euclidean domains

$\mathbb{Z}$ with $\varphi(n) = |n|$ .
$k[x]$ (for $k$ a field) with $\varphi(f) = \deg(f)$ .
$\mathbb{Z}[i]$ (Gaussian integers) with $\varphi(a+bi) = a^2 + b^2$ .
$\mathbb{Z}[\omega]$ where $\omega = e^{2\pi i/3}$ (Eisenstein integers) with $\varphi(a+b\omega) = a^2 - ab + b^2$ .
$\mathbb{Z}[\sqrt{2}]$ with $\varphi(a+b\sqrt{2}) = |a^2 - 2b^2|$ .

The Euclidean Algorithm

Theorem6.3Euclidean algorithm

In a Euclidean domain, the GCD of two elements $a, b$ can be computed by repeated division:

$a = bq_0 + r_1, \quad b = r_1 q_1 + r_2, \quad r_1 = r_2 q_2 + r_3, \quad \ldots$

The last nonzero remainder is $\gcd(a,b)$ . Moreover, it can be expressed as a linear combination: $\gcd(a,b) = sa + tb$ for some $s, t \in R$ (the extended Euclidean algorithm).

ExampleGCD in Gaussian integers

Compute $\gcd(3+i, 1+2i)$ in $\mathbb{Z}[i]$ :

$(3+i)/(1+2i) = (3+i)(1-2i)/|1+2i|^2 = (5-5i)/5 = 1 - i$ .

So $3 + i = (1+2i)(1-i) + r$ where $r = (3+i) - (1+2i)(1-i) = (3+i) - (3+i) = 0$ .

Thus $\gcd(3+i, 1+2i) = 1+2i$ (up to units $\{\pm 1, \pm i\}$ ).

Every ED is a PID

Theorem6.4Euclidean domain implies PID

Every Euclidean domain is a principal ideal domain.

Proof

Let $I$ be a nonzero ideal of the Euclidean domain $R$ . Among all nonzero elements of $I$ , choose $b$ with minimal $\varphi(b)$ . We claim $I = (b)$ .

For any $a \in I$ , divide: $a = bq + r$ with $r = 0$ or $\varphi(r) < \varphi(b)$ . Since $r = a - bq \in I$ and $\varphi(b)$ was minimal, we must have $r = 0$ . So $a = bq \in (b)$ . $\blacksquare$

■

RemarkThe full hierarchy

$\text{fields} \subset \text{Euclidean domains} \subset \text{PIDs} \subset \text{UFDs} \subset \text{integral domains}$

Each inclusion is strict. The ring $\mathbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a PID that is not Euclidean (proved by Motzkin). The ring $\mathbb{Z}[x]$ is a UFD that is not a PID.