## The Euclidean algorithm

Just as in the case of the integers, there is a Euclidean algorithm for polynomials over any ring.

Definition 2.2.11   The greatest common divisor of any two polynomials is the monic polynomial of highest degree such that and .

Proposition 2.2.12 (Division algorithm)   Let be a field. If , are polynomials in with deg deg then there are polynomials , in such that deg deg , deg deg in and

For as in the above theorem, we call the quotient, written , and we call the remainder. written .

Example 2.2.13   This does not hold for rings in the form stated. (See Knuth [Kn], §4.6.1, for a more general form of the division algorithm.) For example, If , and then there is no quotient in such that holds.

Example 2.2.14   Let , . We have
 x
So and .

Theorem 2.2.15 (Euclidean algorithm for polynomials)   Let be a field. If , are polynomials in then there are polynomials , in such that

The proof of this, which is very similar to the proof for the case of the integers given in chapter 1, is omitted. However, here is a sketch of the Euclidean algorithm for polynomials.

Let and . Let .

(1)
Use the division algorithm to compute polynomials and , such that

(2)
If then increment and go to step 1. If then stop.

Since , at some point the above algorithm must terminate. Suppose that and is the smallest such integer. Fact: .

Corollary 2.2.16   Let and be polynomials in , where is a field. is relatively prime to if and only if there are such that .

proof: (only if) This is a special case of the Euclidean algorithm above.

(if) If is a non-zero polynomial satisfying both and then , so . This forces , so .

Here is a reformulation of the Euclidean Algorithm.

Theorem 2.2.17   Let be given, where is a field. Assume , and let , . Repeated Euclidean Algorithm can be regarded as a sequence of polynomials , , and satisfying the following properties.

• For ,

• For some ,

where , .

Remark 2.2.18   This version is useful for decoding alternant codes using Sugiyama's algorithm. However, this goes beyond the scope of this book. For more details, see Roman [Rom], page 399.

david joyner 2008-04-20