§5.1 Congruence in Polynomials and Congruence Classes

The concept of congruence of integers depends only on some basic facts about divisibility in \(\mathbb{Z}\). If \(F\) is a field, then the polynomial ring \(F[x]\) has essentially the same divisibility properties as does \(\mathbb{Z}\). So it is not surprising that the concept of congruence in \(\mathbb{Z}\) and its basic properties (Section 2.1) can be carried over to \(F[x]\) almost verbatim.

Definition

Let \(F\) be a field and \(f(x), g(x), p(x) \in F[x]\) with \(p(x)\) nonzero. Then \(f(x)\) is congruent to \(g(x)\) modulo \(p(x)\)—written \(f(x) \equiv g(x) \pmod{p(x)}\)—provided that \(p(x)\) divides \(f(x) - g(x)\).

Example 1

In \(\mathbb{Q}[x]\), \(x^2 + x + 1 \equiv x + 2 \pmod{x + 1}\) because

\[ (x^2 + x + 1) - (x + 2) = x^2 - 1 = (x + 1)(x - 1). \]

Example 2

In \(\mathbb{R}[x]\), \(3x^4 + 4x^2 + 2x + 2 \equiv 3x^3 + 3x^2 + 3x + 4 \pmod{x^2 + 1}\) because division shows that

\[ (3x^4 + 4x^2 + 2x + 2) - (3x^3 + 3x^2 + 3x + 4) = (x^2 + 1)(3x^2 - x - 2). \]

Theorem 5.1

Let \(F\) be a field and \(p(x)\) a nonzero polynomial in \(F[x]\). Then the relation of congruence modulo \(p(x)\) is

  1. reflexive: \(f(x) \equiv f(x) \pmod{p(x)}\) for all \(f(x) \in F[x]\);
  2. symmetric: if \(f(x) \equiv g(x) \pmod{p(x)}\), then \(g(x) \equiv f(x) \pmod{p(x)}\);
  3. transitive: if \(f(x) \equiv g(x) \pmod{p(x)}\) and \(g(x) \equiv h(x) \pmod{p(x)}\), then \(f(x) \equiv h(x) \pmod{p(x)}\).

Proof

Adapt the proof of Theorem 2.1 with \(p(x), f(x), g(x), h(x)\) in place of \(n, a, b, c\). \(\blacksquare\)

Theorem 5.2

Let \(F\) be a field and \(p(x)\) a nonzero polynomial in \(F[x]\). If \(f(x) \equiv g(x) \pmod{p(x)}\) and \(h(x) \equiv k(x) \pmod{p(x)}\), then

  1. \(f(x) + h(x) \equiv g(x) + k(x) \pmod{p(x)}\);
  2. \(f(x)h(x) \equiv g(x)k(x) \pmod{p(x)}\).

Proof

Adapt the proof of Theorem 2.2 with \(p(x), f(x), g(x), h(x), k(x)\) in place of \(n, a, b, c, d\). \(\blacksquare\)

Definition

Let \(F\) be a field and \(f(x), p(x) \in F[x]\) with \(p(x)\) nonzero. The congruence class (or residue class) of \(f(x)\) modulo \(p(x)\) is denoted \([f(x)]\) and consists of all polynomials in \(F[x]\) that are congruent to \(f(x)\) modulo \(p(x)\), that is,

\[ [f(x)] = \{g(x) \mid g(x) \in F[x] \text{ and } g(x) \equiv f(x) \pmod{p(x)} \}. \]

Since \(g(x) \equiv f(x) \pmod{p(x)}\) means that \(g(x) - f(x) = k(x)p(x)\) for some \(k(x) \in F[x]\), or, equivalently, that \(g(x) = f(x) + k(x)p(x)\), we see that

\[ [f(x)] = \{g(x) \mid g(x) = f(x) + k(x)p(x), \text{ for some } k(x) \in F[x]\}. \]

Example 3

Consider congruence modulo \(x^2 + 1\) in \(\mathbb{R}[x]\). The congruence class of \(2x + 1\) is the set

\[ \{(2x + 1) + k(x)(x^2 + 1) \mid k(x) \in \mathbb{R}[x]\}. \]

The Division Algorithm shows that the elements of this set are the polynomials in \(\mathbb{R}[x]\) that leave remainder \(2x + 1\) when divided by \(x^2 + 1\).

Example 4

Consider congruence modulo \(x^2 + x + 1\) in \(\mathbb{Z}_2[x]\). To find the congruence class of \(x^2\), we note that \(x^2 \equiv x + 1 \pmod{x^2 + x + 1}\) because \(x^2 - (x + 1) = x^2 - x - 1 = (x^2 + x + 1)(1)\) (remember that \(1 + 1 = 0\) in \(\mathbb{Z}_2\), so that \(1 = -1\)). Therefore, \(x^2\) is a member of the congruence class \([x^2]\). In fact, the next theorem shows that \([x + 1] = [x^2]\).

