Euclidean domain
In mathematics, more specifically in ring theory, a Euclidean domain is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of the integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination
of them. Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is a unique factorization domain.
It is important to compare the class of Euclidean domains with the larger class of principal ideal domains. An arbitrary PID has much the same "structural properties" of a Euclidean domain, but when an explicit algorithm for Euclidean division is known, one may use Euclidean algorithm and extended Euclidean algorithm to compute greatest common divisors and Bézout's identity. In particular, the existence of efficient algorithms for Euclidean division of integers and of polynomials in one variable over a field is of basic importance in computer algebra.
So, given an integral domain, it is often very useful to know that has a Euclidean function: in particular, this implies that is a PID. However, if there is no "obvious" Euclidean function, then determining whether is a PID is generally a much easier problem than determining whether it is a Euclidean domain.
Euclidean domains appear in the following chain of class inclusions:
Definition
Let be an integral domain. A Euclidean function on is a function from to the non-negative integers satisfying the following fundamental division-with-remainder property:- If and are in and is nonzero, then there exists and in such that and either or.
Most algebra texts require a Euclidean function to have the following additional property:
- For all nonzero and in,.
In words, one may define to be the minimum value attained by on the set of all non-zero elements of the principal ideal generated by.
A multiplicative Euclidean function is a Euclidean function such that and is never zero. It follows that. More generally, if and only if is a unit.
Examples
Examples of Euclidean domains include:- Any field. Define for all nonzero.
- , the ring of integers. Define, the absolute value of.
- , the ring of Gaussian integers. Define, the norm of the Gaussian integer.
- , the ring of Eisenstein integers. Define, the norm of the Eisenstein integer.
- , the ring of polynomials over a field. For each nonzero polynomial, define to be the degree of.
- , the ring of formal power series over the field. For each nonzero power series, define as the order of, that is the degree of the smallest power of occurring in. In particular, for two nonzero power series and, if and only if divides.
- Any discrete valuation ring. Define to be the highest power of the maximal ideal containing. Equivalently, let be a generator of, and be the unique integer such that is an associate of, then define. The previous example is a special case of this.
- A Dedekind domain with finitely many nonzero prime ideals. Define, where is the discrete valuation corresponding to the ideal.
- Every domain that is not a principal ideal domain, such as the ring of polynomials in at least two indeterminates over a field, or the ring of univariate polynomials with integer coefficients, or the number ring.
- The ring of integers of, consisting of the numbers where and are integers and both even or both odd. It is a principal ideal domain that is not Euclidean.
- The ring is also a principal ideal domain that is not Euclidean.
Properties
- R is a principal ideal domain. In fact, if I is a nonzero ideal of R then any element a of I\ with minimal value of f is a generator of I. As a consequence R is also a unique factorization domain and a Noetherian ring. With respect to general principal ideal domains, the existence of factorizations is particularly easy to prove in Euclidean domains: choosing a Euclidean function f satisfying, x cannot have any decomposition into more than f nonunit factors, so starting with x and repeatedly decomposing reducible factors is bound to produce a factorization into irreducible elements.
- Any element of R at which f takes its globally minimal value is invertible in R. If an f satisfying is chosen, then the converse also holds, and f takes its minimal value exactly at the invertible elements of R.
- If the Euclidean property is algorithmic, i.e., if there is a division algorithm that for given a and nonzero b produces a quotient q and remainder r with and either or, then an extended Euclidean algorithm can be defined in terms of this division operation.
- If a Euclidean domain is not a field then it has an element a with the following property: any element x not divisible by a can be written as x=ay+u for some unit u and some element y. This follows by taking a to be a non-unit with f as small as possible. This strange property can be used to show that some principal ideal domains are not Euclidean domains, as not all PIDs have this property. For example, for d = −19, −43, −67, −163, the ring of integers of is a PID which is Euclidean, but the cases d = −1, −2, −3, −7, −11 Euclidean.
Assuming the extended Riemann hypothesis, if K is a finite extension of Q and the ring of integers of K is a PID with an infinite number of units, then the ring of integers is Euclidean.
In particular this applies to the case of totally real quadratic number fields with trivial class group.
In addition, if the field K is a Galois extension of Q, has trivial class group and unit rank strictly greater than three, then the ring of integers is Euclidean.
An immediate corollary of this is that if the number field is Galois over Q, its class group is trivial and the extension has degree greater than 8 then the ring of integers is necessarily Euclidean.
Norm-Euclidean fields
s K come with a canonical norm function on them: the absolute value of the field norm N that takes an algebraic element α to the product of all the conjugates of α. This norm maps the ring of integers of a number field K, say OK, to the nonnegative rational integers, so it is a candidate to be a Euclidean norm on this ring. If this norm satisfies the axioms of a Euclidean function then the number field K is called norm-Euclidean or simply Euclidean. Strictly speaking it is the ring of integers that is Euclidean since fields are trivially Euclidean domains, but the terminology is standard.If a field is not norm-Euclidean then that does not mean the ring of integers is not Euclidean, just that the field norm does not satisfy the axioms of a Euclidean function. In fact, the rings of integers of number fields may be divided in several classes:
- Those that are not principal and therefore not Euclidean, such as the integers of
- Those that are principal and not Euclidean, such as the integers of
- Those that are Euclidean and not norm-Euclidean, such as the integers of
- Those that are norm-Euclidean, such as Gaussian integers
Every Euclidean imaginary quadratic field is norm-Euclidean and is one of the five first fields in the preceding list.