Greatest Common Divisor of Two Polynomials - Univariate Polynomials With Coefficients in A Field - Euclid's Algorithm

Euclid's Algorithm

As for the integers, Euclidean division allows us to define Euclid's algorithm for computing GCDs.

Starting from two polynomials a and b, Euclid's algorithm consists of recursively replacing the pair (a, b) by (b, rem(a, b)) (where "rem(a, b)" denotes the remainder of the Euclidean division, computed by the algorithm of the preceding section), until b = 0. The GCD is the last non zero remainder.

Euclid's algorithm may be formalized in the recursive programming style as:

.

In the imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder:

while do

The sequence of the degrees of the r_i is strictly decreasing. Thus after, at most, deg(b) steps, one get a null remainder, say r_k. As (a, b) and (b, rem(a,b)) have the same divisors, the set of the common divisors is not changed by Euclid's algorithm and thus all pairs (r_i, r_{i + 1}) have the same set of common divisors. The common divisors of aand bare thus the common divisors of r_{k − 1} and 0. Thus r_{k − 1} is a GCD of aand b. This not only proves that Euclid's algorithm computes GCDs, but also proves that GCDs exist.