The greatest common divisor of two polynomials

Invariant subspaces of linear maps: Diagonalizability

The greatest common divisor of two polynomials

When dealing with the notion of minimal polynomial we used division with remainder for polynomials. We have seen that polynomials have arithmetic similarities with integers, where the degree of a polynomial is comparable to the absolute value of an integer. This also holds for the notion of greatest common divisor, which we will use later on to find the Jordan normal form, a unique form of a square matrix within its conjugation class.

Let $f,g$ be polynomials in one variable. A common divisor of $f$ and $g$ is a polynomial dividing both $f$ and $g$ .

If $f$ and $g$ are both unequal to the zero polynomial, then the common divisor of the highest possible degree is called a greatest common divisor (gcd).

Every greatest common divisor of $f$ and $g$ is a multiple of every divisor of $f$ and $g$ .

In particular, the greatest common divisors are unique up to a scalar multiple not equal to $0$ . Each set of two polynomials of which at least one is not equal to $0$ , hence, has a unique monic gcd.

With $\gcd(f,g)$ we indicate the monic gcd of $f$ and $g$ .

The monic gcd of $x^4-1$ and $x^6-1$ is $x^2-1$ . This can be seen as follows:

$x^2-1$ is monic since the coefficient of $x^2$ is equal to $1$
$x^4-1 = (x^2-1)\cdot (x^2+1)$ , hence $x^2-1$ divides $x^4-1$
$x^6-1 = (x^2-1)\cdot (x^4+x^2+1)$ , hence $x^2-1$ divides $x^6-1$
If $d$ is a divisor of $x^4-1$ and $x^6-1$ of degree higher than $2$ , then $x^2+1$ (a divisor of $x^4-1$ of degree $2$ ) must have a factor in common with $d$ , such that $d(\ii)=0$ or $d(-\ii) = 0$ . But $\ii^6-1=-2$ and $(-\ii)^6-1=-2$ , hence $\ii$ and $-\ii$ are not zeros of $x^6-1$ , hence $x^2+1$ is no divisor of $x^6-1$ , a contradiction.

With the following rules of calculation, the calculation becomes simpler and the procedure more systematic.

The following rules are useful for the calculation of gcd's of polynomials. They show great similarities with the rules of calculation for the gcd of integers.

Rules of calculation for the gcd of polynomials

Let $f$ and $g$ be polynomials, of which at least one is not equal to $0$ .

${\gcd}(f,g)={\gcd}(g,f)$ .
${\gcd}(0,g)=\frac{g}{c}$ where $c$ is the leading coefficient of $g$ .
$\gcd(f,g) = \gcd(g,r)$ , in which $r$ is the remainder when dividing $f$ by $g$ .
If $m$ is a commmon divisor of $f$ and $g$ with leading coefficient equal to $1$ , then we have $\gcd( f, g) = m\cdot\gcd\left(\frac{f}{m},\frac{g}{m}\right)$ .

Rules $1$ and $2$ directly follow from the definition of gcd.

To prove rule 3, $\gcd(f,g) = \gcd(g,r)$ , in which $r$ is the remainder when dividing $f$ by $g$ , we write $c = \gcd(g,r)$ and deduce that $c$ is the gcd of $f$ and $g$ . Since $c$ is a gcd itself, its leading coefficient will be equal to $1$ . From the definition of $c$ follows that $c$ is a divisor of $g$ . If $q$ is the quotient when dividing with remainder of $f$ by $g$ , we have $f=q\cdot g+r$ . Since $c$ divides both $r$ and $g$ , this shows that $c$ also divides $f$ . We still have to prove that $c$ is a common divisor of $f$ and $g$ of the highest possible degree. Assume that $d$ is a common divisor of $f$ and $g$ . Then $d$ also divides $f-q\cdot g=r$ , such that $d$ is a common divisor of $g$ and $r$ . This results in the fact that $d$ is a divisor of $c$ , hence, not having a degree bigger than the degree of $c$ .

To prove rule 4, we write $e = m\cdot\gcd\left(\frac{f}{m},\frac{g}{m}\right)$ . The leading coefficient of $e$ is equal to $1$ . Moreover, we know that $e$ is a divisor of $f$ since $\gcd\left(\frac{f}{m},\frac{g}{m}\right)$ is a divisor of $\frac{f}{m}$ . Similarly, $e$ is a divisor of $g$ . We still have to deduce that each common divisor of $f$ and $g$ is a divisor of $e$ . Let $h$ be such a common divisor. Write $p=\gcd(m,h)$ and $q=\frac{h}{p}$ . Then both $p$ and $q$ are polynomials with $h=p\cdot q$ . Moreover, $q$ divides both $\frac{f}{m}$ and $\frac{g}{m}$ ; hence, it is a divisor of $\gcd\left(\frac{f}{m},\frac{g}{m}\right)$ . Since $p$ is a divisor of $m$ , we see that $h=p\cdot q$ is a divisor of $e$ . With this we conclude the proof of rule 5.

What is the monic gcd of the polynomials $f(x)=x^2+1$ and $g(x)=x^8$ ?

$\gcd(f(x),g(x))=$ $1$

The gcd can be determined by use of the gcd rule for polynomials regarding the replacement of an argument of the gcd by a remainder as follows:

$\begin{array}{rcl} \gcd (f(x),g(x))&=&{\rm gcd}(x^2+1,x^8)\\ &=& \gcd(x^2+1,1)\\ &&\phantom{xx}\color{blue}{\text{second argument replaced by remainder}}\\ &&\phantom{xx}\color{blue}{\text{by dividing this argument by the first argument}}\\ &=& \gcd(0,1)\\ &&\phantom{xx}\color{blue}{\text{first argument replaced by remainder}}\\ &&\phantom{xx}\color{blue}{\text{by dividing this argument by the second argument}}\\ &=& 1 \end{array}$

New example