Polynomial greatest common divisor

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.