In algebra, the greatest common divisor (frequently abbreviated GCD or gcd) of two polynomials is a polynomial, of the highest possible degree, which is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers. In the important case of univariate polynomials over a field, the polynomial GCD may be computed as for the integer GCD, with the Euclidean algorithm using long division. The polynomial GCD is defined only up to the multiplication by an invertible constant. The similarity between integer GCD and polynomial GCD allows extending to univariate polynomials all the properties that may be deduced from the Euclidean algorithm and Euclidean division. Moreover, the polynomial GCD has specific properties that make it a fundamental notion in various areas of algebra. Typically, the roots of the GCD of two polynomials are the common roots of the two polynomials, and this provides information on the roots without computing them. For example, the multiple roots of a polynomial are the roots of the GCD of the polynomial and its derivative, and further GCD computations allow computing the square-free factorization of the polynomial, which provides polynomials whose roots are the roots of a given multiplicity of the original polynomial. The greatest common divisor may be defined and exists, more generally, for multivariate polynomials over a field, over the ring of integers, and over any unique factorization domain. There exist algorithms to compute them as soon as one has a GCD algorithm in the ring of coefficients. These algorithms proceed by a recursion on the number of variables to reduce the problem to a variant of the Euclidean algorithm. They are a fundamental tool in computer algebra, because computer algebra systems use them systematically to simplify fractions: this was the motivation for much of the modern theory of polynomial GCD.
General definition Let p and q be polynomials with coefficients in an integral domain F, typically a field or the integers. A greatest common divisor of p and q is a polynomial d that divides p and q, and such that every common divisor of p and q also divides d. Every pair of polynomials (not both zero) has a GCD if and only if F is a unique factorization domain. If F is a field and p and q are not both zero, a polynomial d is a greatest common divisor if and only if it divides both p and q, and it has the greatest degree among the polynomials having this property. If p = q = 0, the GCD is 0; however some authors consider that it is not defined in this case. The greatest common divisor of p and q is usually denoted gcd(p, q). The greatest common divisor is unique only up to multiplication by an invertible constant. That is, if d is a GCD of p and q, then the polynomial c is another GCD if and only if there is an invertible element u of F such that
c = u d and d = u − 1 c . {\displaystyle c=ud\quad {\text{ and }}\quad d=u^{-1}c.} In the case of the integers, this ambiguity may be removed by choosing the unique positive GCD, rather than its negative. For univariate polynomials over a field, one can instead choose the standard GCD to be the unique monic choice (having leading coefficient 1), but over more general coefficient rings there is no standard choice. Therefore, equalities like d = gcd(p, q) or gcd(p, q) = gcd(r, s) should be understood to mean "d is a GCD of p and q" and "p and q have the same set of GCDs as r and s". In particular, gcd(p, q) = 1 means that the invertible constants are the only common divisors: in this case, by analogy with the ring of integers, one says that p and q are coprime polynomials.
Properties As stated above, the GCD of two polynomials exists if the coefficients belong either to a field, the ring of the integers, or more generally to a unique factorization domain. If c is any common divisor of p and q, then c divides their GCD.
gcd ( p , q ) = gcd ( q , p ) . {\displaystyle \gcd(p,q)=\gcd(q,p).}
gcd ( p , q ) = gcd ( q , p + r q ) {\displaystyle \gcd(p,q)=\gcd(q,p+rq)} for any polynomial r. This property is at the basis of the proof of Euclidean algorithm. For any invertible element k of the ring of the coefficients, gcd ( p , q ) = gcd ( p , k q ) {\displaystyle \gcd(p,q)=\gcd(p,kq)} . Hence gcd ( p , q ) = gcd ( a 1 p + b 1 q , a 2 p + b 2 q ) {\displaystyle \gcd(p,q)=\gcd(a_{1}p+b_{1}q,a_{2}p+b_{2}q)} for any scalars a 1 , b 1 , a 2 , b 2 {\displaystyle a_{1},b_{1},a_{2},b_{2}} such that a 1 b 2 − a 2 b 1 {\displaystyle a_{1}b_{2}-a_{2}b_{1}} is invertible. If gcd ( p , r ) = 1 {\displaystyle \gcd(p,r)=1} , then gcd ( p , q ) = gcd ( p , q r ) {\displaystyle \gcd(p,q)=\gcd(p,qr)} . If gcd ( q , r ) = 1 {\displaystyle \gcd(q,r)=1} , then gcd ( p , q r ) = gcd ( p , q ) gcd ( p , r ) {\displaystyle \gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)} . For two univariate polynomials p and q over a field, there exist polynomials a and b, such that gcd ( p , q ) = a p + b q {\displaystyle \gcd(p,q)=ap+bq} and gcd ( p , q ) {\displaystyle \gcd(p,q)} divides every such linear combination of p and q (Bézout's identity). The greatest common divisor of three or more polynomials may be defined similarly as for two polynomials. It may be computed recursively from GCD's of two polynomials by the identities: gcd ( p , q , r ) = gcd ( p , gcd ( q , r ) ) , {\displaystyle \gcd(p,q,r)=\gcd(p,\gcd(q,r)),} and gcd ( p 1 , p 2 , … , p n ) = gcd ( p 1 , gcd ( p 2 , … , p n ) ) . {\displaystyle \gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})).}
GCD by hand computation There are several ways to find the greatest common divisor of two polynomials. Two of them are:
Factorization of polynomials, in which one finds the factors of each expression, then selects the set of common factors held by all from within each set of factors. This method may be useful only in simple cases, as factoring is usually more difficult than computing the greatest common divisor. The Euclidean algorithm, which can be used to find the GCD of two polynomials in the same manner as for two numbers.
Factoring To find the GCD of two polynomials using factoring, simply factor the two polynomials completely. Then, take the product of all common factors. At this stage, we do not necessarily have a monic polynomial, so finally multiply this by a constant to make it a monic polynomial. This will be the GCD of the two polynomials as it includes all common divisors and is monic. Example one: Find the GCD of x2 + 7x + 6 and x2 − 5x − 6.
Thus, their GCD is x + 1.
Euclidean algorithm Factoring polynomials can be difficult, especially if the polynomials have a large degree. The Euclidean algorithm is a method that works for any pair of polynomials. It makes repeated use of Euclidean division. When using this algorithm on two numbers, the size of the numbers decreases at each stage. With polynomials, the degree of the polynomials decreases at each stage. The last nonzero remainder, made monic if necessary, is the GCD of the two polynomials. More specifically, for finding the gcd of two polynomials a(x) and b(x), one can suppose b ≠ 0 (otherwise, the GCD is a(x)), and
deg ( b ( x ) ) ≤ deg ( a ( x ) ) . {\displaystyle \deg(b(x))\leq \deg(a(x))\,.}
The Euclidean division provides two polynomials q(x), the quotient and r(x), the remainder such that
a ( x ) = q 0 ( x ) b ( x ) + r 0 ( x ) and deg ( r 0 ( x ) ) < deg ( b ( x ) ) {\displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)\quad {\text{and}}\quad \deg(r_{0}(x))<\deg(b(x))}
A polynomial g(x) divides both a(x) and b(x) if and only if it divides both b(x) and r0(x). Thus
gcd ( a ( x ) , b ( x ) ) = gcd ( b ( x ) , r 0 ( x ) ) . {\displaystyle \gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).}
Setting
a 1 ( x ) = b ( x ) , b 1 ( x ) = r 0 ( x ) , {\displaystyle a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),}
one can repeat the Euclidean division to get new polynomials q1(x), r1(x), a2(x), b2(x) and so on. At each stage we have
deg ( a k + 1 ) + deg ( b k + 1 ) < deg ( a k ) + deg ( b k ) , {\displaystyle \deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),}
so the sequence will eventually reach a point at which
b N ( x ) = 0 {\displaystyle b_{N}(x)=0}
and one has got the GCD:
gcd ( a , b ) = gcd ( a 1 , b 1 ) = ⋯ = gcd ( a N , 0 ) = a N . {\displaystyle \gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.}
Example: finding the GCD of x2 + 7x + 6 and x2 − 5x − 6:
Since 12 x + 12 is the last nonzero remainder, it is a GCD of the original polynomials, and the monic GCD is x + 1. In this example, it is not difficult to avoid introducing denominators by factoring out 12 before the second step. This can always be done by using pseudo-remainder sequences, but, without care, this may introduce very large integers during the computation. Therefore, for computer computation, other algorithms are used, that are described below. This method works only if one can test the equality to zero of the coefficients that occur during the computation. So, in practice, the coefficients must be integers, rational numbers, elements of a finite field, or must belong to some finitely generated field extension of one of the preceding fields. If the coefficients are floating-point numbers that represent real numbers that are known only approximately, then one must know the degree of the GCD for having a numerically stable result; in this case other techniques may be used, usually based on singular value decomposition.
Univariate polynomials with coefficients in a field The basic case of univariate polynomials over a field is especially important. It is the simplest example beyond the ring of integers, and this analogy is the source of the notion of Euclidean domain. The theory and algorithms for the multivariate case and for coefficients in a unique factorization domain depend heavily on the basic case. 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 {\textstyle a} and b ≠ 0 {\displaystyle b\neq 0} defined over a field, there exist two polynomials q {\displaystyle q} (the quotient) and r {\displaystyle r} (the remainder) which satisfy
a = b q + r {\displaystyle a=bq+r}
and
deg ( r ) < deg ( b ) , {\displaystyle \deg(r)<\deg(b),}
where "deg(...)" 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 deg(0) < 0), and "lc" stands for the leading coefficient, the coefficient of the highest degree of the variable. Euclidean division Input: a and b ≠ 0 two polynomials in the variable x; Output: q, the quotient, and r, the remainder; begin
q := 0 r := a d := deg(b) c := lc(b) while deg(r) ≥ d do s := (lc(r)/c) ⋅ xdeg(r)−d q := q + s r := r − sb end do return (q, r)
end The proof of the validity of this algorithm relies on the fact that during the whole "while" loop, we have a = bq + r and deg(r) 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 (a, b) by (b, rem(a, b)) (where "rem(a, b)" 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 ) := { a if b = 0 gcd ( b , rem ( a , b ) ) otherwise . {\displaystyle \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: r0 := a r1 := b for (i := 1; ri ≤ 0; i := i + 1) do
ri+1 := rem(ri−1, ri)
end do return ri-1. The sequence of the degrees of the ri is strictly decreasing. Thus after, at most, deg(b) steps, one get a null remainder, say rk. As (a, b) and (b, rem(a,b)) have the same divisors, the set of the common divisors is not changed by Euclid's algorithm and thus all pairs (ri, ri+1) have the same set of common divisors. The common divisors of a and b are thus the common divisors of rk−1 and 0. Thus rk−1 is a GCD of a and b. 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 u and v. 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. Extended GCD algorithm Input: a, b, univariate polynomials Output:
g, the GCD of a and b u, v, as in above statement a1, b1, such that a = g a1 b = g b1
Begin
(r0, r1) := (a, b) (s0, s1) := (1, 0) (t0, t1) := (0, 1) for (i := 1; ri ≠ 0; i := i+1) do q := quo(ri−1, ri) ri+1 := ri−1 − qri si+1 := si−1 − qsi ti+1 := ti−1 − qti end do g := ri−1 u := si−1 v := ti−1 a1 := (−1)i−1 ti b1 := (−1)i si
End The proof that the algorithm satisfies its output specification relies on the fact that, for every i we have
r i = a s i + b t i {\displaystyle r_{i}=as_{i}+bt_{i}}
s i t i + 1 − t i s i + 1 = s i t i − 1 − t i s i − 1 , {\displaystyle 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 . {\displaystyle 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 si and ti increase at most as the degree of ri 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 L an algebraic extension of a field K, generated by an element whose minimal polynomial f has degree n. The elements of L are usually represented by univariate polynomials over K of degree less than n. The addition in L is simply the addition of polynomials:
a + L b = a + K [ X ] b . {\displaystyle a+_{L}b=a+_{K[X]}b.}
The multiplication in L is the multiplication of polynomials followed by the division by f:
a ⋅ L b = rem ( a . K [ X ] b , f ) . {\displaystyle a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f).}
The inverse of a non zero element a of L is the coefficient u in Bézout's identity au + fv = 1, which may be computed by extended GCD algorithm. (The GCD is 1 because the minimal polynomial f is irreducible.) The degree inequality in the specification of extended GCD algorithm shows that a further division by f is not needed to get deg(u) < deg(f).
Subresultants In the case of univariate polynomials, there is a strong relationship between 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 theory of subresultantsis a generalization of this property that allows characterizing generically the GCD of two polynomials, and the resultant is the 0-th subresultant polynomial. The i-th subresultant polynomial Si(P, Q) of two polynomials P and Q is a polynomial of degree at most i whose coefficients are polynomial functions of the coefficients of P and Q, and the i-th principal subresultant coefficient si(P, Q) is the coefficient of degree i of Si(P, Q). They have the property that the GCD of P and Q has a degree d if and only if
s 0 ( P , Q ) = ⋯ = s d − 1 ( P , Q ) = 0 , s d ( P , Q ) ≠ 0. {\displaystyle s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0,\ s_{d}(P,Q)\neq 0.}
In this case, Sd(P, Q) is a GCD of P and Q and
S 0 ( P , Q ) = ⋯ = S d − 1 ( P , Q ) = 0. {\displaystyle 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 P and Q. 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 R into another commutative ring S. It extends to another homomorphism, denoted also φ between the polynomials rings over R and S. Then, if P and Q are univariate polynomials with coefficients in R such that
deg ( P ) = deg ( φ ( P ) ) {\displaystyle \deg(P)=\deg(\varphi (P))}
and
deg ( Q ) = deg ( φ ( Q ) ) , {\displaystyle \deg(Q)=\deg(\varphi (Q)),}
then the subresultant polynomials and the principal subresultant coefficients of φ(P) and φ(Q) are the image by φ of those of P and Q. 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 + ⋯ + p m X m , Q = q 0 + q 1 X + ⋯ + q n X n . {\displaystyle 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 P i {\displaystyle {\mathcal {P}}_{i}} the K vector space of dimension i of polynomials of degree less than i. For non-negative integer i such that i ≤ m and i ≤ n, let
φ i : P n − i × P m − i → P m + n − i {\displaystyle \varphi _{i}:{\mathcal {P}}_{n-i}\times {\mathcal {P}}_{m-i}\rightarrow {\mathcal {P}}_{m+n-i}}
be the linear map such that
φ i ( A , B ) = A P + B Q . {\displaystyle \varphi _{i}(A,B)=AP+BQ.}
The resultant of P and Q is the determinant of the Sylvester matrix, which is the (square) matrix of φ 0 {\displaystyle \varphi _{0}} on the bases of the powers of X. Similarly, the i-subresultant polynomial is defined in term of determinants of submatrices of the matrix of φ i . {\displaystyle \varphi _{i}.}
Let us describe these matrices more precisely; Let pi = 0 for i < 0 or i > m, and qi = 0 for i < 0 or i > n. The Sylvester matrix is the (m + n) × (m + n)-matrix such that the coefficient of the i-th row and the j-th column is pm+j−i for j ≤ n and qj−i for j > n:
S = ( p m 0 ⋯ 0 q n 0 ⋯ 0 p m − 1 p m ⋯ 0 q n − 1 q n ⋯ 0 p m − 2 p m − 1 ⋱ 0 q n − 2 q n − 1 ⋱ 0 ⋮ ⋮ ⋱ p m ⋮ ⋮ ⋱ q n ⋮ ⋮ ⋯ p m − 1 ⋮ ⋮ ⋯ q n − 1 p 0 p 1 ⋯ ⋮ q 0 q 1 ⋯ ⋮ 0 p 0 ⋱ ⋮ 0 q 0 ⋱ ⋮ ⋮ ⋮ ⋱ p 1 ⋮ ⋮ ⋱ q 1 0 0 ⋯ p 0 0 0 ⋯ q 0 ) . {\displaystyle 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 Ti of φ i {\displaystyle \varphi _{i}} is the (m + n − i) × (m + n − 2i)-submatrix of S which is obtained by removing the last i rows of zeros in the submatrix of the columns 1 to n − i and n + 1 to m + n