Editing Euclidean algorithm (section)

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