Editing Euclidean algorithm (section)

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