Modular arithmetic with polynomials

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

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

Definition 2.5.1  

If $a(x),b(x),m(x)\in F[x]$ then we say $a(x)$ is congruent to $b(x)$ modulo $m(x)$ , written $a(x)\equiv b(x) ({\rm mod} m(x))$ , if $m(x)$ divides the polynomial $a(x)-b(x)$ .

Lemma 2.5.2   Let $F$ be a ring. Fix a polynomial modulus $m(x)\not=0$ and let $a(x),b(x),c(x),d(x)\in F[x]$ .

• If $a(x)\equiv c(x) ({\rm mod} m(x))$ and $(x)b\equiv d(x) ({\rm mod} m(x))$ then
  $$\begin{array}{c} a(x)+b(x)\equiv c(x)+d(x) ({\rm mod} m(... ...(x))\\ a(x)^2\equiv c(x)^2 ({\rm mod} m(x)). \end{array}$$

• If $a(x)+c(x)\equiv b(x)+c(x) ({\rm mod} m(x))$ then $a(x)\equiv b(x) ({\rm mod} m(x))$ .
• If $a(x)c(x)\equiv b(x)c(x) ({\rm mod} m(x))$ and $gcd(c(x),m(x))=1$ then $a(x)\equiv b(x) ({\rm mod} m(x))$ .

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

Assume $a(x)c(x)\equiv b(x)c(x) ({\rm mod} m(x))$ and $gcd(c(x),m(x))=1$ . Then $m(x)\vert(a(x)c(x)-b(x)c(x))=c(x)(a(x)-b(x))$ . By the unique factorization theorem, $m(x)\vert(a(x)-b(x))$ . $\Box$

Example 2.5.3   $2x^2\equiv 2 ({\rm mod} x^2-1)$ since $(x^2-1)\vert(2x^2-2)$ . Similarly, $x^4\equiv 1 ({\rm mod} x^2-1)$ and $x^3\equiv x ({\rm mod} x^2-1)$ .

In general, when computing a polynomial modulo $x^2-1$ , we may always replace $x^2$ , $x^4$ , $x^6$ , ... by $1$ and $x^3$ , $x^5$ , $x^7$ , ... by $x$ . For example, $7x^8+3x^7-5x^6+2x^5-2x^4+x^3-4x^2-x+9 \equiv (3+2+1-1)x+(7-5-2-4+9)\ \equiv 5x+5 ({\rm mod} x^2-1)$ .

Example 2.5.4   Let $m(x)=x^2+1$ . By the division algorithm, we have $x\equiv x ({\rm mod} x^2+1)$ , $x^2\equiv -1 ({\rm mod} x^2+1)$ , $x^3\equiv -x ({\rm mod} x^2+1)$ , $x^4\equiv -x^2\equiv 1 ({\rm mod} x^2+1)$ , $x^5\equiv -x^3\equiv x ({\rm mod} x^2+1)$ . In general, this pattern of congruences leads to $x^{2n}\equiv (-1)^n ({\rm mod} x^2+1)$ , $x^{2n+1}\equiv (-1)^nx ({\rm mod} x^2+1)$ , for $n>0$ .

For each fixed non-zero $m(x)\in F[x]$ , the congruence relation $\equiv$ defines an equivalence relation (in the sense of §1.7.2). Let

$$\overline{a(x)}=a(x)+m(x)F[x].$$

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

$$(a(x)+m(x)F[x])+b(x)+m(x)F[x])=a(x)+b(x)+m(x)F[x],$$

and

$$(a(x)+m(x)F[x])(b(x)+m(x)F[x])=a(x)b(x)+m(x)F[x].$$

This collection of congruence classes is denoted $F[x]/(m(x))$ .

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

Lemma 2.5.5   Let $a(x),m(x)\in F[x]$ be non-zero polynomials. Assume that $m(x)$ is not a constant. $a(x)$ is relatively prime to $m(x)$ if and only if there is a $b(x)\in F[x]$ such that $a(x)b(x) \equiv 1 ({\rm mod} m(x))$ .

The polynomial $b(x)$ in the above lemma is called the inverse of $a(x)$ modulo $m(x)$ , written $b(x)=a(x)^{-1} ({\rm mod} m(x))$ .

Example 2.5.6   $-x$ is the inverse of $x$ modulo $x^2+1$ in $\mathbb{R}[x]$ since $(-x)\cdot x = -x^2 \equiv 1 ({\rm mod} x^2+1)$ .

proof: (only if) Assume $gcd(a(x),m(x))=1$ . There are $p(x),q(x)\in F[x]$ such that $a(x)p(x)+m(x)q(x)=1$ , by the Euclidean algorithm (more precisely, by Corollary 2.2.16). Thus $m(x)\vert(a(x)p(x)-1)$ .

(if) Assume $a(x)p(x) \equiv 1 ({\rm mod} m(x))$ . There is a polynomial $q(x)$ such that $a(x)p(x)-1=m(x)q(x)$ . By Corollary 2.2.16 again, we must have $gcd(a(x),m(x))=1$ . $\Box$

Exercise 2.5.7   Let $m(x)=x^2+1\in \mathbb{R}[x]$ . Compute $(x+1)^{-1} ({\rm mod} m(x))$ .

Exercise 2.5.8   Let $m(x)=x^2+x+1\in \mathbb{F}_2[x]$ . Compute $x^{-1} ({\rm mod} m(x))$ .