Congruence Classes of Polynomials Modulo p(x) over a Field

Recall that if $a, b \in \mathbb{Z}$ and $m \in \mathbb{Z}$ then we say that $a$ is congruent to $b$ modulo $m$ written $a \equiv b \pmod m$ if $m | (a - b)$. In other words, two integers are congruent modulo $m$ if upon division by $m$ we have that $a$ and $b$ have the same remainder.

We now extend this notion to polynomials over a field $F$.

Definition: Let $(F, +, \cdot)$ be a field and let $p \in F[x]$. If $a, b \in F[x]$ then we say that $a$ is Congruent to $b$ modulo $p$ denoted $a(x) \equiv b(x) \pmod {p(x)}$ if $p(x) | (a(x) - b(x))$.

In the following proposition we show that congruence modulo $p$ is an equivalence relation.

Proposition 1: Let $(F, +, \cdot)$ be a field and let $p \in F[x]$. Then congruence modulo $p$ is an equivalence relation.

• Proof: Let $a \in F[x]$. Then clearly $p(x) | (a(x) - a(x)) = 0$. So $a(x) \equiv a(x) \pmod {p(x)}$ so congruence modulo $p$ is reflexive.

• Let $a, b \in F[x]$ and suppose that $a(x) \equiv b(x) \pmod {p(x)}$. Then $p | (a(x) - b(x))$. So there exists a polynomial $q \in F[x]$ such that $p(x)q(x) = a(x) - b(x)$. Hence $p(x)[-q(x)] = b(x) - a(x)$. So $p(x) | (b(x) - a(x))$ and hence $b(x) \equiv a(x) \pmod {p(x)}$. So congruence modulo $p$ is symmetric.

• Lastly, let $a, b, c \in F[x]$ and suppose that $a(x) \equiv b(x) \pmod {p(x)}$ and $b(x) \equiv c(x) \pmod {p(x)}$. Then $p(x) | (a(x) - b(x))$ which implies there exists a $q_1(x) \in F[x]$ such that $p(x)q_1(x) = a(x) - b(x)$ and $p(x) | (b(x) - c(x))$ which implies there exists a $q_2(x) \in F[x]$ such that $p(x)q_2(x) = b(x) - c(x)$. So by substituting the first equation into the second we get:

(1)

\begin{align} \quad p(x)q_2(x) &= b(x) - c(x) \\ &= [a(x) - p(x)q_1(x)] - c(x) \\ \end{align}

• Hence $p(x)[q_1(x) + q_2(x)] = a(x) - c(x)$ so $a(x) \equiv c(x) \pmod {p(x)}$. So congruence modulo $p$ is transitive.

• Therefore equivalence modulo $p$ is an equivalence relation. $\blacksquare$

From the previous proposition we can define congruence classes and the set of all congruence classes modulo $p$.

Definition: Let $(F, +, \cdot)$ be a field and let $p \in F[x]$. For any polynomial $a \in F[x]$ the Congruence Class of $a$ modulo $p$ denoted $[a(x)]_{p(x)}$ is defined as $[a(x)]_{p(x)} = \{ b(x) \in F[x] : b(x) \equiv a(x) \pmod {p(x)}$. The set of all congruence classes modulo $p$ is denoted by $F[x] / <p(x)>$.

When no ambiguity arises we may use the notation "$[a(x)]$" in place of "$[a(x)]_{p(x)}$".

Note that a polynomial $b \in [a(x)]_{p(x)}$ is always of the form:

(2)

\begin{align} \quad b(x) = a(x) + q(x)p(x) \end{align}

Theorem 1: Let $(F, +, \cdot)$ be a field and let $p \in F[x]$ with $p(x) \neq 0$. Let $a \in F[x]$. If $p$ is not a divisor of $a$ then there exists exactly one polynomial $r(x) \in [a(x)]_{p(x)}$ such that $\deg (r) < \deg (p)$.

• Proof: Let $a \in F[x]$. Since $p \in F[x]$ is such that $p(x) \neq 0$, by The Division Algorithm for Polynomials over a Field there exists unique polynomials $q, r \in F[x]$ such that:

(3)

\begin{align} \quad a(x) = p(x)q(x) + r(x) \end{align}

• Where $r(x) = 0$ or $\deg(r) < \deg(p)$. Since $p$ is not a divisor of $a$ we have that $r(x) \neq 0$. We rewrite the equation above as:

(4)

\begin{align} \quad r(x) &= a(x) - p(x)q(x) \\ &= a(x) + [-q(x)]p(x) \end{align}

• So $r(x) \in [a(x)]_{p(x)}$ is such that $\deg (r) < \deg (p)$.

• We now show that only one such $r(x)$ exists. Suppose that $r'(x) \in [a(x)]_{p(x)}$ is such that $\deg (r') < \deg (p)$. Then since $r'(x) \in [a(x)]_{p(x)}$ we have that $r'(x) \equiv a(x) \pmod {p(x)}$.

• Since $r(x) \equiv a(x) \pmod {p(x)}$ and $r'(x) \equiv a(x) \pmod {p(x)}$ we have that $r(x) \equiv r'(x) \pmod {p(x)}$ so $p(x) | (r(x) - r'(x))$. But since $\deg (p) > \deg (r), \deg (r')$ can only happen if $r(x) - r'(x) = 0$, so $r(x) = r'(x)$. $\blacksquare$