In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, more specifically in
ring theory, a Euclidean domain (also called a Euclidean ring) is an
integral domain that can be endowed with a
Euclidean function which allows a suitable generalization of the
Euclidean division of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s. 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 (
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they ...
). Also every
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considered ...
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
Class or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used differently ...
of Euclidean domains with the larger class of
principal ideal domains (PIDs). An arbitrary PID has much the same "structural properties" of a Euclidean domain (or, indeed, even of the ring of integers), but when an explicit
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for Euclidean division is known, one may use the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an e ...
and
extended Euclidean algorithm to compute greatest common divisors and
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they ...
. In particular, the existence of efficient algorithms for Euclidean division of integers and of
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
s in one variable over a
field is of basic importance in
computer algebra
In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions ...
.
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:
*(EF1) If and are in and is nonzero, then there exist and in such that and either or .
A Euclidean domain is an integral domain which can be endowed with at least one Euclidean function. A particular Euclidean function is ''not'' part of the definition of a Euclidean domain, as, in general, a Euclidean domain may admit many different Euclidean functions.
In this context, and are called respectively a ''quotient'' and a ''remainder'' of the ''division'' (or ''Euclidean division'') of by . In contrast with the case of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s and
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
s, the quotient is generally not uniquely defined, but when a quotient has been chosen, the remainder is uniquely defined.
Most algebra texts require a Euclidean function to have the following additional property:
*(EF2) For all nonzero and in , .
However, one can show that (EF1) alone suffices to define a Euclidean domain; if an integral domain is endowed with a function satisfying (EF1), then can also be endowed with a function satisfying both (EF1) and (EF2) simultaneously. Indeed, for in , one can define as follows:
:
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 Euclidean function is multiplicative if and is never zero. It follows that . More generally, if and only if is a
unit.
Notes on the definition
Many authors use other terms in place of "Euclidean function", such as "degree function", "valuation function", "gauge function" or "norm function".
Some authors also require the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...
of the Euclidean function to be the entire ring ;
however, this does not essentially affect the definition, since (EF1) does not involve the value of . The definition is sometimes generalized by allowing the Euclidean function to take its values in any
well-ordered set; this weakening does not affect the most important implications of the Euclidean property.
The property (EF1) can be restated as follows: for any principal ideal of with nonzero generator , all nonzero classes of the
quotient ring have a representative with . Since the possible values of are well-ordered, this property can be established by showing that for any with minimal value of in its class. Note that, for a Euclidean function that is so established, there need not exist an effective method to determine and in (EF1).
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 .
* (where is a
primitive (non-
real)
cube root of unity), 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
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of ...
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
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible b ...
.
*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 In mathematics, a discrete valuation is an integer valuation on a field ''K''; that is, a function:
:\nu:K\to\mathbb Z\cup\
satisfying the conditions:
:\nu(x\cdot y)=\nu(x)+\nu(y)
:\nu(x+y)\geq\min\big\
:\nu(x)=\infty\iff x=0
for all x,y\in K ...
corresponding to the ideal .
Examples of domains that are ''not'' Euclidean domains include:
* 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. To see that it is not a Euclidean domain, it suffices to show that for every non-zero prime
, the map
induced by the quotient map
is not
surjective.
Properties
Let ''R'' be a domain and ''f'' a Euclidean function on ''R''. Then:
* ''R'' is a
principal ideal domain (PID). In fact, if ''I'' is a nonzero
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considered ...
of ''R'' then any element ''a'' of ''I'' \ with minimal value (on that set) of ''f''(''a'') 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 (i.e., that ''R'' is an
atomic domain) 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 Euclidean division is algorithmic, that is, if there is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for computing the quotient and the remainder, then an
extended Euclidean algorithm can be defined exactly as in the case of integers.
*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''(''a'') 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.
However, in many
finite extensions of Q with
trivial
Trivia is information and data that are considered to be of little value. It can be contrasted with general knowledge and common sense.
Latin Etymology
The ancient Romans used the word ''triviae'' to describe where one road split or fork ...
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
Extension, extend or extended may refer to:
Mathematics
Logic or set theory
* Axiom of extensionality
* Extensible cardinal
* Extension (model theory)
* Extension (predicate logic), the set of tuples of values that satisfy the predicate
* Ext ...
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.
Norm-Euclidean fields
Algebraic number fields ''K'' come with a canonical norm function on them: the absolute value of the
field norm ''N'' that takes an
algebraic element
In mathematics, if is a field extension of , then an element of is called an algebraic element over , or just algebraic over , if there exists some non-zero polynomial with coefficients in such that . Elements of which are not algebraic ove ...
''α'' to the product of all the
conjugates of ''α''. This norm maps the
ring of integers of a number field ''K'', say ''O''
''K'', 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 (integers of
)
The norm-Euclidean
quadratic fields have been fully classified; they are
where
takes the values
:−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 .
Every Euclidean imaginary quadratic field is norm-Euclidean and is one of the five first fields in the preceding list.
See also
*
Valuation (algebra)
Notes
References
*
*
{{DEFAULTSORT:Euclidean Domain
Ring theory
Commutative algebra
Domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...