Editing Euclidean algorithm (section)

==== 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>