Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Greatest common divisor of polynomials

by , PhD

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.

Table of Contents

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 F be a field (e.g., the set of real numbers R or the set of complex numbers $U{2102} $).

A polynomial of degree $m$ is a function $f:F ightarrow F$ defined by[eq1]where $m$ is a non-negative integer, the coefficients [eq2] and the argument $z$ belong to F, and $a_{m} eq 0$.

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

When the leading coefficient $a_{m}$ is equal to 1, then we say that the polynomial is monic.

When $fleft( z ight) $ is identically equal to zero, by convention the degree of the polynomial is $-infty $.

The degree of a polynomial $f$ is often denoted by [eq3].

Review of division

The division of two polynomials $f$ and $g$ (with [eq4]) is performed by finding the unique polynomial quotient $q$ such that [eq5]and [eq6]. Two cases are possible:

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

If the remainder $r$, which in general is itself a polynomial, is identically equal to zero, that is, if[eq10]then we say that $g$ is a divisor of $f$ (or that $g$ divides $f$, or that $f $ is divisible by $g$) and we write[eq11]

Example Consider the polynomial [eq12] defined by [eq13]Then $left( 4+z ight) $ and [eq14] are divisors of $f$. These are not the only divisors of $f$. For example, [eq15] is a divisor of $f$ because[eq16]

Monic divisor

The previous example highlights an interesting fact: if $g$ is a divisor of $f$, then, for any scalar $c eq 0$, $cg$ is also a divisor of $f$. 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 1.

Example In the previous example, we can write the polynomial $f$ as[eq17]from which we can see that $left( 4+z ight) $ and [eq18] are monic divisors of $f$. Also the polynomial[eq19]is a monic divisor of $f$.

Common divisors

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

Definition Let [eq20] be polynomials. We say that a polynomial $g$ is a common divisor of [eq21] if and only if it is monic and[eq22]for $j=1,ldots ,n$.

Here is an example.

Example Let [eq23]Then, the polynomial[eq24]is monic and it divides both $f_{1}$ and $f_{2}$. Therefore, $g$ is a common divisor of $f_{1}$ and $f_{2}$.

GCD

We are now ready to define the greatest common divisor.

Definition Let [eq25] be polynomials. A common divisor $g$ of [eq26] is a greatest common divisor if and only if [eq27]for every other common divisor $d$, in which case we write[eq28]

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 $f eq 0$, we have[eq29]where $a_{m}$ is the leading coefficient of $f$.

Proof

Since any polynomial divides the zero polynomial, the common divisors of $f$ and 0 are all the monic divisors of $f$. The only monic polynomial which 1) divides $f$ and 2) is divisible by all the monic divisors of $f$ is: $frac{1}{a_{m}}f$. Therefore $frac{1}{a_{m}}f$ is the gcd of $f$ and 0.

GCD of two divisible polynomials

Here is another simple example. When $f_{1}|f_{2}$, then[eq30]where $a_{m}$ is the leading coefficient of $f_{1}$.

Proof

Since $f_{1}|f_{2}$, all the divisors of $f_{1}$ are also divisors of $f_{2}$. Therefore, the set of common divisors coincides with the set of monic divisors of $f_{1}$. As in the previous section, this implies that $frac{1}{a_{m}}f$ 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 $f_{1}$ and $f_{2}$ be two polynomials. Let[eq31]be the result of the Division Algorithm, where $q$ is the quotient and $r$ is the remainder. Then, [eq32]if and only if[eq33]

Proof

Let us prove the "if" part, starting from the hypothesis that (2) holds. Then, we have[eq34]where we have denoted by $f_{2}/g$ and $r/g$ the quotient obtained by dividing $f_{2}$ and $r$ by $g$. Thus, $g|f_{1}$, and $g$ is a common divisor of $f_{1}$ and $f_{2}$. Suppose that there exists another common divisor $d$ of $f_{1}$ and $f_{2}$ (fact A). Then,[eq35]which implies that $d$ is a divisor of $r$ and, hence, a common divisor of $f_{2}$ and $r$. Hence, by the initial hypothesis (equation 2), it must be that $d|g$ (fact B). Facts A and B combined imply that $g$ is a greatest common divisor of $f_{1}$ and $f_{2}$. Let us now prove the "only if" part, starting from the hypothesis that (1) holds. Then, we have[eq36]which implies that $g|r$ and, as a consequence, $g$ is a common divisor of $f_{2}$ and $r$. Suppose that there exists another common divisor $d$ of $f_{2}$ and $r$ (fact C). Then,[eq37]which implies that $d$ is a divisor of $f_{1}$ and, hence, a common divisor of $f_{1}$ and $f_{2}$. Hence, by the initial hypothesis (equation 1), it must be that $d|g$ (fact D). Facts C and D combined imply that $g$ is a greatest common divisor of $f_{2}$ and $r$.

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 $f_{1}$ and $f_{2}$ be two polynomials such that at least one of them is not identically equal to zero. Then, there exists a polynomial $g$ such that[eq38]

