Editing Euclidean algorithm (section)

== Generalizations ==
Although the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers), it may be generalized to the real numbers, and to other mathematical objects, such as [[polynomial]]s,<ref name="Lang_1984"/> [[quadratic integer]]s<ref name="weinberger"/> and [[Hurwitz quaternion]]s.<ref name="stillwell151-152"/> In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely into [[irreducible element]]s, the counterparts of prime numbers. Unique factorization is essential to many proofs of number theory.

=== Rational and real numbers ===
Euclid's algorithm can be applied to [[real number]]s, as described by Euclid in Book 10 of his ''[[Euclid's Elements|Elements]]''. The goal of the algorithm is to identify a real number {{mvar|g}} such that two given real numbers, {{mvar|a}} and {{mvar|b}}, are integer multiples of it: {{math|1=''a'' = ''mg''}} and {{math|1=''b'' = ''ng''}}, where {{mvar|m}} and {{mvar|n}} are [[integer]]s.<ref name="Weil_1983" /> This identification is equivalent to finding an [[integer relation algorithm|integer relation]] among the real numbers {{mvar|a}} and {{mvar|b}}; that is, it determines integers {{mvar|s}} and {{mvar|t}} such that {{math|1=''sa'' + ''tb'' = 0}}. If such an equation is possible, ''a'' and ''b'' are called commensurable lengths, otherwise they are [[Commensurability (mathematics)|incommensurable lengths]].<ref>{{cite book | last1 = Boyer | first1 = C. B. | last2 = Merzbach | first2 = U. C. | author2-link = Uta Merzbach | year = 1991 | title = A History of Mathematics | edition = 2nd | publisher = Wiley | location = New York | isbn = 0-471-54397-7 | pages = [https://archive.org/details/historyofmathema00boye/page/116 116–117] | url = https://archive.org/details/historyofmathema00boye/page/116 }}</ref><ref>{{cite book | author-link = Florian Cajori|last=Cajori|first= F | year = 1894 | title = A History of Mathematics | url = https://archive.org/details/in.ernet.dli.2015.73802| publisher = Macmillan | location = New York | page = [https://archive.org/details/in.ernet.dli.2015.73802/page/n78 70]}} Reprinted, Dover Publications, 2004, {{isbn|0-486-43874-0}}</ref>

The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders {{math|''r''<sub>''k''</sub>}} are real numbers, although the quotients {{math|''q''<sub>''k''</sub>}} are integers as before. Second, the algorithm is not guaranteed to end in a finite number {{mvar|N}} of steps. If it does, the fraction {{math|''a''/''b''}} is a rational number, i.e., the ratio of two integers
: <math>\frac{a}{b} = \frac{mg}{ng} = \frac{m}{n},</math>
and can be written as a finite continued fraction {{math|1=[''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, ..., ''q''<sub>''N''</sub>]}}. If the algorithm does not stop, the fraction {{math|''a''/''b''}} is an [[irrational number]] and can be described by an infinite continued fraction {{math|1=[''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …]}}.<ref>{{cite book|title=Algorithmic Cryptanalysis|first=Antoine|last=Joux|publisher=CRC Press|year=2009|isbn=9781420070033|url=https://books.google.com/books?id=buQajqt-_iUC&pg=PA33|page=33}}</ref> Examples of infinite continued fractions are the [[golden ratio]] {{math|1=''φ'' = [1; 1, 1, ...]}} and the [[square root of 2|square root of two]], {{math|1={{sqrt|2}} = [1; 2, 2, ...]}}.<ref>{{cite book|title=Mathematical Omnibus: Thirty Lectures on Classic Mathematics|first1=D. B.|last1=Fuks|first2=Serge|last2=Tabachnikov|author-link2=Sergei Tabachnikov|publisher=American Mathematical Society|year=2007|isbn=9780821843161|page=13|url=https://books.google.com/books?id=IiG9AwAAQBAJ&pg=PA13}}</ref> The algorithm is unlikely to stop, since [[almost all]] ratios {{math|''a''/''b''}} of two real numbers are irrational.<ref>{{cite book|title=The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes|first=David|last=Darling|author-link=David J. Darling|publisher=John Wiley & Sons|year=2004|isbn=9780471667001|url=https://books.google.com/books?id=HrOxRdtYYaMC&pg=PA175|page=175|contribution=Khintchine's constant}}</ref>

An infinite continued fraction may be truncated at a step {{math|1=''k'' [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, ..., ''q''<sub>''k''</sub>]}} to yield an approximation to {{math|''a''/''b''}} that improves as {{mvar|k}} is increased. The approximation is described by [[Convergent (continued fraction)|convergents]] {{math|''m''<sub>''k''</sub>/''n''<sub>''k''</sub>}}; the numerator and denominators are coprime and obey the [[recurrence relation]]
: <math>\begin{align}
   m_k &= q_k m_{k-1} + m_{k-2} \\
   n_k &= q_k n_{k-1} + n_{k-2},
 \end{align}</math>
where {{math|1=''m''<sub>−1</sub> = ''n''<sub>−2</sub> = 1}} and {{math|1=''m''<sub>−2</sub> = ''n''<sub>−1</sub> = 0}} are the initial values of the recursion. The convergent {{math|''m''<sub>''k''</sub>/''n''<sub>''k''</sub>}} is the best [[rational number]] approximation to {{math|''a''/''b''}} with denominator {{math|''n''<sub>''k''</sub>}}:<ref>{{cite book|title=Explorations in Quantum Computing|first=Colin P.|last=Williams|publisher=Springer|year=2010|isbn=9781846288876|url=https://books.google.com/books?id=QE8S--WjIFwC&pg=PA277|pages=277–278}}</ref>
: <math> \left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}.</math>

=== Polynomials ===
{{main|Polynomial greatest common divisor}}
Polynomials in a single variable ''x'' can be added, multiplied and factored into [[irreducible polynomial]]s, which are the analogs of the prime numbers for integers. The greatest common divisor polynomial {{math|''g''(''x'')}} of two polynomials {{math|''a''(''x'')}} and {{math|''b''(''x'')}} is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm.<ref name="Lang_1984" >{{cite book | author-link = Serge Lang|last=Lang|first= S. | year = 1984 | title = Algebra | edition = 2nd | publisher = Addison–Wesley | location = Menlo Park, CA | isbn = 0-201-05487-6 | pages = 190–194}}</ref> The basic procedure is similar to that for integers. At each step {{mvar|k}}, a quotient polynomial {{math|''q''<sub>''k''</sub>(''x'')}} and a remainder polynomial {{math|''r''<sub>''k''</sub>(''x'')}} are identified to satisfy the recursive equation
: <math>r_{k-2}(x) = q_k(x)r_{k-1}(x) + r_k(x),</math>
where {{math|1=''r''<sub>−2</sub>(''x'') = ''a''(''x'')}} and {{math|1=''r''<sub>−1</sub>(''x'') = ''b''(''x'')}}. Each quotient polynomial is chosen such that each remainder is either zero or has a degree that is smaller than the degree of its predecessor: {{math|deg[''r''<sub>''k''</sub>(''x'')] &lt; deg[''r''<sub>''k''−1</sub>(''x'')]}}. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The last nonzero remainder is the greatest common divisor of the original two polynomials, {{math|''a''(''x'')}} and {{math|''b''(''x'')}}.<ref>{{Harvnb|Cox|Little|O'Shea|1997|pp=37–46}}</ref>

For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials
: <math>\begin{align}
   a(x) &= x^4 - 4x^3 + 4x^2 - 3x + 14 = (x^2 - 5x + 7)(x^2 + x + 2) \qquad \text{and}\\
   b(x) &= x^4 + 8x^3 + 12x^2 + 17x + 6 = (x^2 + 7x + 3)(x^2 + x + 2).
 \end{align}</math>

[[polynomial long division|Dividing]] {{math|''a''(''x'')}} by {{math|''b''(''x'')}} yields a remainder {{math|1=''r''<sub>0</sub>(''x'') = ''x''<sup>3</sup> + (2/3)''x''<sup>2</sup> + (5/3)''x'' − (2/3)}}. In the next step, {{math|''b''(''x'')}} is divided by {{math|''r''<sub>0</sub>(''x'')}} yielding a remainder {{math|1=''r''<sub>1</sub>(''x'') = ''x''<sup>2</sup> + ''x'' + 2}}. Finally, dividing {{math|''r''<sub>0</sub>(''x'')}} by {{math|''r''<sub>1</sub>(''x'')}} yields a zero remainder, indicating that {{math|''r''<sub>1</sub>(''x'')}} is the greatest common divisor polynomial of {{math|''a''(''x'')}} and {{math|''b''(''x'')}}, consistent with their factorization.

Many of the applications described above for integers carry over to polynomials.<ref>{{Harvnb|Schroeder|2005|pp=254–259}}</ref> The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.

The polynomial Euclidean algorithm has other applications, such as [[Sturm chain]]s, a method for counting the [[zero of a function|zeros of a polynomial]] that lie inside a given [[Interval (mathematics)|real interval]].<ref>{{cite book|title=Convolutions in French Mathematics, 1800-1840: From the Calculus and Mechanics to Mathematical Analysis and Mathematical Physics. Volume II: The Turns|first=Ivor|last=Grattan-Guinness|author-link=Ivor Grattan-Guinness|publisher=Birkhäuser|series=Science Networks: Historical Studies|volume=3|location=Basel, Boston, Berlin|year=1990|isbn=9783764322380|page=1148|url=https://books.google.com/books?id=_GgioErrbW8C&pg=PA1148|quote=Our subject here is the 'Sturm sequence' of functions defined from a function and its derivative by means of Euclid's algorithm, in order to calculate the number of real roots of a polynomial within a given interval}}</ref> This in turn has applications in several areas, such as the [[Routh–Hurwitz stability criterion]] in [[control theory]].<ref>{{cite book|title=Solving Ordinary Differential Equations I: Nonstiff Problems|series=Springer Series in Computational Mathematics|volume=8|first1=Ernst|last1=Hairer|first2=Syvert P.|last2=Nørsett|first3=Gerhard|last3=Wanner|edition=2nd|publisher=Springer|year=1993|isbn=9783540566700|pages=81ff|url=https://books.google.com/books?id=F93u7VcSRyYC&pg=PA81|contribution=The Routh–Hurwitz Criterion}}</ref>

Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fields {{math|GF(''p'')}} described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.<ref name="Lang_1984" />

=== Gaussian integers ===
[[File:Gaussian primes.svg|thumb|alt="A set of dots lying within a circle. The pattern of dots has fourfold symmetry, i.e., rotations by 90 degrees leave the pattern unchanged. The pattern can also be mirrored about four lines passing through the center of the circle: the vertical and horizontal axes, and the two diagonal lines at ±45 degrees."|Distribution of Gaussian primes {{math|''u'' + ''vi''}} in the complex plane, with norms {{math|''u''<sup>2</sup> + ''v''<sup>2</sup>}} less than 500]]

The [[Gaussian integer]]s are [[complex number]]s of the form {{math|1=''α'' = ''u'' + ''vi''}}, where {{mvar|u}} and {{mvar|v}} are ordinary [[integer]]s<ref group=note>The phrase "ordinary integer" is commonly used for distinguishing usual integers from Gaussian integers, and more generally from [[algebraic integer]]s.</ref> and {{mvar|i}} is the [[imaginary unit|square root of negative one]].<ref name="Stillwell_2003" /> By defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument [[#Bézout's identity|above]].<ref name="Gauss_1832">{{cite journal | author-link = Carl Friedrich Gauss|last=Gauss|first=C. F. | year = 1832 | title = Theoria residuorum biquadraticorum | journal = Comm. Soc. Reg. Sci. Gött. Rec. | volume = 4}} Reprinted in {{cite book|first=C. F.|last=Gauss|year=2011|chapter=Theoria residuorum biquadraticorum commentatio prima |title=Werke|volume=2|publisher=Cambridge Univ. Press|pages=65–92|doi=10.1017/CBO9781139058230.004|isbn=9781139058230}} and {{cite book|first=C. F.|last=Gauss|year=2011|chapter=Theoria residuorum biquadraticorum commentatio secunda|title=Werke|volume=2|publisher=Cambridge Univ. Press|pages=93–148|doi=10.1017/CBO9781139058230.005|isbn=9781139058230}}</ref> This unique factorization is helpful in many applications, such as deriving all [[Pythagorean triple]]s or proving [[Fermat's theorem on sums of two squares]].<ref name="Stillwell_2003">{{Harvnb|Stillwell|2003|pp=101–116}}</ref> In general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments.

The Euclidean algorithm developed for two Gaussian integers {{mvar|α}} and {{mvar|β}} is nearly the same as that for ordinary integers,<ref name="hensley">{{cite book|title=Continued Fractions|first=Doug|last=Hensley|publisher=World Scientific|year=2006|isbn=9789812564771|page=26|url=https://books.google.com/books?id=k3PVXFkweKgC&pg=PA26}}</ref> but differs in two respects. As before, we set {{math|1=''r''<sub>−2</sub> = ''α''}} and {{math|1=''r''<sub>−1</sub> = ''β''}}, and the task at each step {{mvar|k}} is to identify a quotient {{math|''q''<sub>''k''</sub>}} and a remainder {{math|''r''<sub>''k''</sub>}} such that
: <math>r_k = r_{k-2} - q_k r_{k-1},</math>
where every remainder is strictly smaller than its predecessor: {{math|{{mabs|''r''<sub>''k''</sub>}} &lt; {{mabs|''r''<sub>''k''−1</sub>}}}}. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are [[complex number]]s. The quotients {{math|''q''<sub>''k''</sub>}} are generally found by rounding the real and complex parts of the exact ratio (such as the complex number {{math|''α''/''β''}}) to the nearest integers.<ref name="hensley"/> The second difference lies in the necessity of defining how one complex remainder can be "smaller" than another. To do this, a [[norm (mathematics)|norm function]] {{math|1=''f''(''u'' + ''vi'') = ''u''<sup>2</sup> + ''v''<sup>2</sup>}} is defined, which converts every Gaussian integer {{math|''u'' + ''vi''}} into an ordinary integer. After each step {{mvar|k}} of the Euclidean algorithm, the norm of the remainder {{math|''f''(''r''<sub>''k''</sub>)}} is smaller than the norm of the preceding remainder, {{math|''f''(''r''<sub>''k''−1</sub>)}}. Since the norm is a nonnegative integer and decreases with every step, the Euclidean algorithm for Gaussian integers ends in a finite number of steps.<ref>{{cite book|title=Theory of Algebraic Integers|series=Cambridge Mathematical Library|first=Richard|last=Dedekind|author-link=Richard Dedekind|publisher=Cambridge University Press|year=1996|isbn=9780521565189|pages=22–24|url=https://books.google.com/books?id=KZRBabJY4ewC&pg=PA222}}</ref> The final nonzero remainder is {{math|gcd(''α'', ''β'')}}, the Gaussian integer of largest norm that divides both {{mvar|α}} and {{mvar|β}}; it is unique up to multiplication by a unit, {{math|±1}} or {{math|±''i''}}.<ref>{{cite book|title=Numbers and Symmetry: An Introduction to Algebra|first1=Bernard L.|last1=Johnston|first2=Fred|last2=Richman|publisher=CRC Press|year=1997|isbn=9780849303012|page=44|url=https://books.google.com/books?id=koUfrlgsmUcC&pg=PA44}}</ref>

Many of the other applications of the Euclidean algorithm carry over to Gaussian integers. For example, it can be used to solve linear Diophantine equations and Chinese remainder problems for Gaussian integers;<ref>{{cite book|title=Introduction to Number Theory|url=https://archive.org/details/introductiontonu0000adam|url-access=registration|first1=William W.|last1=Adams|first2=Larry Joel|last2=Goldstein|publisher=Prentice-Hall|year=1976|isbn=9780134912820|at=Exercise 24, p.&nbsp;205|quote=State and prove an analogue of the Chinese remainder theorem for the Gaussian integers.}}</ref> continued fractions of Gaussian integers can also be defined.<ref name="hensley"/>

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

=== Noncommutative rings ===
The Euclidean algorithm may be applied to some noncommutative rings such as the set of [[Hurwitz quaternion]]s.<ref name="stillwell151-152">{{Harvnb|Stillwell|2003|pp=151–152}}</ref><ref name=bgv>{{harvtxt|Bueso|Gómez-Torrecillas|Verschoren|2003}}; see pp. 37-38 for non-commutative extensions of the Euclidean algorithm and Corollary 4.35, p. 40, for more examples of noncommutative rings to which they apply.</ref> Let {{mvar|α}} and {{mvar|β}} represent two elements from such a ring. They have a common right divisor {{mvar|δ}} if {{math|1=''α'' = ''ξδ''}} and {{math|1=''β'' = ''ηδ''}} for some choice of {{mvar|ξ}} and {{mvar|η}} in the ring. Similarly, they have a common left divisor if {{math|1=''α'' = ''dξ''}} and {{math|1=''β'' = ''dη''}} for some choice of {{mvar|ξ}} and {{mvar|η}} in the ring. Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors.<ref name="stillwell151-152"/><ref name=bgv/> Choosing the right divisors, the first step in finding the {{math|gcd(''α'', ''β'')}} by the Euclidean algorithm can be written
: <math>\rho_0 = \alpha - \psi_0\beta = (\xi - \psi_0\eta)\delta,</math>
where {{math|''ψ''<sub>0</sub>}} represents the quotient and {{math|''ρ''<sub>0</sub>}} the remainder. Here the quotient and remainder are chosen so that (if nonzero) the remainder has {{math|''N''(''ρ''<sub>0</sub>) < ''N''(''&beta;'')}} for a "Euclidean function" ''N'' defined analogously to the Euclidean functions of [[Euclidean domain]]s in the non-commutative case.<ref name=bgv/> This equation shows that any common right divisor of {{mvar|α}} and {{mvar|β}} is likewise a common divisor of the remainder {{math|''ρ''<sub>0</sub>}}. The analogous equation for the left divisors would be
: <math>\rho_0 = \alpha - \beta\psi_0 = \delta(\xi - \eta\psi_0).</math>

With either choice, the process is repeated as above until the greatest common right or left divisor is identified. As in the Euclidean domain, the "size" of the remainder {{math|''ρ''<sub>0</sub>}} (formally, its Euclidean function or "norm") must be strictly smaller than {{mvar|β}}, and there must be only a finite number of possible sizes for {{math|''ρ''<sub>0</sub>}}, so that the algorithm is guaranteed to terminate.<ref name="entgtrg">{{cite book|title=Elementary Number Theory, Group Theory and Ramanujan Graphs|title-link=Elementary Number Theory, Group Theory and Ramanujan Graphs|volume=55|series=London Mathematical Society Student Texts|first1=Giuliana|last1=Davidoff|author1-link= Giuliana Davidoff |first2=Peter|last2=Sarnak|first3=Alain|last3=Valette|publisher=Cambridge University Press|year=2003|isbn=9780521531436|contribution=2.6 The Arithmetic of Integer Quaternions|pages=59–70|contribution-url=https://books.google.com/books?id=AlvfFDJOGZ8C&pg=PA59}}</ref>

Many results for the GCD carry over to noncommutative numbers. For example, [[Bézout's identity]] states that the right {{math|gcd(''α'', ''β'')}} can be expressed as a linear combination of {{mvar|α}} and {{mvar|β}}.<ref>{{cite book|title=Classical Theory of Algebraic Numbers|series=Universitext|publisher=Springer-Verlag|first=Paulo|last=Ribenboim|year=2001|isbn=9780387950709|page=104|url=https://books.google.com/books?id=u5443xdaNZcC&pg=PA104}}</ref> In other words, there are numbers {{mvar|σ}} and {{mvar|τ}} such that
: <math>\Gamma_\text{right} = \sigma\alpha + \tau\beta.</math>

The analogous identity for the left GCD is nearly the same:
: <math>\Gamma_\text{left} = \alpha\sigma + \beta\tau.</math>

Bézout's identity can be used to solve Diophantine equations. For instance, one of the standard proofs of [[Lagrange's four-square theorem]], that every positive integer can be represented as a sum of four squares, is based on quaternion GCDs in this way.<ref name="entgtrg"/>