Theorem 5.3

\(f(x) \equiv g(x) \pmod{p(x)}\) if and only if \([f(x)] = [g(x)]\).

Proof

Adapt the proof of Theorem 2.3 with \(f(x), g(x), p(x)\) and Theorem 5.1 in place of \(a, c, n\), and Theorem 2.1. \(\blacksquare\)

Corollary 5.4

Two congruence classes modulo \(p(x)\) are either disjoint or identical.

Proof

Adapt the proof of Corollary 2.4. \(\blacksquare\)

Under congruence modulo \(n\) in \(\mathbb{Z}\), there are exactly \(n\) distinct congruence classes (Corollary 2.5). These classes are \([0], [1], \dots, [n - 1]\). Note that there is a class for each possible remainder under division by \(n\). In \(F[x]\), the possible remainders under division by a polynomial of degree \(n\) are all the polynomials of degree less than \(n\) (and, of course, \(0\)). So the analogue of Corollary 2.5 is

Corollary 5.5

Let \(F\) be a field and \(p(x)\) a polynomial of degree \(n\) in \(F[x]\), and consider congruence modulo \(p(x)\).

  1. If \(f(x) \in F[x]\) and \(r(x)\) is the remainder when \(f(x)\) is divided by \(p(x)\), then \([f(x)] = [r(x)]\).
  2. Let \(S\) be the set consisting of the zero polynomial and all the polynomials of degree less than \(n\) in \(F[x]\). Then every congruence class modulo \(p(x)\) is the class of some polynomial in \(S\), and the congruence classes of different polynomials in \(S\) are distinct.

Proof

  1. By the Division Algorithm, \(f(x) = p(x)q(x) + r(x)\), with \(r(x) = 0_F\) or \(\deg r(x) < n\). Thus, \(f(x) - r(x)=p(x)q(x)\), so that \(f(x) \equiv r(x) \pmod{p(x)}\). By Theorem 5.3, \([f(x)]=[r(x)]\).
  2. Since \(r(x) = 0_F\) or \(\deg r(x) < n\), we see that \(r(x) \in S\). Hence, every congruence class is equal to the congruence class of a polynomial in \(S\). Two different polynomials in \(S\) cannot be congruent modulo \(p(x)\) because their difference has degree less than \(n\), and hence is not divisible by \(p(x)\). Therefore, different polynomials in \(S\) must be in distinct congruence classes by Theorem 5.3. \(\blacksquare\)

The set of all congruence classes modulo \(p(x)\) is denoted

\[ F[x]/(p(x)), \]

which is the notational analogue of \(\mathbb{Z}_n\).

Example 5

Consider congruence modulo \(x^2 + 1\) in \(\mathbb{R}[x]\). There is a congruence class for each possible remainder on division by \(x^2 + 1\). Note, the possible remainders are polynomials of the form \(rx + s\) (with \(r, s \in \mathbb{R}\)). So, \(\mathbb{R}[x]/(x^2 + 1)\) consists of infinitely many distinct congruence classes, including

\[ [0], [x], [x + 1], [5x + 3], \left[ \frac{7}{9}x + 2 \right], [x - 7], \dots \]

Corollary 5.5 states that \([rx + s] = [cx + d]\) if and only if \(rx + s\) is equal (not just congruent) to \(cx + d\). By the definition of polynomial equality, \(rx + s = cx + d\) if and only if \(r = c\) and \(s = d\). Therefore, every element of \(\mathbb{R}[x]/(x^2 + 1)\) can be written uniquely in the form \([rx + s]\).

Example 6

Consider congruence modulo \(x^2 + x + 1\) in \(\mathbb{Z}_2[x]\). The possible remainders on division by \(x^2 + x + 1\) are the polynomials of the form \(ax + b\) with \(a, b \in \mathbb{Z}_2\). Thus there are only four possible remainders: \(0, 1, x\), and \(x + 1\). Therefore, \(\mathbb{Z}_2[x]/(x^2 + x + 1)\) consists of four congruence classes: \([0], [1], [x],\) and \([x + 1]\).

Example 7

The pattern in Example 6 works in the general case. Let \(n\) be a prime integer, so that \(\mathbb{Z}_n\) is a field and the Division Algorithm holds in \(\mathbb{Z}_n[x]\). If \(p(x) \in \mathbb{Z}_n[x]\) has degree \(k\), then the possible remainders on division by \(p(x)\) are of the form \(a_0 + a_1 x + \dots + a_{k-1}x^{k-1}\) , with \(a_i \in \mathbb{Z}_n\). There are \(n\) possibilities for each of the \(k\) coefficients \(a_0, \dots, a_{k-1}\), and so there are \(n^k\) different polynomials of this form. Consequently, by Corollary 5.5, there are exactly \(n^k\) distinct congruence classes modulo \(p(x)\) in \(\mathbb{Z}_n[x]/(p(x)\).