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

# 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] /$.

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)$.
(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$