Editing Euclidean domain

{{short description|Commutative ring with a Euclidean division}}
In [[mathematics]], more specifically in [[ring theory]], a '''Euclidean domain''' (also called a '''Euclidean ring''') is an [[integral domain]] that can be endowed with a [[#Definition|Euclidean function]] which allows a suitable generalization of [[Euclidean division]] of [[integer]]s.  This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the [[ring (mathematics)|ring]] of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the [[Greatest common divisor#In commutative rings|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 particular, the existence of efficient algorithms for Euclidean division of integers and of [[polynomial]]s in one variable over a [[field (mathematics)|field]] is of basic importance in [[computer algebra]].

It is important to compare the [[class (set theory)|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 lacks an analogue of the [[Euclidean algorithm]] and [[extended Euclidean algorithm]] to compute greatest common divisors. So, given an integral domain {{mvar|R}}, it is often very useful to know that {{mvar|R}} has a Euclidean function: in particular, this implies that {{mvar|R}} is a PID.  However, if there is no "obvious" Euclidean function, then determining whether {{mvar|R}} is a PID is generally a much easier problem than determining whether it is a Euclidean domain.

Every [[ideal (ring theory)|ideal]] in a Euclidean domain is [[principal ideal|principal]], which implies a suitable generalization of the [[fundamental theorem of arithmetic]]: every Euclidean domain is also a [[unique factorization domain]]. Euclidean domains appear in the following chain of [[subclass (set theory)|class inclusions]]:
{{Commutative ring classes}}
{{Algebraic structures |Ring}}

==Definition==
Let {{mvar|R}} be an integral domain.  A '''Euclidean function''' on {{mvar|R}} is a [[function (mathematics)|function]] {{mvar|f}} from {{math|''R''&thinsp;\&hairsp;{0} }}to the non-negative integers satisfying the following fundamental division-with-remainder property:

*(EF1) If {{mvar|a}} and {{mvar|b}} are in {{mvar|R}} and {{mvar|b}} is nonzero, then there exist {{mvar|q}} and {{mvar|r}} in {{mvar|R}} such that {{math|''a'' {{=}} ''bq'' + ''r''}} and either {{math|1=''r'' = 0}} or {{math|''f''&thinsp;(''r'') < ''f''&thinsp;(''b'')}}.

A '''Euclidean domain''' is an integral domain which can be endowed with at least one Euclidean function. A particular Euclidean function {{mvar|f}} 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, {{mvar|q}} and {{mvar|r}} are called respectively a ''quotient'' and a ''remainder'' of the ''division'' (or ''Euclidean division'') of {{mvar|a}} by {{mvar|b}}. In contrast with the case of [[integer]]s and [[polynomial]]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 {{mvar|a}} and {{mvar|b}} in {{mvar|R}}, {{math|''f''&thinsp;(''a'') ≤ ''f''&thinsp;(''ab'')}}.

However, one can show that (EF1) alone suffices to define a Euclidean domain; if an integral domain {{mvar|R}} is endowed with a function {{mvar|g}} satisfying (EF1), then {{mvar|R}} can also be endowed with a function satisfying both (EF1) and (EF2) simultaneously. Indeed, for {{mvar|a}} in {{math|''R''&thinsp;\&hairsp;{0} }}, one can define {{math|''f''&thinsp;(''a'')}} as follows:<ref>{{Citation | last = Rogers | first = Kenneth | title = The Axioms for Euclidean Domains | journal = [[American Mathematical Monthly]] | volume = 78 | issue = 10 | pages = 1127–8 | year = 1971 | doi = 10.2307/2316324 | jstor = 2316324 | zbl=0227.13007 }}</ref>

:<math>f(a) = \min_{x \in R \setminus \{0\}} g(xa)</math>

In words, one may define {{math|''f''&thinsp;(''a'')}} to be the minimum value attained by {{mvar|g}} on the set of all non-zero elements of the principal ideal generated by {{mvar|a}}.

A Euclidean function {{mvar|f}} is '''multiplicative''' if {{math|''f''&thinsp;(''ab'') {{=}} ''f''&thinsp;(''a'')&thinsp;''f''&thinsp;(''b'')}} and {{math|''f''&thinsp;(''a'')}} is never zero. It follows that {{math|''f''&thinsp;(1) {{=}} 1}}. More generally, {{math|''f''&thinsp;(''a'') {{=}} 1}} if and only if {{mvar|a}} is a [[unit (ring theory)|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".<ref name="DummitAlgebra">{{Cite book|title=Abstract Algebra|last1=Dummit|first1=David S.|last2=Foote|first2=Richard M.|publisher=Wiley|year=2004|isbn=9780471433347 |page=270}}</ref> Some authors also require the [[domain of a function|domain]] of the Euclidean function to be the entire ring {{mvar|R}};<ref name="DummitAlgebra"/> however, this does not essentially affect the definition, since (EF1) does not involve the value of {{math|''f''&thinsp;(0)}}. 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 {{mvar|I}} of {{mvar|R}} with nonzero generator {{mvar|b}}, all nonzero classes of the [[quotient ring]] {{math|''R''/''I''}} have a representative {{mvar|r}} with {{math|''f''&thinsp;(''r'') < ''f''&thinsp;(''b'')}}. Since the possible values of {{mvar|f}} are well-ordered, this property can be established by showing that {{math|''f''&thinsp;(''r'') < ''f''&thinsp;(''b'')}} for any {{math|''r'' ∉ ''I''}} with minimal value of {{math|''f''&thinsp;(''r'')}} in its class. Note that, for a Euclidean function that is so established, there need not exist an effective method to determine {{mvar|q}} and {{mvar|r}} in (EF1).

==Examples==
Examples of Euclidean domains include:

*Any field. Define {{math|''f''&thinsp;(''x'') {{=}} 1}} for all nonzero {{mvar|x}}.
*{{math|'''Z'''}}, the ring of integers. Define {{math|''f''&thinsp;(''n'') {{=}} {{!}}''n''{{!}}}}, the [[absolute value]] of {{mvar|n}}.<ref>{{harvnb|Fraleigh|Katz|1967|p=377, Example 1}}</ref>
*{{math|'''Z'''[{{hairsp|''i''}}]}}, the ring of [[Gaussian integer]]s. Define {{math|''f''&thinsp;(''a'' + ''bi'') {{=}} ''a''{{sup|2}} + ''b''{{sup|2}}}}, the [[field norm|norm]] of the Gaussian integer {{math|''a'' + ''bi''}}.
* {{math|'''Z'''[ω]}} (where {{math|ω}} is a [[Root of unity#General definition|primitive]] (non-[[real number|real]]) [[cube root of unity]]), the ring of [[Eisenstein integer]]s. Define {{math|''f''&thinsp;(''a'' + ''b''ω) {{=}} ''a''{{sup|2}} − ''ab'' + ''b''{{sup|2}}}}, the norm of the Eisenstein integer {{math|''a'' + ''b''ω}}.
*{{math|''K''[''X'']}}, the [[polynomial ring|ring of polynomials]] over a [[field (mathematics)|field]] {{mvar|K}}. For each nonzero polynomial {{mvar|P}}, define {{math|''f''&thinsp;(''P'')}} to be the [[degree of a polynomial|degree]] of {{mvar|P}}.<ref>{{harvnb|Fraleigh|Katz|1967|p=377, Example 2}}</ref>
*{{math|''K''{{brackets|''X''}}}}, the ring of [[formal power series]] over the field {{mvar|K}}. For each nonzero [[power series]] {{mvar|P}}, define {{math|''f''&thinsp;(''P'')}} as the [[order (power series)|order]] of {{mvar|P}}, that is the degree of the smallest power of {{mvar|X}} occurring in {{mvar|P}}. In particular, for two nonzero power series {{mvar|P}} and {{mvar|Q}}, {{math|''f''&thinsp;(''P'') ≤ ''f''&thinsp;(''Q'')}} if and only if {{mvar|P}} [[Formal power series#Dividing series|divides]] {{mvar|Q}}.
*Any [[discrete valuation ring]]. Define {{math|''f''&thinsp;(''x'')}} to be the highest power of the [[maximal ideal]] {{mvar|M}} containing {{mvar|x}}. Equivalently, let {{mvar|g}} be a generator of {{mvar|M}}, and {{mvar|v}} be the unique integer such that {{mvar|g{{hairsp}}{{sup|v}}}} is an [[associated elements|associate]] of {{mvar|x}}, then define {{math|''f''&thinsp;(''x'') {{=}} ''v''}}. The previous example {{math|''K''{{brackets|''X''}}}} is a special case of this.
*A [[Dedekind domain]] with finitely many [[zero ideal|nonzero]] [[prime ideal]]s {{math|''P''{{sub|1}}, ..., ''P{{sub|n}}''}}.  Define <math>f(x) = \sum_{i=1}^n v_i(x)</math>, where {{mvar|v{{sub|i}}}} is the [[discrete valuation]] corresponding to the ideal {{mvar|P{{sub|i}}}}.<ref>{{Cite journal|last=Samuel|first=Pierre|date=1 October 1971|title=About Euclidean rings|journal=Journal of Algebra|volume=19|issue=2|pages=282–301 (p. 285)|doi=10.1016/0021-8693(71)90110-4|issn=0021-8693|doi-access=free}}</ref>

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 [[coefficient]]s, or the number ring {{math|'''Z'''[{{hairsp|{{sqrt|&minus;5}}}}]}}.
* The [[ring of integers]] of {{math|'''Q'''({{hairsp|{{sqrt|−19}}}})}}, consisting of the numbers {{math|{{sfrac|''a'' + ''b''{{sqrt|&minus;19}}|2}}}} where {{mvar|a}} and {{mvar|b}} are integers and both even or both odd. It is a principal ideal domain that is not Euclidean.This was proved by [[Theodore Motzkin]] and was the first case known.<ref>{{Cite journal |last=Motzkin |first=Th |date=December 1949 |title=The Euclidean algorithm |url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-55/issue-12/The-Euclidean-algorithm/bams/1183514381.full |journal=Bulletin of the American Mathematical Society |volume=55 |issue=12 |pages=1142–1146 |doi=10.1090/S0002-9904-1949-09344-8 |issn=0002-9904|doi-access=free }}</ref>
* The ring {{math|1=''A'' = '''R'''[''X'', ''Y'']/(''X''<sup>&thinsp;2</sup> + ''Y''<sup>&thinsp;2</sup> + 1)}} is also a principal ideal domain<ref>
{{cite book|last=Pierre|first=Samuel|url=http://www.math.tifr.res.in/~publ/ln/tifr30.pdf|title=Lectures on Unique Factorization Domains|date=1964|publisher=Tata Institute of Fundamental Research|isbn= |pages=27–28|author-link=}}
</ref> that is not Euclidean. To see that it is not a Euclidean domain, it suffices to show that for every non-zero prime <math>p\in A</math>, the map <math>A^\times\to(A/p)^\times</math> induced by the quotient map <math>A\to A/p</math> is not [[surjective]].<ref>
{{cite web
 |url=https://math.stackexchange.com/a/864627
 |title=Quotient of polynomials, PID but not Euclidean domain?
 |last=
 |first=
 |date=
 |website=
 |publisher=
 |access-date=
 |quote=}}
</ref>
==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 (ring theory)|ideal]] of ''R'' then any element ''a'' of ''I''&nbsp;\&thinsp;{0} with minimal value (on that set) of ''f''(''a'') is a generator of ''I''.<ref>{{harvnb|Fraleigh|Katz|1967|p=377, Theorem 7.4}}</ref> 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 [[mathematical proof|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 element]]s.
* 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 (logic)|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]] for computing the quotient and the remainder, then an [[extended Euclidean algorithm]] can be defined exactly as in the case of integers.<ref>{{harvnb|Fraleigh|Katz|1967|p=380, Theorem 7.7}}</ref>
*If a Euclidean domain is not a field then it has a non-unit 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 <math>\mathbf{Q}(\sqrt{d}\,)</math> is a PID which is {{em|not}} Euclidean (because it doesn't have this property), but the cases ''d'' = −1, −2, −3, −7, −11 {{em|are}} Euclidean.<ref>{{Citation
  | last = Motzkin | first = Theodore | author-link = Theodore Motzkin
  | title = The Euclidean algorithm
  | journal = [[Bulletin of the American Mathematical Society]]
  | volume = 55 | issue = 12 | pages = 1142–6 | year = 1949
  | url = http://projecteuclid.org/handle/euclid.bams/1183514381
  | doi = 10.1090/S0002-9904-1949-09344-8 | zbl=0035.30302
| doi-access = free}}</ref>

However, in many [[finite extension]]s of '''Q''' with [[trivial group|trivial]] [[Ideal class group|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 [[field extension|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.<ref>{{Citation
  | last = Weinberger | first = Peter J. | author-link = Peter J. Weinberger
  | title = On Euclidean rings of algebraic integers
  | journal = Proceedings of Symposia in Pure Mathematics
  | publisher = AMS
  | volume = 24 | pages = 321–332 | year = 1973
| doi = 10.1090/pspum/024/0337902 | isbn = 9780821814246 }}</ref>
In particular this applies to the case of [[totally real field|totally real]] [[quadratic field|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 [[Dirichlet's unit theorem|unit rank]] strictly greater than three, then the ring of integers is Euclidean.<ref>{{Citation
  | last1 = Harper | first1 = Malcolm
  | last2 = Murty | first2 = M. Ram | author2-link = M. Ram Murty
  | title = Euclidean rings of algebraic integers
  | journal = Canadian Journal of Mathematics
  | volume = 56 | issue = 1 | pages = 71–76 | year = 2004
  | url = http://www.mast.queensu.ca/~murty/harper-murty.pdf
  | doi = 10.4153/CJM-2004-004-5
| citeseerx = 10.1.1.163.7917}}</ref>
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 of a field extension|degree]] greater than 8 then the ring of integers is necessarily Euclidean.
<!--
== Euclidean domains according to Motzkin and Samuel ==
-->

== Norm-Euclidean fields ==

[[Algebraic number field]]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 [[Conjugate element (field theory)|conjugates]] of ''α''.  This norm maps the [[ring of integers]] of a number field ''K'', say ''O''<sub>''K''</sub>, to the nonnegative [[Integer|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''.<ref name="RibAlgNum">{{cite book | title=Algebraic Numbers | publisher=Wiley-Interscience | author=Ribenboim, Paulo | year=1972 | isbn=978-0-471-71804-8}}</ref><ref name="HardyWright">{{cite book |first1=G.H. |last1=Hardy |first2=E.M. |last2=Wright |first3=Joseph |last3=Silverman |first4=Andrew |last4=Wiles |title=An Introduction to the Theory of Numbers |url=https://books.google.com/books?id=P6uTBqOa3T4C&pg=PP1 |date=2008 |publisher=Oxford University Press |edition=6th |isbn=978-0-19-921986-5 }}</ref>  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 ideal domain|principal]] and therefore not Euclidean, such as the integers of <math>\mathbf{Q}(\sqrt{-5}\,)</math>
*Those that are principal and not Euclidean, such as the integers of <math>\mathbf{Q}(\sqrt{-19}\,)</math>
*Those that are Euclidean and not norm-Euclidean, such as the integers of <math>\mathbf{Q}(\sqrt{69}\,)</math><ref>{{cite journal | last=Clark | first=David A. | title=A quadratic field which is Euclidean but not norm-Euclidean | journal=[[Manuscripta Mathematica]] | volume=83 | number=3–4 | pages=327–330 | year=1994 | doi = 10.1007/BF02567617 | zbl=0817.11047 | citeseerx=10.1.1.360.6129 }}</ref>
*Those that are norm-Euclidean, such as [[Gaussian integer]]s (integers of <math>\mathbf{Q}(\sqrt{-1}\,)</math>)

The norm-Euclidean [[quadratic field]]s have been fully classified; they are <math>\mathbf{Q}(\sqrt{d}\,)</math> where <math>d</math> takes the values
:−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 {{OEIS|id=A048981}}.<ref>{{cite book | last = LeVeque | first = William J. | author-link = William J. LeVeque | title = Topics in Number Theory|volume=I and II | publisher = Dover | year = 2002 | orig-year = 1956 | isbn = 978-0-486-42539-9 | zbl = 1009.11001 | pages = [https://archive.org/details/topicsinnumberth0000leve/page/ II:57,81] | url = https://archive.org/details/topicsinnumberth0000leve/page/ }}</ref>

Every Euclidean imaginary quadratic field is norm-Euclidean and is one of the five first fields in the preceding list.
<!--
== Euclidean rings with zero-divisors ==
== ''k''-stage Euclidean domains ==
== Euclidean ideal classes ==
-->

== See also ==
*[[Valuation (algebra)]]

== Notes ==
<references/>

== References ==
*{{cite book |first1=John B. |last1=Fraleigh |first2=Victor J. |last2=Katz |title=A first course in abstract algebra |publisher=Addison-Wesley |edition=5th |year=1967 |isbn=0-201-53467-3 }}
*{{cite journal |first=Pierre |last=Samuel |title=About Euclidean rings |journal=Journal of Algebra |volume=19 |issue=2 |pages=282–301 |year=1971 |doi=10.1016/0021-8693(71)90110-4 |doi-access=free }}
{{DEFAULTSORT:Euclidean Domain}}
[[Category:Ring theory]]
[[Category:Commutative algebra]]
[[Category:Euclid|Domain]]