Euclidean domain




A Euclidean domain is an integral domain which admits a form of the Euclidean quotient-and-remainder algorithm familiar from school mathematics.


A Euclidean domain is an integral domain AA for which there exists a function d:A{0}d: A \setminus \{0\} \to \mathbb{N} to the natural numbers, often called a degree function, such that given f,gAf, g \in A with g0g \neq 0, there exist q,rAq, r \in A such that f=qg+rf = q \cdot g + r and either r=0r = 0 or d(r)<d(g)d(r) \lt d(g). (One may harmlessly stipulate that d(0)=0d(0) = 0; what to do with the zero element varies from author to author.) There is no uniqueness requirement for q,rq, r.

Some authors also add the requirement that d(a)d(ab)d(a) \leq d(a b) for all nonzero a,ba, b. There is no loss of generality in assuming it; every Euclidean domain admits such a degree function dd', defining d(a)=min{d(ab):bA,b0}d'(a) = \min \{d(a b): b \in A, b \neq 0\}. We’ll use it freely below, if and when we need to.


  • The (rational) integers \mathbb{Z}.

  • The ring of polynomials k[x]k[x] over a field kk, using the ordinary polynomial degree.

  • Any field (trivially).

  • Any discrete valuation ring: letting π\pi be a generator of the maximal ideal, put d(x)=nd(x) = n where x=uπ nx = u \pi^n, with uu a unit.

  • The Gaussian integers [i]\mathbb{Z}[i], with d(a+bi)=a 2+b 2d(a + b i) = a^2 + b^2 (the norm).

  • The Eisenstein integers? [ω]\mathbb{Z}[\omega], where ω\omega is a primitive cube root of unity, with d(a+bω)=a 2ab+b 2d(a + b \omega) = a^2 - a b + b^2 (the norm).



A Euclidean domain is a principal ideal domain.


Let IAI \subseteq A be a nonzero ideal, and suppose d(g)d(g) is the minimum degree taken over all nonzero gIg \in I. For such a gg and any fIf \in I, we may write f=qg+rf = q g + r where either r=0r = 0 or d(r)<d(g)d(r) \lt d(g) (which is impossible since rIr \in I and d(g)d(g) is minimal). So r=0r = 0 it is, and thus I=(g)I = (g).

This proof uses the well-orderedness of \mathbb{N}. It also suggests the practical procedure known as the Euclidean algorithm: given two elements a,ba, b in a Euclidean domain AA, this algorithm provides a generator dd of the ideal I=(a)+(b)I = (a) + (b), called a greatest common divisor of a,ba, b, as follows. One constructs a sequence of pairs (a n,b n)(a_n, b_n) of elements of II, with (a 0,b 0)=(a,b)(a_0, b_0) = (a, b), and (a n+1,b n+1)=(b n,r n)(a_{n+1}, b_{n+1}) = (b_n, r_n) where a n=b nq n+r na_n = b_n q_n + r_n for some choice of q n,r nq_n, r_n such that d(r n)<d(b n)d(r_n) \lt d(b_n) and r n0r_n \neq 0. If no such choices for q n,r nq_n, r_n exist, then the sequence terminates at (a n,b n)(a_n, b_n), and b nb_n generates II, i.e, (b n)=I(b_n) = I. Notice that the sequence terminates after finitely many steps since we cannot have an infinite descent of natural numbers

d(r 0)>d(r 1)>,d(r_0) \gt d(r_1) \gt \ldots,

again by well-orderedness of \mathbb{N}.

The proof that this algorithm produces a gcd consists in the observation that at each step we have

(a n+1)+(b n+1)=(a n)+(b n),(a_{n+1}) + (b_{n+1}) = (a_n) + (b_n),

and that from the definition of Euclidean domain, the only reason why the sequence would terminate at (a n,b n)(a_n, b_n) is that a n=b nq n+0a_n = b_n q_n + 0 for some q nq_n, and in that case (a n)+(b n)=(b n)(a_n) + (b_n) = (b_n).

Last revised on December 19, 2020 at 21:13:16. See the history of this page for a list of all contributions to it.