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 for which there exists a function to the natural numbers, often called a degree function, such that given with , there exist such that and either or . (One may harmlessly stipulate that ; what to do with the zero element varies from author to author.) There is no uniqueness requirement for .
Some authors also add the requirement that for all nonzero . There is no loss of generality in assuming it; every Euclidean domain admits such a degree function , defining . We’ll use it freely below, if and when we need to.
The (rational) integers .
The ring of polynomials over a field , using the ordinary polynomial degree.
Any field (trivially).
Any discrete valuation ring: letting be a generator of the maximal ideal, put where , with a unit.
The Gaussian integers , with (the norm).
The Eisenstein integers? , where is a primitive cube root of unity, with (the norm).
A Euclidean domain is a principal ideal domain.
Let be a nonzero ideal, and suppose is the minimum degree taken over all nonzero . For such a and any , we may write where either or (which is impossible since and is minimal). So it is, and thus .
This proof uses the well-orderedness of . It also suggests the practical procedure known as the Euclidean algorithm: given two elements in a Euclidean domain , this algorithm provides a generator of the ideal , called a greatest common divisor of , as follows. One constructs a sequence of pairs of elements of , with , and where for some choice of such that and . If no such choices for exist, then the sequence terminates at , and generates , i.e, . Notice that the sequence terminates after finitely many steps since we cannot have an infinite descent of natural numbers
again by well-orderedness of .
The proof that this algorithm produces a gcd consists in the observation that at each step we have
and that from the definition of Euclidean domain, the only reason why the sequence would terminate at is that for some , and in that case .
Last revised on December 19, 2020 at 21:13:16. See the history of this page for a list of all contributions to it.