|
This method can even be used for [[real number|real]] inputs ''a'' and ''b''; if ''a''/''b'' is [[irrational number|irrational]], then the Euclidean algorithm will not terminate, but the computed sequence of quotients still represents the (now infinite) continued fraction representation of ''a''/''b''.
boring boring broing lol
== Generalization to Euclidean domains ==
The Euclidean algorithm can be applied to some [[ring (mathematics)|rings]], not just the [[integers]]. The most general context in which the algorithm terminates with the greatest common divisor is the so-called [[Euclidean ___domain]]. These include the [[Gaussian integers]] and [[polynomial ring]]s over a [[field (mathematics)|field]].
As an example, consider the ring of polynomials with [[rational number|rational]] coefficients. In this ring, division with remainder is carried out using [[polynomial long division|long division]], also known as [[synthetic division]]. The resulting polynomials are then made [[monic polynomial|monic]] by factoring out the leading coefficient.
We calculate the greatest common divisor of
: <math>x^4-4x^3+4x^2-3x+14 = (x^2-5x+7)(x^2+x+2)</math>
and
: <math>x^4+8x^3+12x^2+17x+6 = (x^2+7x+3)(x^2+x+2).</math>
Following the algorithm gives these values:
{|class=wikitable
!a!!b
|-
|<math>x^4-4x^3+4x^2-3x+14</math>||<math>x^4+8x^3+12x^2+17x+6</math>
|-
|<math>x^3+\frac{2}{3}x^2+\frac{5}{3}x-\frac{2}{3}</math>||<math>x^4-4x^3+4x^2-3x+14</math>
|-
|<math>x^2+x+2</math>||<math>x^3+\frac{2}{3}x^2+\frac{5}{3}x-\frac{2}{3}</math>
|-
|<math>0</math>||<math>x^2+x+2</math>
|-
|}
This agrees with the explicit factorization. For general Euclidean domains, the proof of correctness is by induction on some size function. For the integers, this size function is just the identity. For rings of polynomials over a field, it is the degree of the polynomial (note that each step in the above table reduces the degree by one).
==[[C programming language|C]]/[[C++]]/[[Java programming language|Java]] implementation==
| 