Editing Euclidean algorithm (section)

=== Euclidean domains ===
A set of elements under two [[binary operation]]s, denoted as addition and multiplication, is called a [[Euclidean domain]] if it forms a [[commutative ring]] {{mvar|R}} and, roughly speaking, if a generalized Euclidean algorithm can be performed on them.<ref>{{Harvnb|Stark|1978|p=290}}</ref><ref>{{Harvnb|Cohn|1980|pp=104–105}}</ref> The two operations of such a ring need not be the addition and multiplication of ordinary arithmetic; rather, they can be more general, such as the operations of a [[group (mathematics)|mathematical group]] or [[monoid]]. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as [[commutative property|commutativity]], [[associative property|associativity]] and [[distributive property|distributivity]].

The generalized Euclidean algorithm requires a ''Euclidean function'', i.e., a mapping {{mvar|f}} from {{mvar|R}} into the set of nonnegative integers such that, for any two nonzero elements {{mvar|a}} and {{mvar|b}} in {{mvar|R}}, there exist {{mvar|q}} and {{mvar|r}} in {{mvar|R}} such that {{math|1=''a'' = ''qb'' + ''r''}} and {{math|''f''(''r'') &lt; ''f''(''b'')}}.<ref>{{cite book|title=Concrete Abstract Algebra: From Numbers to Gröbner Bases|first=Niels|last=Lauritzen|publisher=Cambridge University Press|year=2003|isbn=9780521534109|page=130|url=https://books.google.com/books?id=BdAbcje-TZUC&pg=PA130}}</ref> Examples of such mappings are the absolute value for integers, the degree for [[univariate polynomial]]s, and the norm for Gaussian integers [[#Gaussian integers|above]].<ref>{{harvtxt|Lauritzen|2003}}, p.&nbsp;132</ref><ref>{{harvtxt|Lauritzen|2003}}, p.&nbsp;161</ref> The basic principle is that each step of the algorithm reduces ''f'' inexorably; hence, if {{mvar|f}} can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on the [[well-order]]ing property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.<ref name="sharpe">{{cite book|title=Rings and Factorization|first=David|last=Sharpe|publisher=Cambridge University Press|year=1987|isbn=9780521337182|page=[https://archive.org/details/ringsfactorizati0000shar/page/55 55]|url=https://archive.org/details/ringsfactorizati0000shar|url-access=registration}}</ref>

The [[fundamental theorem of arithmetic]] applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely into [[irreducible element]]s. Any Euclidean domain is a [[unique factorization domain]] (UFD), although the converse is not true.<ref name="sharpe"/> The Euclidean domains and the UFD's are subclasses of the [[GCD domain]]s, domains in which a greatest common divisor of two numbers always exists.<ref>{{harvtxt|Sharpe|1987}}, p.&nbsp;52</ref> In other words, a greatest common divisor may exist (for all pairs of elements in a domain), although it may not be possible to find it using a Euclidean algorithm. A Euclidean domain is always a [[principal ideal domain]] (PID), an [[integral domain]] in which every [[ideal (ring theory)|ideal]] is a [[principal ideal]].<ref>{{harvtxt|Lauritzen|2003}}, p.&nbsp;131</ref> Again, the converse is not true: not every PID is a Euclidean domain.

The unique factorization of Euclidean domains is useful in many applications. For example, the unique factorization of the Gaussian integers is convenient in deriving formulae for all [[Pythagorean triple]]s and in proving [[Fermat's theorem on sums of two squares]].<ref name="Stillwell_2003" /> Unique factorization was also a key element in an attempted proof of [[Fermat's Last Theorem]] published in 1847 by Gabriel Lamé, the same mathematician who analyzed the efficiency of Euclid's algorithm, based on a suggestion of [[Joseph Liouville]].<ref>{{cite journal | last = Lamé |first=G. |author-link=Gabriel Lamé| year = 1847 | title = Mémoire sur la résolution, en nombres complexes, de l'équation A<sup>n</sup> + B<sup>n</sup> + C<sup>n</sup> = 0 |language=fr | journal = J. Math. Pures Appl. | volume = 12 | pages = 172–184}}</ref> Lamé's approach required the unique factorization of numbers of the form {{math|''x'' + ''ωy''}}, where {{mvar|x}} and {{mvar|y}} are integers, and {{math|1=''ω'' = ''e''<sup>2''iπ''/''n''</sup>}} is an {{mvar|n}}th root of 1, that is, {{math|1=''ω''<sup>''n''</sup> = 1}}. Although this approach succeeds for some values of {{mvar|n}} (such as {{math|1=''n'' = 3}}, the [[Eisenstein integer]]s), in general such numbers do {{em|not}} factor uniquely. This failure of unique factorization in some [[cyclotomic field]]s led [[Ernst Kummer]] to the concept of [[ideal number]]s and, later, [[Richard Dedekind]] to [[ideal (ring theory)|ideals]].<ref>{{cite book|author-link=Harold Edwards (mathematician) | last=Edwards|first=H.|title=Fermat's last theorem: a genetic introduction to algebraic number theory|year=2000|publisher=Springer|page=76}}</ref>

