transfinite arithmetic, cardinal arithmetic, ordinal arithmetic
prime field, p-adic integer, p-adic rational number, p-adic complex number
arithmetic geometry, function field analogy
A Euclidean domain is an integral domain which admits a form of the Euclidean quotient-and-remainder algorithm familiar from school mathematics, as well as a form of the extended Euclidean algorithm for calculating the greatest common divisor and Bézout coefficients in a Bézout domain.
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 .
One could posit, instead of the property that for all and , there exist such that and either or ; that the integral domain has the structure of a function called the division function, and a function called the remainder function, such that for all and , and either or . There might be multiple such division and remainder functions for the integral domain .
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.
In constructive mathematics, there are different types of integral domains, yielding different types of Euclidean domains: the degree function, division, function, and remainder function are no longer valued in in one variable, but in , , or some other definition, depending on what the base integral domain ends up being (classical, Heyting, discrete, residue, et cetera).
The definition of the Euclidean domain further bifurcates in constructive mathematics due to the disjunctive condition above. These statements, which are equivalent in the presence of excluded middle, include:
or equivalently,
The (rational) integers .
Any field (trivially).
The ring of polynomials over a discrete field , using the ordinary polynomial degree.
On the other hand, if is a Heyting field which is not a discrete field, not every polynomial in apart from zero can be proven to have a well-defined degree, and so is not an Euclidean domain.
The real polynomial ring is only an Euclidean domain in the presence of the analytic limited principle of omniscience, which states that it has decidable apartness.
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 Bézout domain.
Let be a nonzero finitely generated 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 extended 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 .
Euclidean domains could be generalised to the case where the structure is only a rig instead of a ring; these objects could be called Euclidean cancellative rigs.
See also:
Wikipedia, Euclidean algorithm
Wikipedia, extended Euclidean algorithm
Last revised on August 19, 2024 at 15:07:20. See the history of this page for a list of all contributions to it.