Polynomial Greatest Common Divisor

A polynomial greatest common divisor of polynomials , not both zero, over a field is a polynomial that divides both and and is divisible by every common divisor. It is customary to choose to be monic. This makes unique, and it is denoted .

The Euclidean algorithm computes by repeated polynomial division. For , if

(1)

where or , then

(2)

The last nonzero polynomial remainder, divided by its leading coefficient, is the desired monic polynomial (Brown and Traub 1971, pp. 506-507). Back substitution gives polynomials such that

(3)

For example,

(4)

and divides , so .

Subresultants provide another characterization. For nonzero and with degrees , let be their th subresultant and its principal subresultant coefficient, using the terminal convention , where is the leading coefficient of . If is the first index with , then

(5)

and (El Kahoui 2003, pp. 290-291). In particular, the resultant is zero iff the polynomials have a common divisor of positive degree.

The ring of coefficients matters. In , a greatest common divisor is determined up to sign and need not be monic. For example, a greatest common divisor of and in is , whereas their monic greatest common divisor in is . Moreover, the linear combination property over a field need not hold with integer coefficients. Although 2 and have greatest common divisor 1 in , an identity with is impossible, as evaluating at shows.

Polynomial greatest common divisors are computed in the Wolfram Language using PolynomialGCD[f, g]. To make a nonzero output monic, divide it by its leading coefficient. The coefficients in a linear combination are returned by PolynomialExtendedGCD[f, g, x].