Euclidean domain
Encyclopedia
In mathematics
, more specifically in abstract algebra
and ring theory
, a Euclidean domain (also called a Euclidean ring) is a ring
that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm
. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integer
s: 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 (Bézout identity). 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 domain
s (PIDs). An arbitrary PID has much the same "structural properties" of a Euclidean domain (or, indeed, even of the ring of integers), but knowing an explicit Euclidean function gives a concreteness which is useful for algorithmic applications. Especially, the fact that the integers and any polynomial ring in one variable over a field are Euclidean domains with respect to easily computable Euclidean functions is of basic importance in computational algebra.
So, given an integral domain R, it is often very useful to know that R has a Euclidean function: in particular, this implies that R is a PID. However, if there is no "obvious" Euclidean function, then determining whether R 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:
s with the natural operations of + and ⋅. The familiar concept of long division
on the integers relies heavily on the following fact: Given an integer a and a non-zero integer b, there exists integers q and r with a = q⋅b + r, and furthermore, with r = 0 or |r| < |b|. If we only were to have considered positive a and b, this restriction on r and b may be expressed as r = 0, or r < b. Any ring
has a notion of addition and multiplication so it is conceivable to think that this notion of long division may be generalized to any ring. However, the requirement on the remainder
and the quotient
(r = 0 or r < b) cannot be easily defined in the context of rings, unless of course there exists an ordering
of some sort defined on the ring. This leads to the concept of a Euclidean domain, where the ring is equipped with a norm
, called its "degree function", mapping each element in the ring to its distance from the additive identity 0. So rather than requiring r = 0 or r < b, we may lift this to r = 0 or d(r) < d(b). The essential idea behind a Euclidean domain is a ring, any element of which (a) and any non-zero element of which (b) have the property that there exists a multiple of b not too far away from a. Of course, if the ring happens to be a division ring
(or a field
), a⋅b−1 yields a multiple of b (the pre-multiplication of this entity with b), which gives a. So for fields and division rings, there exists a multiple of b which exactly matches with a. Of course this need not be true in general (e.g. it fails for the integers) so the restriction is relaxed to just "a multiple of b sufficiently close to a". The natural question to ask is what the range
of the degree function is defined to be. For many purposes, and in particular for the purpose that the Euclidean algorithm
should hold, the range is defined to be the natural numbers. The crucial property of the natural numbers, here, is that they are well-ordered.
satisfying the following fundamental division-with-remainder property:
A Euclidean domain is an integral domain which can be endowed with at least one Euclidean function. It is important to note that a particular Euclidean function f is not part of the structure of a Euclidean domain: in general, a Euclidean domain will admit many different Euclidean functions.
Most algebra texts require a Euclidean function to have the following additional property:
However, one can show that (EF2) is superfluous in the following sense: any domain R which
can be endowed with a function g satisfying (EF1) can also be endowed with a function f satisfying (EF1) and (EF2): indeed, for
one can define f(a) as follows. (Rogers 1971)
In words, one may define f(a) to be the minimum value attained by g on the set of all non-zero elements of the principal ideal generated by a.
Not every PID is Euclidean. For example, for d = −19, −43, −67, −163, the ring of integers
of
is a PID which is not Euclidean, but the cases d = −1, −2, −3, −7, −11 are Euclidean.
However, in many finite extensions
of Q with trivial class group
, the ring of integers is Euclidean (not necessarily with respect to the absolute value of the field norm; see below).
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 (and without assuming ERH), 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.
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. 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. Indeed, there are examples of number fields whose ring of integers is Euclidean but not norm-Euclidean, a simple example being the quadratic field
. Finding all such fields is a major open problem, particularly in the quadratic case.
The norm-Euclidean quadratic fields have been fully classified, they are
where d takes the values
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, more specifically in abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
and ring theory
Ring theory
In abstract algebra, ring theory is the study of rings—algebraic structures in which addition and multiplication are defined and have similar properties to those familiar from the integers...
, a Euclidean domain (also called a Euclidean ring) is a ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
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 (Bézout identity). Also every ideal in a Euclidean domain is principal
Principal ideal
In ring theory, a branch of abstract algebra, a principal ideal is an ideal I in a ring R that is generated by a single element a of R.More specifically:...
, which implies a suitable generalization of the Fundamental Theorem of Arithmetic
Fundamental theorem of arithmetic
In number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
: every Euclidean domain is a unique factorization domain
Unique factorization domain
In mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...
.
It is important to compare the class of Euclidean domains with the larger class of principal ideal domain
Principal ideal domain
In abstract algebra, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principal, although some authors refer to PIDs as...
s (PIDs). An arbitrary PID has much the same "structural properties" of a Euclidean domain (or, indeed, even of the ring of integers), but knowing an explicit Euclidean function gives a concreteness which is useful for algorithmic applications. Especially, the fact that the integers and any polynomial ring in one variable over a field are Euclidean domains with respect to easily computable Euclidean functions is of basic importance in computational algebra.
So, given an integral domain R, it is often very useful to know that R has a Euclidean function: in particular, this implies that R is a PID. However, if there is no "obvious" Euclidean function, then determining whether R 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:
- Commutative ringCommutative ringIn ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....
s ⊃ integral domains ⊃ integrally closed domainIntegrally closed domainIn commutative algebra, an integrally closed domain A is an integral domain whose integral closure in the field of fractions of A is A itself...
s ⊃ unique factorization domainUnique factorization domainIn mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...
s ⊃ principal ideal domainPrincipal ideal domainIn abstract algebra, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principal, although some authors refer to PIDs as...
s ⊃ Euclidean domains ⊃ fieldField (mathematics)In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
s
Motivation
Consider the set of integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s with the natural operations of + and ⋅. The familiar concept of long division
Long division
In arithmetic, long division is a standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a...
on the integers relies heavily on the following fact: Given an integer a and a non-zero integer b, there exists integers q and r with a = q⋅b + r, and furthermore, with r = 0 or |r| < |b|. If we only were to have considered positive a and b, this restriction on r and b may be expressed as r = 0, or r < b. Any ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
has a notion of addition and multiplication so it is conceivable to think that this notion of long division may be generalized to any ring. However, the requirement on the remainder
Remainder
In arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
and the quotient
Quotient
In mathematics, a quotient is the result of division. For example, when dividing 6 by 3, the quotient is 2, while 6 is called the dividend, and 3 the divisor. The quotient further is expressed as the number of times the divisor divides into the dividend e.g. The quotient of 6 and 2 is also 3.A...
(r = 0 or r < b) cannot be easily defined in the context of rings, unless of course there exists an ordering
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
of some sort defined on the ring. This leads to the concept of a Euclidean domain, where the ring is equipped with a norm
Norm (mathematics)
In linear algebra, functional analysis and related areas of mathematics, a norm is a function that assigns a strictly positive length or size to all vectors in a vector space, other than the zero vector...
, called its "degree function", mapping each element in the ring to its distance from the additive identity 0. So rather than requiring r = 0 or r < b, we may lift this to r = 0 or d(r) < d(b). The essential idea behind a Euclidean domain is a ring, any element of which (a) and any non-zero element of which (b) have the property that there exists a multiple of b not too far away from a. Of course, if the ring happens to be a division ring
Division ring
In abstract algebra, a division ring, also called a skew field, is a ring in which division is possible. Specifically, it is a non-trivial ring in which every non-zero element a has a multiplicative inverse, i.e., an element x with...
(or a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
), a⋅b−1 yields a multiple of b (the pre-multiplication of this entity with b), which gives a. So for fields and division rings, there exists a multiple of b which exactly matches with a. Of course this need not be true in general (e.g. it fails for the integers) so the restriction is relaxed to just "a multiple of b sufficiently close to a". The natural question to ask is what the range
Range (mathematics)
In mathematics, the range of a function refers to either the codomain or the image of the function, depending upon usage. This ambiguity is illustrated by the function f that maps real numbers to real numbers with f = x^2. Some books say that range of this function is its codomain, the set of all...
of the degree function is defined to be. For many purposes, and in particular for the purpose that the Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
should hold, the range is defined to be the natural numbers. The crucial property of the natural numbers, here, is that they are well-ordered.
Definition
Let R be an integral domain. A Euclidean function on R is a function satisfying the following fundamental division-with-remainder property:- (EF1) If a and b are in R and b is nonzero, then there are q and r in R such that and either r = 0 or .
A Euclidean domain is an integral domain which can be endowed with at least one Euclidean function. It is important to note that a particular Euclidean function f is not part of the structure of a Euclidean domain: in general, a Euclidean domain will admit many different Euclidean functions.
Most algebra texts require a Euclidean function to have the following additional property:
- (EF2) For all nonzero a and b in R, .
However, one can show that (EF2) is superfluous in the following sense: any domain R which
can be endowed with a function g satisfying (EF1) can also be endowed with a function f satisfying (EF1) and (EF2): indeed, for
one can define f(a) as follows. (Rogers 1971)In words, one may define f(a) to be the minimum value attained by g on the set of all non-zero elements of the principal ideal generated by a.
Examples
Examples of Euclidean domains include:- Any field. Define f(x) = 1 for all nonzero x.
- Z, the ring of integerIntegerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s. Define f(n) = |n|, the absolute valueAbsolute valueIn mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
of n. - Z[i], the ring of Gaussian integerGaussian integerIn number theory, a Gaussian integer is a complex number whose real and imaginary part are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i]. The Gaussian integers are a special case of the quadratic...
s. Define f(a + bi) = a2 + b2, the squared norm of the Gaussian integer a + bi. - Z[ω] (where ω is a cube root of 1), the ring of Eisenstein integerEisenstein integerIn mathematics, Eisenstein integers , also known as Eulerian integers , are complex numbers of the formz = a + b\omega \,\!where a and b are integers and...
s. Define f(a + bω) = a2 − ab + b2, the norm of the Eisenstein integer a + bω. - K[X], the ring of polynomialsPolynomial ringIn mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...
over a fieldField (mathematics)In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
K. For each nonzero polynomial P, define f(P) to be the degree of P. - K
X , the ring of formal power series Formal power seriesIn mathematics, formal power series are a generalization of polynomials as formal objects, where the number of terms is allowed to be infinite; this implies giving up the possibility to substitute arbitrary values for indeterminates...
over the field K. For each nonzero power series P, define f(P) as the degree of the smallest power of X occurring in P. In particular, for two nonzero power series P and Q, f(P)≤f(Q) iff P divides Q. - Any discrete valuation ringDiscrete valuation ringIn abstract algebra, a discrete valuation ring is a principal ideal domain with exactly one non-zero maximal ideal.This means a DVR is an integral domain R which satisfies any one of the following equivalent conditions:...
. Define f(x) to be the highest power of the maximal ideal M containing x (equivalently, to the power of the generator of the maximal ideal that x is associated to). The previous case KX is a special case of this. - A Dedekind domainDedekind domainIn abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily unique up to the order of the factors...
with finitely many nonzero prime ideals P1, ..., Pn. Define
, where 
is the discrete valuation corresponding to the ideal Pi. (Samuel 1971)
Properties
Let R be a domain and f a Euclidean function on R. Then:- R is a principal ideal domainPrincipal ideal domainIn abstract algebra, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principal, although some authors refer to PIDs as...
. In fact, if I is a nonzero ideal of R then any element a of I\{0} with minimal value (on that set) of f(a) is a generator of I. As a consequence R is also a unique factorization domainUnique factorization domainIn mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...
and a Noetherian ringNoetherian ringIn mathematics, more specifically in the area of modern algebra known as ring theory, a Noetherian ring, named after Emmy Noether, is a ring in which every non-empty set of ideals has a maximal element...
. With respect to general principal ideal domains, the existence of factorizations (i.e., that R is an atomic domainAtomic domainIn mathematics, more specifically ring theory, an atomic domain or factorization domain is an integral domain, every non-zero non-unit of which can be written as a product of irreducible elements...
) is particularly easy to prove in Euclidean domains: choosing a Euclidean function f satisfying (EF2), x cannot have any decomposition into more than f(x) 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 (EF2) 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 algorithmDivision algorithmIn mathematics, and more particularly in arithmetic, the usual process of division of integers producing a quotient and a remainder can be specified precisely by a theorem stating that these exist uniquely with given properties. An integer division algorithm is any effective method for producing...
that for given a and nonzero b produces a quotient q and remainder r with and either or , then an extended Euclidean algorithmExtended Euclidean algorithmThe extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...
can be defined in terms of this division operation.
Not every PID is Euclidean. For example, for d = −19, −43, −67, −163, the ring of integers
Ring of integers
In mathematics, the ring of integers is the set of integers making an algebraic structure Z with the operations of integer addition, negation, and multiplication...
of
is a PID which is not Euclidean, but the cases d = −1, −2, −3, −7, −11 are Euclidean.However, in many finite extensions
Field extension
In abstract algebra, field extensions are the main object of study in field theory. The general idea is to start with a base field and construct in some manner a larger field which contains the base field and satisfies additional properties...
of Q with trivial class group
Ideal class group
In mathematics, the extent to which unique factorization fails in the ring of integers of an algebraic number field can be described by a certain group known as an ideal class group...
, the ring of integers is Euclidean (not necessarily with respect to the absolute value of the field norm; see below).
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 (and without assuming ERH), if the field K is a Galois extension of Q, has trivial class group and unit rank
Dirichlet's unit theorem
In mathematics, Dirichlet's unit theorem is a basic result in algebraic number theory due to Gustav Lejeune Dirichlet. It determines the rank of the group of units in the ring OK of algebraic integers of a number field K...
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
Algebraic number fieldAlgebraic number field
In mathematics, an algebraic number field F is a finite field extension of the field of rational numbers Q...
s K come with a canonical norm function on them: the absolute value of the field norm
Field norm
In mathematics, the norm is a mapping defined in field theory, to map elements of a larger field into a smaller one.-Formal definitions:1. Let K be a field and L a finite extension of K...
N that takes an algebraic element α to the product of all the conjugates
Conjugate element (field theory)
In mathematics, in particular field theory, the conjugate elements of an algebraic element α, over a field K, are the roots of the minimal polynomialof α over K.-Example:The cube roots of the number one are:...
of α. This norm maps the ring of integers
Ring of integers
In mathematics, the ring of integers is the set of integers making an algebraic structure Z with the operations of integer addition, negation, and multiplication...
of a number field K, say OK, to the nonnegative rational integers
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
, 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. 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. Indeed, there are examples of number fields whose ring of integers is Euclidean but not norm-Euclidean, a simple example being the quadratic field
. Finding all such fields is a major open problem, particularly in the quadratic case.The norm-Euclidean quadratic fields have been fully classified, they are
where d takes the values
- −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 .