Polynomial greatest common divisor

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that 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, like for the integer GCD, by the Euclidean algorithm using long division. The polynomial GCD is defined only up to the multiplication by an invertible constant.

The similarity between the integer GCD and the 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 or the ring of integers, and also over a 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. Conversely, most of the modern theory of polynomial GCD has been developed to satisfy the need for efficiency of computer algebra systems.

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).$

$\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,kq)$ .

Hence $\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}$ such that $a_{1}b_{2}-a_{2}b_{1}$ is invertible.

If $\gcd(p,r)=1$ , then $\gcd(p,q)=\gcd(p,qr)$ .

If $\gcd(q,r)=1$ , then $\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)=ap+bq$ and $\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)),$ and $\gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})).$

Modular GCD algorithm[edit]

If $f$ and $g$ are polynomials in $F [x]$ for some finitely generated field $F$ , the Euclidean Algorithm is the most natural way to compute their GCD. However, modern computer algebra systems only use it if $F$ is finite because of a phenomenon called intermediate expression swell. Although degrees keep decreasing during the Euclidean algorithm, if $F$ is not finite then the bit size of the polynomials can increase (sometimes dramatically) during the computations because repeated arithmetic operations in $F$ tends to lead to larger expressions. For example, the addition of two rational numbers whose denominators are bounded by $b$ leads to a rational number whose denominator is bounded by $b 2$ , so in the worst case, the bit size could nearly double with just one operation.

To expedite the computation, take a ring $D$ for which $f$ and $g$ are in $D [x]$ , and take an ideal $I$ such that $D / I$ is a finite ring. Then compute the GCD over this finite ring with the Euclidean Algorithm. Using reconstruction techniques (Chinese remainder theorem, rational reconstruction, etc.) one can recover the GCD of $f$ and $g$ from its image modulo a number of ideals $I$ . One can prove^[3] that this works provided that one discards modular images with non-minimal degrees, and avoids ideals $I$ modulo which a leading coefficient vanishes.

Suppose $F=\mathbb {Q} ({\sqrt {3}})$ , $D=\mathbb {Z} [{\sqrt {3}}]$ , $f={\sqrt {3}}x^{3}-5x^{2}+4x+9$ and $g=x^{4}+4x^{2}+3{\sqrt {3}}x-6$ . If we take $I=(2)$ then $D/I$ is a finite ring (not a field since $I$ is not maximal in $D$ ). The Euclidean algorithm applied to the images of $f,g$ in $(D/I)[x]$ succeeds and returns 1. This implies that the GCD of $f,g$ in $F[x]$ must be 1 as well. Note that this example could easily be handled by any method because the degrees were too small for expression swell to occur, but it illustrates that if two polynomials have GCD 1, then the modular algorithm is likely to terminate after a single ideal $I$ .

Polynomial greatest common divisor

unique factorization domain

Bézout's identity

Modular GCD algorithm[edit]

List of polynomial topics

Multivariate division algorithm