The case of univariate polynomials over a field is especially important for several reasons. Firstly, it is the most elementary case and therefore appears in most first courses in algebra. Secondly, it is very similar to the case of the integers, and this analogy is the source of the notion of
Euclidean domain. A third reason is that the theory and the algorithms for the
multivariate case and for coefficients in a
unique factorization domain are strongly based on this particular case. Last but not least, polynomial GCD algorithms and derived algorithms allow one to get useful information on the roots of a polynomial, without computing them.
Euclidean division Euclidean division of polynomials, which is used in
Euclid's algorithm for computing GCDs, is very similar to
Euclidean division of integers. Its existence is based on the following theorem: Given two univariate polynomials a and b \neq 0 defined over a
field, there exist two polynomials q (the
quotient) and r (the
remainder) which satisfy a = bq + r and \deg(r) where "" denotes the degree and the degree of the zero polynomial is defined as being negative. Moreover,
q and
r are uniquely defined by these relations. The difference from Euclidean division of the integers is that, for the integers, the degree is replaced by the absolute value, and that to have uniqueness one has to suppose that
r is non-negative. The rings for which such a theorem exists are called
Euclidean domains. Like for the integers, the Euclidean division of the polynomials may be computed by the
long division algorithm. This algorithm is usually presented for paper-and-pencil computation, but it works well on computers when formalized as follows (note that the names of the variables correspond exactly to the regions of the paper sheet in a pencil-and-paper computation of long division). In the following computation "deg" stands for the degree of its argument (with the convention ), and "lc" stands for the leading coefficient, the coefficient of the highest degree of the variable. The proof of the validity of this algorithm relies on the fact that during the whole "while" loop, we have and is a non-negative integer that decreases at each iteration. Thus the proof of the validity of this algorithm also proves the validity of the Euclidean division.
Euclid's algorithm As for the integers, the Euclidean division allows us to define
Euclid's algorithm for computing GCDs. Starting from two polynomials
a and
b, Euclid's algorithm consists of recursively replacing the pair by (where "" denotes the remainder of the Euclidean division, computed by the algorithm of the preceding section), until
b = 0. The GCD is the last non zero remainder. Euclid's algorithm may be formalized in the recursive programming style as: \gcd(a,b):= \begin{cases} a & \text{if } b = 0 \\ \gcd(b, \operatorname{rem}(a,b)) & \text{otherwise}. \end{cases} In the
imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder: The sequence of the degrees of the is strictly decreasing. Thus after, at most, steps, one get a null remainder, say . As and have the same divisors, the set of the common divisors is not changed by Euclid's algorithm and thus all pairs have the same set of common divisors. The common divisors of and are thus the common divisors of and 0. Thus is a GCD of and . This not only proves that Euclid's algorithm computes GCDs but also proves that GCDs exist.
Bézout's identity and extended GCD algorithm Bézout's identity is a GCD related theorem, initially proved for the integers, which is valid for every
principal ideal domain. In the case of the univariate polynomials over a field, it may be stated as follows. The interest of this result in the case of the polynomials is that there is an efficient algorithm to compute the polynomials and . This algorithm differs from Euclid's algorithm by a few more computations done at each iteration of the loop. It is therefore called
extended GCD algorithm. Another difference with Euclid's algorithm is that it also uses the quotient, denoted "quo", of the Euclidean division instead of only the remainder. This algorithm works as follows. The proof that the algorithm satisfies its output specification relies on the fact that, for every we have r_i = a s_i + b t_i s_i t_{i+1} - t_i s_{i+1} = s_i t_{i-1} - t_i s_{i-1}, the latter equality implying s_i t_{i+1} - t_i s_{i+1} = (-1)^i. The assertion on the degrees follows from the fact that, at every iteration, the degrees of and increase at most as the degree of decreases. An interesting feature of this algorithm is that, when the coefficients of Bezout's identity are needed, one gets for free the quotient of the input polynomials by their GCD.
Arithmetic of algebraic extensions An important application of the extended GCD algorithm is that it allows one to compute division in
algebraic field extensions. Let an algebraic extension of a field , generated by an element whose minimal polynomial has degree . The elements of are usually represented by univariate polynomials over of degree less than . The addition in is simply the addition of polynomials: a+_Lb=a+_{K[X]}b. The multiplication in is the multiplication of polynomials followed by the division by : a\cdot_Lb=\operatorname{rem}(a._{K[X]}b,f). The inverse of a non zero element of is the coefficient in Bézout's identity , which may be computed by extended GCD algorithm. (the GCD is 1 because the minimal polynomial is irreducible). The degrees inequality in the specification of extended GCD algorithm shows that a further division by is not needed to get deg() In the case of univariate polynomials, there is a strong relationship between the greatest common divisors and
resultants. More precisely, the resultant of two polynomials
P,
Q is a polynomial function of the coefficients of
P and
Q which has the value zero if and only if the GCD of
P and
Q is not constant. The subresultants theory is a generalization of this property that allows characterizing generically the GCD of two polynomials, and the resultant is the 0-th subresultant polynomial. The -th
subresultant polynomial of two polynomials and is a polynomial of degree at most whose coefficients are polynomial functions of the coefficients of and , and the -th
principal subresultant coefficient is the coefficient of degree of . They have the property that the GCD of and has a degree if and only if s_0(P,Q) = \cdots = s_{d-1}(P,Q) =0, \ s_d(P,Q)\neq 0. In this case, is a GCD of and and S_0(P,Q)=\cdots=S_{d-1}(P,Q) =0. Every coefficient of the subresultant polynomials is defined as the determinant of a submatrix of the
Sylvester matrix of and . This implies that subresultants "specialize" well. More precisely, subresultants are defined for polynomials over any commutative ring
R, and have the following property. Let be a
ring homomorphism of into another commutative ring . It extends to another homomorphism, denoted also between the polynomials rings over and . Then, if and are univariate polynomials with coefficients in such that \deg(P)=\deg(\varphi(P)) and \deg(Q)=\deg(\varphi(Q)), then the subresultant polynomials and the principal subresultant coefficients of and are the image by of those of and . The subresultants have two important properties which make them fundamental for the computation on computers of the GCD of two polynomials with integer coefficients. Firstly, their definition through determinants allows bounding, through
Hadamard inequality, the size of the coefficients of the GCD. Secondly, this bound and the property of good specialization allow computing the GCD of two polynomials with integer coefficients through
modular computation and
Chinese remainder theorem (see
below).
Technical definition Let P=p_0+p_1 X+\cdots +p_m X^m,\quad Q=q_0+q_1 X+\cdots +q_n X^n. be two univariate polynomials with coefficients in a field
K. Let us denote by \mathcal{P}_i the
vector space of dimension of polynomials of degree less than . For non-negative integer such that and , let \varphi_i:\mathcal{P}_{n-i} \times \mathcal{P}_{m-i} \rightarrow \mathcal{P}_{m+n-i} be the
linear map such that \varphi_i(A,B) = AP + BQ. The
resultant of and is the determinant of the
Sylvester matrix, which is the (square) matrix of \varphi_0 on the bases of the powers of . Similarly, the -subresultant polynomial is defined in term of determinants of submatrices of the matrix of \varphi_i. Let us describe these matrices more precisely; Let for or , and for or . The
Sylvester matrix is the -matrix such that the coefficient of the -th row and the -th column is for and for : S=\begin{pmatrix} p_m & 0 & \cdots & 0 & q_n & 0 & \cdots & 0 \\ p_{m-1} & p_m & \cdots & 0 & q_{n-1} & q_n & \cdots & 0 \\ p_{m-2} & p_{m-1} & \ddots & 0 & q_{n-2} & q_{n-1} & \ddots & 0 \\ \vdots &\vdots & \ddots & p_m & \vdots &\vdots & \ddots & q_n \\ \vdots &\vdots & \cdots & p_{m-1} & \vdots &\vdots & \cdots & q_{n-1} \\ p_0 & p_1 & \cdots & \vdots & q_0 & q_1 & \cdots & \vdots \\ 0 & p_0 & \ddots & \vdots & 0 & q_0 & \ddots & \vdots \\ \vdots & \vdots & \ddots & p_1 & \vdots & \vdots & \ddots & q_1 \\ 0 & 0 & \cdots & p_0 & 0 & 0 & \cdots & q_0 \end{pmatrix}. The matrix of \varphi_i is the -submatrix of which is obtained by removing the last rows of zeros in the submatrix of the columns 1 to and to of (that is removing columns in each block and the last rows of zeros). The
principal subresultant coefficient is the determinant of the first rows of . Let be the matrix defined as follows. First we add columns of zeros to the right of the
identity matrix. Then we border the bottom of the resulting matrix by a row consisting in zeros followed by : V_i=\begin{pmatrix} 1 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ \vdots &\vdots & \ddots & \vdots & \vdots &\ddots & \vdots & 0 \\ 0 & 0 & \cdots & 1 & 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 & X^i & X^{i-1} & \cdots & 1 \end{pmatrix}. With this notation, the -th
subresultant polynomial is the determinant of the matrix product . Its coefficient of degree is the determinant of the square submatrix of
Ti consisting in its first rows and the -th row.
Sketch of the proof It is not obvious that, as defined, the subresultants have the desired properties. Nevertheless, the proof is rather simple if the properties of
linear algebra and those of polynomials are put together. As defined, the columns of the matrix are the vectors of the coefficients of some polynomials belonging to the image of \varphi_i. The definition of the -th subresultant polynomial shows that the vector of its coefficients is a linear combination of these column vectors, and thus that
Si belongs to the image of \varphi_i. If the degree of the GCD is greater than , then
Bézout's identity shows that every non zero polynomial in the image of \varphi_i has a degree larger than . This implies that . If, on the other hand, the degree of the GCD is , then Bézout's identity again allows proving that the multiples of the GCD that have a degree lower than are in the image of \varphi_i. The vector space of these multiples has the dimension and has a base of polynomials of pairwise different degrees, not smaller than . This implies that the submatrix of the first rows of the column echelon form of is the identity matrix and thus that is not 0. Thus is a polynomial in the image of \varphi_i, which is a multiple of the GCD and has the same degree. It is thus a greatest common divisor.
GCD and root finding Square-free factorization Most
root-finding algorithms behave badly with polynomials that have
multiple roots. It is therefore useful to detect and remove them before calling a root-finding algorithm. A GCD computation allows detection of the existence of multiple roots, since the multiple roots of a polynomial are the roots of the GCD of the polynomial and its
derivative. After computing the GCD of the polynomial and its derivative, further GCD computations provide the complete
square-free factorization of the polynomial, which is a factorization f = \prod_{i=1}^{\deg(f)} f_i^i where, for each , the polynomial either is 1 if does not have any root of multiplicity or is a square-free polynomial (that is a polynomial without multiple root) whose roots are exactly the roots of multiplicity of (see
Yun's algorithm). Thus the square-free factorization reduces root-finding of a polynomial with multiple roots to root-finding of several square-free polynomials of lower degree. The square-free factorization is also the first step in most
polynomial factorization algorithms.
Sturm sequence The
Sturm sequence of a polynomial with real coefficients is the sequence of the remainders provided by a variant of Euclid's algorithm applied to the polynomial and its derivative. For getting the Sturm sequence, one simply replaces the instruction r_{i+1} := \operatorname{rem}(r_{i-1},r_{i}) of Euclid's algorithm by r_{i+1} := -\operatorname{rem}(r_{i-1},r_{i}). Let be the number of changes of signs in the sequence, when evaluated at a point . Sturm's theorem asserts that is the number of real roots of the polynomial in the interval . Thus the Sturm sequence allows computing the number of real roots in a given interval. By subdividing the interval until every subinterval contains at most one root, this provides an algorithm that locates the real roots in intervals of arbitrary small length. ==GCD over a ring and its field of fractions==