Greatest common divisor of two polynomials

Informally, the greatest common divisor (GCD) of two polynomials p(x) and q(x) is the "biggest" polynomial that divides evenly into both p(x) and q(x). The definition is modeled on the concept of the greatest common divisor of two integers. This is simply the greatest integer that divides into both of them with a remainder of zero. For polynomials, the situation is slightly more complicated, because there is no canonical order which we can use to say which polynomial is "biggest." Instead, we choose the GCD so that its degree is as great as possible, and so that its leading coefficient equals one (i.e a monic polynomial). The greatest common divisor is also sometimes referred to as the greatest common factor or the highest common factor.

Formal definition

Let p(x) and q(x) be polynomials, not both zero, with coefficients in a field F. The greatest common divisor of p(x) and q(x) is the monic polynomial d(x) of highest degree such that d(x) is a divisor of p(x) and of q(x). We may denote the greatest common divisor of p(x) and q(x) by GCD(p(x), q(x)).

F may be, for example, the complex numbers, the real numbers or the rational numbers.

If p(x)=q(x) = 0, then every polynomial is a common divisor of p(x) and q(x). Thus no greatest common divisor exists in this case.

We require that F be a field and that d(x) be monic. Under these two hypotheses, the GCD exists and is uniquely defined. They are necessary hypotheses. For example, suppose we allow F=Z/6Z, which is not a field. Then we have

and

after reduction modulo six (see modular arithmetic). This shows that x and x + 3 would both satisfy the definition of

Suppose, on the other hand, that we did not require d(x) to be monic. In that case, whenever d(x) satisfied the definition of GCD(p(x), q(x)), so would k•d(x) for any nonzero scalar k in F. Again, the GCD would not be uniquely determined.

The constant 1 is always a common divisor of p(x) and q(x); we may regard it as a monic polynomial of degree zero. If GCD(p(x), q(x)) = 1, we say p and q are relatively prime.

Properties

• As stated above, the GCD of two polynomials, not both zero, with coefficients from a field, exists and is unique.
• If c(x) is any common divisor of p(x) and q(x), then c(x) divides d(x). This is sometimes given in the definition instead of requiring d(x) to be the common divisor of highest degree. The two definitions are logically equivalent.
• GCD(p(x),q(x)) = GCD(q(x),p(x)).
• GCD(p(x),q(x)) = GCD(p(x),p(x) + q(x)).
• For any nonzero scalar k in F, GCD(p(x),q(x)) = GCD(p(x),kq(x)).
• Hence GCD(p(x),q(x)) = GCD(a₁p(x) + b₁q(x),a₂p(x) + b₂q(x)) for any scalars a₁,b₁,a₂,b₂ such that a₁b₂ − a₂b₁ is not equal to zero.
• Likewise, if GCD(p(x),r(x)) = 1, then GCD(p(x),q(x)) = GCD(p(x),q(x)r(x)).
• The GCD of two polynomials, p(x) and q(x), is the smallest-degree polynomial which can be written as a linear combination of p(x) and q(x). That is, there exist some polynomials, in the same field, r(x) and s(x), not necessarily unique, such that

d(x) = p(x)r(x) + q(x)s(x).

• It is possible to define the GCD of three or more polynomials inductively. Explicitly:

GCD(p(x),q(x),r(x)) = GCD(p(x),GCD(q(x),r(x))),

and

Methods for finding the GCD

There are several ways to find the greatest common divisor of two polynomials. Two of them are:

1. Factorization, 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.
2. 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 x² + 7x + 6 and x² − 5x − 6.

x² + 7x + 6 = (x + 1)(x + 6)

x² − 5x − 6 = (x + 1)(x − 6)

Thus, their GCD = (x + 1).

Euclidean algorithm

This section requires expansion.

Finding the GCD by factoring is intuitively simple but requires knowing how to factor the polynomials, which can be difficult, especially if the polynomials have large degree. The Euclidean algorithm is a fast method which works for any pair of polynomials. It makes repeated use of polynomial long division or synthetic division, just as when the Euclidean algorithm is applied to two numbers. 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.

Example two: Find the GCD of x² + 7x + 6 and x² − 5x − 6.

x² + 7x + 6 = (x² − 5x − 6)(1) + (x + 1)(12)

x² − 5x − 6 = (x + 1)(x − 6) + 0

Since x + 1 is the last nonzero remainder, the GCD of these polynomials is x + 1.

See also

• List of polynomial topics
• Multivariate division algorithm

References