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)... ...}\ 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))$.