# Modular arithmetic with polynomials

In this section, will be a field, unless stated otherwise.

Modular arithmetic with polynomials is very similar to modular arithmetic with integers.

Definition 2.5.1

If then we say is congruent to modulo , written , if divides the polynomial .

Lemma 2.5.2   Let be a ring. Fix a polynomial modulus and let .
• If and then

• If then .
• If and then .

proof: All of these are left as an exercise, except for the last one.

Assume and . Then . By the unique factorization theorem, .

Example 2.5.3   since . Similarly, and .

In general, when computing a polynomial modulo , we may always replace , , , ... by and , , , ... by . For example, .

Example 2.5.4   Let . By the division algorithm, we have , , , , . In general, this pattern of congruences leads to , , for .

For each fixed non-zero , the congruence relation defines an equivalence relation (in the sense of §1.7.2). Let

denote an equivalence class, which we call the congruence class (or residue class) of . Define addition and multiplication of congruence classes by

and

This collection of congruence classes is denoted .

As in the integral case treated in chapter 1, the following result, is a consequence of the Euclidean algorithm.

Lemma 2.5.5   Let be non-zero polynomials. Assume that is not a constant. is relatively prime to if and only if there is a such that .

The polynomial in the above lemma is called the inverse of modulo , written .

Example 2.5.6   is the inverse of modulo in since .

proof: (only if) Assume . There are such that , by the Euclidean algorithm (more precisely, by Corollary 2.2.16). Thus .

(if) Assume . There is a polynomial such that . By Corollary 2.2.16 again, we must have .

Exercise 2.5.7   Let . Compute .

Exercise 2.5.8   Let . Compute .

david joyner 2008-04-20