Euclidean Domains

A Euclidean domain is an integral domain R which can be equipped with a function

d : R\{0} → ℕ

such that for all a ∈ R and b ≠ 0, b ∈ R we can write

a = qb + r

for some q, r ∈ R with r = 0 or d(r) < d(b).

For example. ℤ with d(n) = |n| is a Euclidean Domain; also, for any field k, k[X] with d(f) = deg(f) is a Euclidean Domain. (WARNING: In the second example above, it is essential that k be a field.)

We shall prove that every Euclidean Domain is a Principal Ideal Domain (and so also a Unique Factorization Domain). This shows that for any field k, k[X] has unique factorization into irreducibles. As a further example, we prove that ℤ [\sqrt{−2} ] is a Euclidean Domain.

Proposition 1. In a Euclidean domain, every ideal is principal.

Proof. Suppose R is a Euclidean domain and I◁R. Then EITHER I = {0} = (0) OR we can take a ≠ 0 in I with d(a) least; then for any b ∈ I, we can write b = qa + r with r = 0 or d(r) < d(a); but r = q − ba ∈ I and so by minimality of d(a), r = 0; thus a|b and I = (a).

Corollary 2. If k is a field then every ideal in k[X] is principal.

Corollary 3. Let k be a field. Then every polynomial in k[X] can be factorized into primes=irreducibles, and the factorization is essentially unique.

Corollary 4. Every element of the ring ℤ [\sqrt{−2} ] can be factorized into primes= irreducibles, and the factorization is essentially unique.

Proof. By Theorem 1, it is enough to show that ℤ [\sqrt{−2} ] is a Euclidean Domain. To this end, define N : ℤ [\sqrt{−2} ] → ℕ by

N (a + b\sqrt{−2} ) = a^{2} + 2b^{2} (= |a + b\sqrt{−2}|^{2}) (a, b ∈ ℤ) .

Note that we can extend N to a function N : ℚ [\sqrt{−2} ] → ℚ defined similarly by

N (a + b\sqrt{−2} ) = a^{2} + 2b^{2} (= |a + b\sqrt{−2}|^{2}) (a, b ∈ ℚ).

Note also that given any a + b\sqrt{−2}, c + d\sqrt{−2} ∈ ℚ [\sqrt{−2} ] we have

N ((a + b\sqrt{−2} ) (c + d\sqrt{−2} )) = N (a + b\sqrt{−2} ) N (c + d\sqrt{−2} ) .

Now, suppose we are given a + b\sqrt{−2}, c + d\sqrt{−2} ∈ ℤ [\sqrt{−2} ] with c + d\sqrt{−2} ≠ 0. Then

\frac{a + b\sqrt{−2}}{c + d\sqrt{−2}} = \frac{(a + b\sqrt{−2} ) (c − d\sqrt{−2} )}{c^{2} + 2d^{2}} = e + f\sqrt{−2} ∈ ℚ [\sqrt{−2} ] .

Pick g, h ∈ ℤ such that |e − g|, |f − h| ≤ \frac{1}{2} and set

q = g + h\sqrt{−2}
r = a + b\sqrt{−2} − q (c + d\sqrt{−2} ) .

Then a + b\sqrt{−2} = q (c + d\sqrt{−2} ) + r and

N(r) = N( (c + d\sqrt{−2} ) ((e − g) + (f − h)\sqrt{−2} ) )
= N (c + d\sqrt{−2} ) N ((e − g) + (f − h)\sqrt{−2} )
≤ \frac{3}{4}N (c + d\sqrt{−2} )
< N (c + d\sqrt{−2} ) .