Proof

Throughout this proof, it is important to remember that any polynomial divides the zero polynomial. We can assume without loss of generality that [eq39] (otherwise we invert the order of the two polynomials). If $f_{2}=0$, then $f_{1} eq 0$ and we can choose [eq40]where $a_{m}$ is the leading coefficient of $f_{1}$. Thus, $g$ is monic. Since [eq41]and $g|0$, $g$ is a common divisor of $f_{1}$ and $f_{2}$. Let $d$ be another common divisor. Then,[eq42]and[eq43]which implies that $d|g$. Hence, $g$ is a greatest common divisor of $f_{1}$ and $f_{2}$. Thus, we have been able to find a gcd in the case in which $f_{2}=0$. If $f_{2} eq 0$, then we iteratively apply the Division Algorithm[eq44]Remember that in the Division Algorithm either the quotient is zero or the remainder has lower degree than the divisor. The former cannot happen because [eq45]. Therefore, the degree of the remainder decreases at each iteration. We stop the iterations when $r_{n}=0$ (which is guaranteed to happen when $r_{n-1}$ reaches degree 1). By the previous proposition, showing the existence of [eq46] is equivalent to showing the existence of [eq47], [eq48], ..., [eq49], [eq50]. But[eq51]where $b_{l}$ is the leading coefficient of $r_{n-1}$, by the same line of reasoning applied above to the case in which $f_{2}=0$.

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 [eq52] be polynomials, at least one of which is not identically equal to zero. Then, there exists a polynomial $g$ such that[eq53]

Proof

The proof is by induction. Suppose without loss of generality that $f_{1} eq 0$ (otherwise we can re-order the polynomials). Then, by the previous proposition there exists[eq54]Suppose that there exists[eq55]We need to prove that the latter assumption implies that there exists[eq56]We define[eq57]By equation (2) $g_{n}|g_{n-1}$ and by equation (1) $g_{n-1}|f_{j}$ ($j=1,ldots ,n-1$). Therefore, $g_{n}|f_{j}$ ($j=1,ldots ,n-1$). Additionally, by equation (2), $g_{n}|f_{n}$. Thus, $g_{n}$ is a common divisor of [eq58]. Let $d$ be any other common divisor of [eq59]. By equation (1), we have that $d|g_{n-1}$. Thus, $d$ is a common divisor of $g_{n-1}$ and $f_{n}$, which implies, by equation (2), that $d|g_{n}$. Hence, [eq56]

Uniqueness

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

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

Proof

Suppose $h$ is another gcd. Both $g$ and $h$ are common divisors of [eq63]. Then, $g|h$ and $h|g$ by the definition of gcd. As proved in the lecture on the Division Algorithm, mutual divisors are scalar multiples of each other. Hence,[eq64]where $c$ is a non-zero constant. But both $g$ and $h$ are monic, which implies that $c=1$. Hence, $h=g$.

Relatively prime

This is a term that you will often encounter.

Definition Let [eq65] be polynomials. If[eq66]then we say that [eq67] are relatively prime.

Bézout's theorem

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

Proposition Let $f_{1}$ and $f_{2}$ be two polynomials such that they are not identically equal to zero. Then, there exist two polynomials $p_{1}$ and $p_{2}$ such that[eq68]

Proof

Let I be the set of all polynomials[eq69]that can be formed by arbitrarily choosing $p_{1}$ and $p_{2}$, excluding the zero polynomial (i.e., [eq70]). Let $h$ be an element of I with the lowest possible degree. Note that [eq71] because we can choose $p_{1}=1$ and $p_{2}=0$. By the Division Algorithm, there exist polynomials $q$ and $r_{1}$ such that [eq72]and [eq73] (we are in this case and not in the case $q=0$ because [eq74]). Suppose that[eq75]We can write[eq76]Thus, $r_{1}$ has the form (1). As a consequence, either it belongs to I or it is the zero polynomial. It cannot belong to I because [eq77], contrary to the assumption that $h$ is a lowest-degree polynomial in I. Therefore, $r_{1}=0$. As a consequence, $h|f_{1}$. In a completely analogous manner, we can prove that $h|f_{2}$. Denote by $h_{m}$ the leading coefficient of $h$ and define[eq78]so that $g$ is monic. The polynomial $g$ is a common divisor of $f_{1}$ and $f_{2}$. Suppose that $d$ is another common divisor. Then,[eq79]and[eq80]Thus, $d|g$. As a consequence,[eq81]

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Use the Euclidean algorithm to find the gcd of[eq82]and[eq83]

Solution

We start by dividing the two polynomials:[eq84]Thus, the remainder of the division is [eq85] and we have[eq86]We need to perform a new division:[eq87]Thus, the remainder of the division is zero and we obtain the gcd by dividing $r_{1}$ by its leading coefficient:[eq88]

How to cite

Please cite as:

Taboga, Marco (2021). "Greatest common divisor of polynomials", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/greatest-common-divisor-of-polynomials.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.