Euclid’s Algorithm for Polynomials

Consider the division algorithm. It looks a lot like division for integers, as it should. Specifically, it’s got all the features we need for the setup of Euclid’s Algorithm, and we have an analogue here!

Just like we did back then, we start with two polynomials and , and we divide them to find . Then if we turn around and divide to find . We keep going until we end up with a remainder of , at which point we can’t divide anymore, and so we stop. And we must eventually stop, because the degree of the remainders keep going down.

At the end, the last nonzero remainder will be the “greatest common divisor” of and . That is, it’s a polynomial that divides both and (leaving no remainder), and any other such common divisor must itself evenly divide .

Euclid’s algorithm also gives us a way of writing out the greatest common divisor as a linear combination . Just like for the integers, this marks the greatest common divisor as the linear combination with the least degree.

Now how to show all this? It’s easy: just go back to the proof of Euclid’s algorithm for integers! Everything works the same way again. We just have to stick in references to the degree where appropriate to measure the “size” of a polynomial.

In fact, if we can equip any integral domain with a degree function (where is the set of nonzero ring elements) so that we have a division algorithm like those for integers and polynomials, then we’ve got the setup for Euclid’s algorithm. In this case, we say we have a “Euclidean domain”. So the point here is that is Euclidean, and so it has a form of Euclid’s algorithm, and all that follows from it.

Notice that in the case of the integers we had some ambiguity about common divisors, since would both work equally well. The point here is that they differ by multiplication by a unit, and so each divides the other. This sort of thing happens in the divisibility preorder for any ring. For polynomials, the units are just the nonzero elements of the base field, considered as constant (degree zero) polynomials. Thus the greatest common divisor is only determined up to a constant multiple, but we can easily ignore that little ambiguity. The “greatest” just has to be read as referring to the degree of the polynomial.