By Bachet's theorem, given two integers a and b, with greatest common divisor (or gcd) d, there are two integers u and v such that au + bv = d. This theorem extends to polynomials because they too admit Euclidean division. The idea behind the proof is to consider all polynomials of the form A U + B V and, more specifically, one of least degree, which is the gcd of A and B (see the box). The proof also gives an algorithm: starting from a polynomial of the form A U + B V, construct one of lower degree, then repeat for as long as possible.
Take an example to illustrate the Euclidean algorithm for finding a pair (U, V) such that the degree of U is strictly less than that of B, while the degree of V is strictly less than that of A. Let *A = 3X3 + 2X2 + 2 and B = X2 – 2. Dividing A by B gives A – B (3X + 2) = 6X + 6; then, dividing B by X + 1 gives B = (X + 1)(X – 1) – 1*. This yields the following Bézout identity:
It follows that the gcd of A and B is 1; in other words, A and B are coprime.
