HowTo: Euclidean algorithm for polynomials

In this HowTo we will describe the analogue of the euclidean algorithm to compute the greatest common divisor of any two polynomials in .

As the name indicates, a greatest common divisor (gcd) of two polynomials is a polynomial of greatest possible degree which divides both and . Clearly is only defined up to multiplication by a non-zero scalar, which is why we talk about ‘a’ gcd instead of ‘the’ gcd. Indeed, let be a non-zero scalar, then if is a gcd of , so is .

Given polynomials with , the division algorithm gives polynomials with such that

A crucial observation, as with the gcd of integers, is that a polynomial is a gcd of and if and only if it is a gcd of and . This is proved in the same way as with integers.

The euclidean algorithm then works in the same way.

Problem. Find a greatest common divisor of two polynomials , with .

Solution (Euclidean algorithm). This is solved by iteration:

1. Let and .
2. Use the division algorithm to find polynomials , with , such that .
3. If then we stop: is a greatest common divisor.
4. If then replace by and by and go to (2).

Notice that this algorithm ends because at every step the degree of is decreasing.

Similarly we can modify the extended euclidean algorithm to write from which it follows that any common divisor of and also divides . As a corollary we can prove that any two gcds of are multiples of each other. Indeed, if and are gcds, then and , whence by Problem 5.3, they have the same degree, hence if, say, , then must be a constant.

We could talk of the greatest common divisor if we imposed an extra condition on to eliminate the freedom of multiplying by a constant. One such condition is that the gcd be monic; that is, that the coefficient of highest degree be .