Polynomial greatest common divisor


In algebra, the greatest common divisor 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.

General definition

Let and be polynomials with coefficients in an integral domain, typically a field or the integers.
A greatest common divisor of and is a polynomial that divides and, and such that every common divisor of and also divides. Every pair of polynomials has a GCD if and only if is a unique factorization domain.
If is a field and and are not both zero, a polynomial is a greatest common divisor if and only if it divides both and, and it has the greatest degree among the polynomials having this property. If, the GCD is 0. However, some authors consider that it is not defined in this case.
The greatest common divisor of and is usually denoted "".
The greatest common divisor is not unique: if is a GCD of and, then the polynomial is another GCD if and only if there is an invertible element of such that
and
In other words, the GCD is unique up to the multiplication by an invertible constant.
In the case of the integers, this indetermination has been settled by choosing, as the GCD, the unique one which is positive. With this convention, the GCD of two integers is also the greatest common divisor. However, since there is no natural total order for polynomials over an integral domain, one cannot proceed in the same way here. For univariate polynomials over a field, one can additionally require the GCD to be monic, but in more general cases there is no general convention. Therefore, equalities like or are common abuses of notation which should be read " is a GCD of and " and " and have the same set of GCDs as and ". In particular, means that the invertible constants are the only common divisors. In this case, by analogy with the integer case, one says that and are .

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 is any common divisor of and, then divides their GCD.
  • for any polynomial. This property is at the basis of the proof of Euclidean algorithm.
  • For any invertible element of the ring of the coefficients,.
  • Hence for any scalars such that is invertible.
  • If, then.
  • If, then.
  • For two univariate polynomials and over a field, there exist polynomials and, such that and divides every such linear combination of and .
  • 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: and

    GCD by hand computation

There are several ways to find the greatest common divisor of two polynomials. Two of them are:
  1. 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.
  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 and.
Thus, their GCD is.

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 and, one can suppose , and
The Euclidean division provides two polynomials, the quotient and, the remainder such that
A polynomial divides both and if and only if it divides both and. Thus
Setting
one can repeat the Euclidean division to get new polynomials and so on. At each stage we have
so the sequence will eventually reach a point at which
and one has got the GCD:
Example: finding the GCD of and :
Since is the last nonzero remainder, it is a GCD of the original polynomials, and the monic GCD is .
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 well defined computation result (that is a numerically stable result; in this cases other techniques may be used, usually based on singular value decomposition.

Univariate polynomials with coefficients in a field

The case of univariate polynomials over a field is especially important for several reasons. Firstly, it is the most elementary case and therefore appears in most first courses in algebra. Secondly, it is very similar to the case of the integers, and this analogy is the source of the notion of Euclidean domain. A third reason is that the theory and the algorithms for the multivariate case and for coefficients in a unique factorization domain are strongly based on this particular case. Last but not least, 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 and defined over a field, there exist two polynomials and which satisfy
and
where "" 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. In the following computation "deg" stands for the degree of its argument, and "lc" stands for the leading coefficient, the coefficient of the highest degree of the variable.
The proof of the validity of this algorithm relies on the fact that during the whole "while" loop, we have and 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 by , until b = 0. The GCD is the last non zero remainder.
Euclid's algorithm may be formalized in the recursive programming style as:
In the imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder:
The sequence of the degrees of the is strictly decreasing. Thus after, at most, steps, one get a null remainder, say. As and have the same divisors, the set of the common divisors is not changed by Euclid's algorithm and thus all pairs have the same set of common divisors. The common divisors of and are thus the common divisors of and 0. Thus is a GCD of and.
This not only proves that Euclid's algorithm computes GCDs but also proves that GCDs exist.