# Greatest common divisor of polynomials

The greatest common divisor (gcd) of a given set of polynomials is the "largest" monic polynomial that divides exactly all the members of the given set.

## Preliminaries

Before introducing the gcd, we are going to review the basics of polynomials (in this section) and their division (in the next one).

Let be a field (e.g., the set of real numbers or the set of complex numbers ).

A polynomial of degree is a function defined bywhere is a non-negative integer, the coefficients and the argument belong to , and .

From now on, unless otherwise specified, we always assume that all the polynomials are defined over the same field .

When the leading coefficient is equal to , then we say that the polynomial is monic.

When is identically equal to zero, by convention the degree of the polynomial is .

The degree of a polynomial is often denoted by .

## Review of division

The division of two polynomials and (with ) is performed by finding the unique polynomial quotient such that and . Two cases are possible:

• if , then ;

• if instead , then .

By using the so-called Division Algorithm, not only we are able to show that such a polynomial exists, but we can actually compute .

If the remainder , which in general is itself a polynomial, is identically equal to zero, that is, ifthen we say that is a divisor of (or that divides , or that is divisible by ) and we write

Example Consider the polynomial defined by Then and are divisors of . These are not the only divisors of . For example, is a divisor of because

## Monic divisor

The previous example highlights an interesting fact: if is a divisor of , then, for any scalar , is also a divisor of . Thus, we can generate an infinite number of divisors by taking arbitrary scalar multiples of any divisor.

In order to avoid dealing with an infinite number of divisors, we often focus on monic divisors, that is, divisors whose leading coefficients are .

Example In the previous example, we can write the polynomial asfrom which we can see that and are monic divisors of . Also the polynomialis a monic divisor of .

## Common divisors

We now provide a simple definition that will subsequently help to define the greatest common divisor.

Definition Let be polynomials. We say that a polynomial is a common divisor of if and only if it is monic andfor .

Here is an example.

Example Let Then, the polynomialis monic and it divides both and . Therefore, is a common divisor of and .

## GCD

We are now ready to define the greatest common divisor.

Definition Let be polynomials. A common divisor of is a greatest common divisor if and only if for every other common divisor , in which case we write

In other words, the gcd is the common divisor which is divisible by all the common divisors.

The simplest example of a GCD is provided in the next section.

## GCD of two polynomials one of which is zero

We immediately note that, when , we havewhere is the leading coefficient of .

Proof

Since any polynomial divides the zero polynomial, the common divisors of and are all the monic divisors of . The only monic polynomial which 1) divides and 2) is divisible by all the monic divisors of is: . Therefore is the gcd of and .

## GCD of two divisible polynomials

Here is another simple example. When , thenwhere is the leading coefficient of .

Proof

Since , all the divisors of are also divisors of . Therefore, the set of common divisors coincides with the set of monic divisors of . As in the previous section, this implies that is the gcd.

## Euclidean algorithm

The proof of the existence of a gcd is based on the so-called Euclidean algorithm, which actually allows us to compute the gcd.

Before introducing the Euclidean algorithm, we need to present the following preliminary result.

Proposition Let and be two polynomials. Letbe the result of the Division Algorithm, where is the quotient and is the remainder. Then, if and only if

Proof

Let us prove the "if" part, starting from the hypothesis that (2) holds. Then, we havewhere we have denoted by and the quotient obtained by dividing and by . Thus, , and is a common divisor of and . Suppose that there exists another common divisor of and (fact A). Then,which implies that is a divisor of and, hence, a common divisor of and . Hence, by the initial hypothesis (equation 2), it must be that (fact B). Facts A and B combined imply that is a greatest common divisor of and . Let us now prove the "only if" part, starting from the hypothesis that (1) holds. Then, we havewhich implies that and, as a consequence, is a common divisor of and . Suppose that there exists another common divisor of and (fact C). Then,which implies that is a divisor of and, hence, a common divisor of and . Hence, by the initial hypothesis (equation 1), it must be that (fact D). Facts C and D combined imply that is a greatest common divisor of and .

We can now prove existence for the case of two polynomials. The iterative algorithm used in the proof is known as Euclidean algorithm.

Proposition Let and be two polynomials such that at least one of them is not identically equal to zero. Then, there exists a polynomial such that

Proof

Throughout this proof, it is important to remember that any polynomial divides the zero polynomial. We can assume without loss of generality that (otherwise we invert the order of the two polynomials). If , then and we can choose where is the leading coefficient of . Thus, is monic. Since and , is a common divisor of and . Let be another common divisor. Then,andwhich implies that . Hence, is a greatest common divisor of and . Thus, we have been able to find a gcd in the case in which . If , then we iteratively apply the Division AlgorithmRemember that in the Division Algorithm either the quotient is zero or the remainder has lower degree than the divisor. The former cannot happen because . Therefore, the degree of the remainder decreases at each iteration. We stop the iterations when (which is guaranteed to happen when reaches degree ). By the previous proposition, showing the existence of is equivalent to showing the existence of , , ..., , . Butwhere is the leading coefficient of , by the same line of reasoning applied above to the case in which .

Note the essential requirement that at least one of the two polynomials be different from the zero polynomial. In case both polynomials are zero, then any other polynomial is a common divisor and therefore, there is no "upper bound" to the set of common divisors and no gcd.

The existence proof can be extended to more than two polynomials.

Proposition Let be polynomials, at least one of which is not identically equal to zero. Then, there exists a polynomial such that

Proof

The proof is by induction. Suppose without loss of generality that (otherwise we can re-order the polynomials). Then, by the previous proposition there existsSuppose that there existsWe need to prove that the latter assumption implies that there existsWe defineBy equation (2) and by equation (1) (). Therefore, (). Additionally, by equation (2), . Thus, is a common divisor of . Let be any other common divisor of . By equation (1), we have that . Thus, is a common divisor of and , which implies, by equation (2), that . Hence,

## Uniqueness

If a greatest common divisor exists, then it is unique.

Proposition Let be polynomials, at least one of which is not identically equal to zero. Then, there is a unique

Proof

Suppose is another gcd. Both and are common divisors of . Then, and by the definition of gcd. As proved in the lecture on the Division Algorithm, mutual divisors are scalar multiples of each other. Hence,where is a non-zero constant. But both and are monic, which implies that . Hence, .

## Relatively prime

This is a term that you will often encounter.

Definition Let be polynomials. Ifthen we say that are relatively prime.

## Bézout's theorem

The following proposition, often called Bézout's theorem, provides a representation of the gcd.

Proposition Let and be two polynomials such that they are not identically equal to zero. Then, there exist two polynomials and such that

Proof

Let be the set of all polynomialsthat can be formed by arbitrarily choosing and , excluding the zero polynomial (i.e., ). Let be an element of with the lowest possible degree. Note that because we can choose and . By the Division Algorithm, there exist polynomials and such that and (we are in this case and not in the case because ). Suppose thatWe can writeThus, has the form (1). As a consequence, either it belongs to or it is the zero polynomial. It cannot belong to because , contrary to the assumption that is a lowest-degree polynomial in . Therefore, . As a consequence, . In a completely analogous manner, we can prove that . Denote by the leading coefficient of and defineso that is monic. The polynomial is a common divisor of and . Suppose that is another common divisor. Then,andThus, . As a consequence,

## Solved exercises

Below you can find some exercises with explained solutions.

### Exercise 1

Use the Euclidean algorithm to find the gcd ofand

Solution

We start by dividing the two polynomials:Thus, the remainder of the division is and we haveWe need to perform a new division:Thus, the remainder of the division is zero and we obtain the gcd by dividing by its leading coefficient: