Editing Extended Euclidean algorithm (section)

== Polynomial extended Euclidean algorithm ==
{{see also|Polynomial greatest common divisor#Bézout's identity and extended GCD algorithm}}

For [[univariate polynomial]]s with coefficients in a [[field (mathematics)|field]], everything works similarly, Euclidean division, Bézout's identity and extended Euclidean algorithm. The first difference is that, in the Euclidean division and the algorithm, the inequality <math>0\le r_{i+1}<|r_i|</math> has to be replaced by an inequality on the degrees <math>\deg r_{i+1}<\deg r_i.</math> Otherwise, everything which precedes in this article remains the same, simply by replacing integers by polynomials.

A second difference lies in the bound on the size of the Bézout coefficients provided by the extended Euclidean algorithm, which is more accurate in the polynomial case, leading to the following theorem.

''If a and b are two nonzero polynomials, then the extended Euclidean algorithm produces the unique pair of polynomials'' (''s'', ''t'') ''such that''
:<math>as+bt=\gcd(a,b)</math>
''and''
:<math>\deg s < \deg b - \deg (\gcd(a,b)), \quad \deg t < \deg a - \deg (\gcd(a,b)).</math>

A third difference is that, in the polynomial case, the greatest common divisor is defined only up to the multiplication by a non zero constant. There are several ways to define unambiguously a greatest common divisor.

In mathematics, it is common to require that the greatest common divisor be a [[monic polynomial]]. To get this, it suffices to divide every element of the output by the [[leading coefficient]] of <math>r_{k}.</math> This allows that, if ''a'' and ''b'' are coprime, one gets 1 in the right-hand side of Bézout's inequality. Otherwise, one may get any non-zero constant. In [[computer algebra]], the polynomials commonly have integer coefficients, and this way of normalizing the greatest common divisor introduces too many fractions to be convenient.

The second way to normalize the greatest common divisor in the case of polynomials with integer coefficients is to divide every output by the [[content (algebra)|content]] of <math>r_{k},</math> to get a [[primitive polynomial (ring theory)|primitive]] greatest common divisor. If the input polynomials are coprime, this normalisation also provides a greatest common divisor equal to 1. The drawback of this approach is that a lot of fractions should be computed and simplified during the computation.

A third approach consists in extending the algorithm of [[Polynomial greatest common divisor#Subresultant pseudo-remainder sequence|subresultant pseudo-remainder sequence]]s in a way that is similar to the extension of the Euclidean algorithm to the extended Euclidean algorithm. This allows that, when starting with polynomials with integer coefficients, all polynomials that are computed have integer coefficients. Moreover, every computed remainder <math>r_i</math> is a [[subresultant|subresultant polynomial]]. In particular, if the input polynomials are coprime, then the Bézout's identity becomes 
:<math>as+bt=\operatorname{Res}(a,b),</math>
where <math>\operatorname{Res}(a,b)</math> denotes the [[resultant]] of ''a'' and ''b''. In this form of Bézout's identity, there is no denominator in the formula. If one divides everything by the resultant one gets the classical Bézout's identity, with an explicit common denominator for the rational numbers that appear in it.