==== Unique factorization of quadratic integers ====

[[File:Eisenstein primes.svg|thumb|alt="A set of dots lying within a circle. The pattern of dots has sixfold symmetry, i.e., rotations by 60 degrees leave the pattern unchanged. The pattern can also be mirrored about six lines passing through the center of the circle: the vertical and horizontal axes, and the four diagonal lines at ±30 and ±60 degrees."|Distribution of Eisenstein primes {{math|''u'' + ''vω''}} in the complex plane, with norms less than 500. The number {{mvar|ω}} is a [[root of unity|cube root of 1]].]]

The [[quadratic integer]] rings are helpful to illustrate Euclidean domains. Quadratic integers are generalizations of the Gaussian integers in which the [[imaginary unit]] ''i'' is replaced by a number {{mvar|ω}}. Thus, they have the form {{math|''u'' + ''vω''}}, where {{mvar|u}} and {{mvar|v}} are integers and {{mvar|ω}} has one of two forms, depending on a parameter {{mvar|D}}. If {{mvar|D}} does not equal a multiple of four plus one, then
: <math>\omega = \sqrt D .</math>

If, however, {{math|''D''}} does equal a multiple of four plus one, then
: <math>\omega = \frac{1 + \sqrt{D}}{2} .</math>

If the function {{mvar|f}} corresponds to a [[field norm|norm]] function, such as that used to order the Gaussian integers [[#Gaussian integers|above]], then the domain is known as ''[[Norm-Euclidean field|norm-Euclidean]]''. The norm-Euclidean rings of quadratic integers are exactly those where {{mvar|D}} is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73.<ref>{{Harvnb|Cohn|1980|pp=104–110}}</ref><ref>{{cite book | last = LeVeque | first = W. J. | author-link = William J. LeVeque | title = Topics in Number Theory, Volumes I and II | publisher = Dover Publications | location = New York | year = 2002 | orig-year = 1956 | isbn = 978-0-486-42539-9 | zbl = 1009.11001 | pages = II:57,81 | url = https://archive.org/details/topicsinnumberth0000leve }}</ref> The cases {{math|1=''D'' = −1}} and {{math|1=''D'' = −3}} yield the [[Gaussian integer]]s and [[Eisenstein integer]]s, respectively.

If {{mvar|f}} is allowed to be any Euclidean function, then the list of possible values of {{mvar|D}} for which the domain is Euclidean is not yet known.<ref name="Clark_1994">{{cite journal | last=Clark | first=D. A. | year = 1994 | title = A quadratic field which is Euclidean but not norm-Euclidean | journal = Manuscripta Mathematica | volume = 83 | issue=1 | pages = 327–330 | doi = 10.1007/BF02567617 | doi-access=free | zbl=0817.11047 | s2cid=895185 }}</ref> The first example of a Euclidean domain that was not norm-Euclidean (with {{math|1=''D'' = 69}}) was published in 1994.<ref name="Clark_1994" /> In 1973, Weinberger proved that a quadratic integer ring with {{math|''D'' &gt; 0}} is Euclidean if, and only if, it is a [[principal ideal domain]], provided that the [[generalized Riemann hypothesis]] holds.<ref name="weinberger">{{cite journal | last = Weinberger | first = P. | title = On Euclidean rings of algebraic integers | journal = Proc. Sympos. Pure Math. | series = Proceedings of Symposia in Pure Mathematics | year = 1973 | volume = 24 | pages = 321–332| location = Providence, Rhode Island | doi = 10.1090/pspum/024/0337902 | isbn = 9780821814246 }}</ref>