Congruence in F[x]

As we seen in chapter 4, the polynomial ring $F[x]$ shares many properties with the ring of integers $\mathbb{Z}$. We have seen we have division algorithm, Bezout’s theorem, unique factorization, etc. In this chapter, we will see the analog of ${\mathbb{Z}}_n$ in the context of polynomials.

To define congruence in $F[x]$, we will fix a nonzero polynomial $p(x)\in F[x]$ as modulus. One should think this is similar with fixing an integer $n\in \mathbb{Z}$ before defining congruence in $\mathbb{Z}$.

Congruence relation in $F[x]$

Recall the congruence relation in $\mathbb{Z}$: $a\equiv b(\mathrm{mod}n)$ if $n\mid (a-b)$. We can define a similar relation in $F[x]$:

Definition:

Given two polynomials $f(x),g(x)\in F[x]$, we say $f(x)$ is congruent to $g(x)$ modulo a nonzero $p(x)$, denoted as $f(x)\equiv g(x)(\mathrm{mod}p(x))$, if $p(x)\mid (f(x)-g(x))$.

The congruence relation in $\mathbb{Z}$ satisfies the reflexivity, symmetry, and transitivity properties. The same holds for the congruence relation in $F[x]$.

Theorem

The congruence relation in $F[x]$ is an equivalence relation, i.e. we have:

1. Reflexivity: $f(x)\equiv f(x)(\mathrm{mod}p(x))$ for all $f(x)\in F[x]$.
2. Symmetry: If $f(x)\equiv g(x)(\mathrm{mod}p(x))$, then $g(x)\equiv f(x)(\mathrm{mod}p(x))$.
3. Transitivity: If $f(x)\equiv g(x)(\mathrm{mod}p(x))$ and $g(x)\equiv h(x)(\mathrm{mod}p(x))$, then $f(x)\equiv h(x)(\mathrm{mod}p(x))$.

Congruence classes in $F[x]$

Back in 2_1_1_congruence_classes, we spent a lot of time to define the congruence classes $[a]$ in ${\mathbb{Z}}_n$. The key idea is define $[a]\in {\mathbb{Z}}_n$ as the set of all integers congruent to $a$ modulo $n$. We do the same for $F[x]$.

Definition:

Given a polynomial $f(x)\in F[x]$ and a nonzero polynomial $p(x)\in F[x]$, the congruence class of $f(x)$ modulo $p(x)$ is the set:

$$[f(x)]=\{g(x)\in F[x]\mid g(x)\equiv f(x)(\mathrm{mod}p(x))\}.$$

The set of all congruence classes is denoted as $F[x]/(p(x))$.

The congruence class $[f(x)]$ has similar translation invariant property when we add a multiple of $p(x)$:

$$[f(x)+p(x)]=[f(x)].$$

We can keep applying the translation property to get the following:

Proposition

For any polynomial $f(x),g(x)\in F[x]$, we have:

$$f(x)\equiv g(x)(\mathrm{mod}p(x))⟺[f(x)]=[g(x)].$$

One natural question then is how many congruence classes are there in $F[x]$ modulo $p(x)$? In ${\mathbb{Z}}_n$, we have exactly $n$ congruence classes. But things are bit different in $F[x]$, we usually get infinitely many congruence classes modulo $p(x)$ when $F$ is an infinite field.

To make the picture more clear, we have precisely:

$$[0],[1],\cdots [n-1]\in {\mathbb{Z}}_n$$

as distinct congruence classes in ${\mathbb{Z}}_n$. They are precisely the possible remainders when we divide an integer by $n$.

So the correct generalization route is recall the [[4_1_poly_division#Division algorithm in $F[x]$|division algorithm]] in $F[x]$, and see what are the possible remainders when we divide a polynomial by $p(x)$.

Theorem

As a set, $F[x]/(p(x))$ can be identified with all polynomials $r(x)\in F[x]$ such that $\mathrm{deg}(r)<\mathrm{deg}(p)$.

Proof of the theorem

Let $f(x)\in F[x]$ be any polynomial. By the division algorithm, we can write:

$$f(x)=q(x)p(x)+r(x)$$

where $q(x),r(x)\in F[x]$ and $\mathrm{deg}(r)<\mathrm{deg}(p)$. We have:

$$f(x)\equiv r(x)(\mathrm{mod}p(x)).$$

Therefore, $[f(x)]=[r(x)]$. This shows that every congruence class in $F[x]/(p(x))$ can be represented by a polynomial $r(x)$ with $\mathrm{deg}(r)<\mathrm{deg}(p)$.

We now show two distinct polynomials $r(x),s(x)$ with $\mathrm{deg}(r)<\mathrm{deg}(p)$ and $\mathrm{deg}(s)<\mathrm{deg}(p)$ give distinct congruence classes. Suppose $r(x)\equiv s(x)(\mathrm{mod}p(x))$, then $p(x)\mid (r(x)-s(x))$. Since $\mathrm{deg}(r-s)<\mathrm{deg}(p)$, we must have $r(x)-s(x)=0$, i.e. $r(x)=s(x)$. $■$

In particular, we will get back to the base field $F$ if we take the modulus $p(x)=x-a$ for some $a\in F$.

Corollary

$F[x]/(x-a)$ is isomorphic to $F$.

$F[x]/(p(x))$ as a ring

We have shown the congruence class ${\mathbb{Z}}_n$ admits a natural ring structure. We can do the same for $F[x]/(p(x))$.

Theorem

The set $F[x]/(p(x))$ is a ring with addition and multiplication defined as:

$$[f(x)]+[g(x)]=[f(x)+g(x)],[f(x)]\cdot [g(x)]=[f(x)\cdot g(x)].$$

The ring $F[x]/(p(x))$ is called the quotient ring of $F[x]$ by the ideal generated by $p(x)$, denoted as $F[x]/(p(x))$. Though we will define the ideal in the next chapter.