ยง5.2 Congruence-Class Arithmetic
Congruence in the integers led to the rings \(\mathbb{Z}_n\). Similarly, congruence in \(F[x]\) also produces new rings and fields. These turn out to be much richer in structure than the rings \(\mathbb{Z}_n\). The development here closely parallels Section 2.2.
Theorem 5.6
Let \(F\) be a field and \(p(x)\) a nonconstant polynomial in \(F[x]\). If \(f(x) = [g(x)]\) and \(h(x) = [k(x)]\) in \(F[x]/(p(x))\), then,
\[ [f(x) + h(x)] = [g(x) + k(x)] \]and
\[ [f(x)h(x)] = [g(x)k(x)]. \]Proof: Copy the proof of Theorem 2.6, with Theorems 5.2 and 5.3 in place of Theorems 2.2 and 2.3. \(\blacksquare\)
Because of Theorem 5.6, we can now define addition and multiplication of congruence classes just as we did in the integers and be certain that these operations are independent of the choice of representatives in each congruence class.
Definition
Let \(F\) be a field and \(p(x)\) a nonconstant polynomial in \(F[x]\). Addition and multiplication in \(F[x]/(p(x))\) are defined by
\[ [f(x) + g(x)] = [f(x) + g(x)], \] \[ [f(x)g(x)] = [f(x)g(x)]. \]Example 1
Consider congruence modulo \(x^2 + 1\) in \(\mathbb{R}[x]\). The sum of the classes \([2x + 1]\) and \([3x + 5]\) is the class \[ [(2x + 1) + (3x + 5)] = [5x + 6]. \] The product is \[ [(2x + 1)][3x + 5] = [(2x + 1)(3x + 5)] = [6x^2 + 13x + 5]. \]
As noted in Example 5 of Section 5.1, every congruence class in \(\mathbb{R}[x]/(x^2 + 1)\) can be written in the form \([ax + b]\). To express the class \([6x^2 + 13x + 5]\) in this form, we divide \(6x^2 + 13x + 5\) by \(x^2 + 1\) and find that
\[ 6x^2 + 13x + 5 = (x^2 - 1)(6) + (13x - 1). \]It follows that \(6x^2 + 13x + 5 \equiv 13x - 1 \pmod{x^2 + 1}\), and hence \([6x^2 + 13x + 5] = [13x - 1]\).
Example 2
In Example 6 of Section 5.1, we saw that \(\mathbb{Z}_2[x]/(x^2 + x + 1)\) consists of four classes: \([0], [1], [x],\) and \([x + 1]\). Using the definition of addition of classes, we see that \([x + 1] + [1] = [x + 1 + 1] = [x]\) (remember that \(1 + 1 = 0\) in \(\mathbb{Z}_2\). Similar calculations produce the following addition table for \(\mathbb{Z}_2[x]/(x^2 + x + 1)\):
\[ \begin{array}{c|cccc} + & [0] & [1] & [x] & [x + 1] \\ \hline [0] & [0] & [1] & [x] & [x + 1] \\ [1] & [1] & [0] & [x + 1] & [x] \\ [x] & [x] & [x + 1] & [0] & [1] \\ [x + 1] & [x + 1] & [x] & [1] & [0] \\ \end{array} \] \[ \begin{array}{c|cccc} \times & [0] & [1] & [x] & [x + 1] \\ \hline [0] & [0] & [0] & [0] & [0] \\ [1] & [0] & [1] & [x] & [x + 1] \\ [x] & [0] & [x] & [x + 1] & [1] \\ [x + 1] & [0] & [x + 1] & [1] & [x] \\ \end{array} \]To fill in the rest of the table, note, for example, that
\[ [x] \cdot [x + 1] = [(x)(x + 1)] = [x^2 + x]. \]Now division or simple addition in \(\mathbb{Z}_2[x]\) shows that \(x^2 + x = (x^2 + x + 1) + 1\). Therefore, \(x^2 + x = 1 \pmod{x^2 + x + 1}\), so that \([x^2 + x] = [1]\). A similar calculation shows that \([x] \cdot [x] = [x^2] = [x + 1]\) (because \(x^2 = (x + 1)(x + 1)\) in \(\mathbb{Z}_2[x]\). Verify that \([x + 1][x + 1] = [x]\).
If you examine the tables in the preceding example, you will see that \(\mathbb{Z}_2[x]/(x^2 + x + 1)\) is a commutative ring with identity (in fact, a field). In view of our experience with \(\mathbb{Z}_n\) and \(\mathbb{Z}_{mn}\), this is not too surprising. What is unexpected is the upper left-hand corners of the two tables (the sums and products of \([0]\) and \([1]\)). It is easy to see that the subset \(F^* = \{[0], [1]\}\) is actually a subring of \(\mathbb{Z}_2[x]/(x^2 + x + 1)\) and that \(F^*\) is isomorphic to \(\mathbb{Z}_2\) (the tables for the two systems are identical except for the brackets in \(F^*\)). These facts illustrate the next theorem.
Theorem 5.7
Let \(F\) be a field and \(p(x)\) a nonconstant polynomial in \(F[x]\). Then the set \(F[x]/(p(x))\) of congruence classes modulo \(p(x)\) is a commutative ring with identity. Furthermore, \(F[x]/(p(x))\) contains a subring \(F^*\) that is isomorphic to \(F\).
Proof (continued)
To prove that \(F[x]/(p(x))\) is a commutative ring with identity, adapt the proof of Theorem 2.7 to the present case. Let \(F^*\) be the subset of \(F[x]/(p(x))\) consisting of the congruence classes of all the constant polynomials; that is, \(F^* = \{[a] \mid a \in F\}\). Verify that \(F^*\) is a subring of \(F[x]/(p(x)\) (Exercise 10). Define a map \(\varphi: F^* \to F\) by \(\varphi([a]) = a\). This definition shows that \(\varphi\) is surjective. The definitions of addition and multiplication in \(F[x]/(p(x))\) show that
\[ \varphi([a + b]) = [a + b] = [a] + [b] = \varphi([a]) + \varphi([b]) \] \[ \varphi([ab]) = [ab] = [a][b] = \varphi([a]) \cdot \varphi([b]) \]Therefore, \(\varphi\) is a homomorphism.
To see that \(\varphi\) is injective, suppose \(\varphi([a]) = \varphi([b])\). Then \([a] = [b]\), so \(a \equiv b \pmod{p(x)}\). Hence, \(p(x)\) divides \(a - b\). However, \(p(x)\) has degree \(\geq 1\), and \(a - b \in F\). This is impossible unless \(a - b = 0\). Therefore, \(a = b\) and \(\varphi\) is injective. Thus \(\varphi: F^* \to F\) is an isomorphism.
We began with a field \(F\) and a polynomial \(p(x)\) in \(F[x]\). We have now constructed a ring \(F[x]/(p(x))\) that contains an isomorphic copy of \(F\). What we would really like is a ring that contains the field \(F\) itself. There are two possible ways to accomplish this, as illustrated in the following example.
Example 3
In Example 2, we used the polynomial \(x^2 + x + 1\) in \(\mathbb{Z}_2[x]\) to construct the ring \(\mathbb{Z}_2[x]/(x^2 + x + 1)\), which contains a subset \(F^* = \{[0], [1]\}\) that is isomorphic to \(\mathbb{Z}_2\). Suppose we identify \(\mathbb{Z}_2\) with its isomorphic copy \(F^*\) inside \(\mathbb{Z}_2[x]/(x^2 + x + 1)\) and write the elements of \(F^*\) as if they were in \(\mathbb{Z}_2\). Then the tables in Example 2 become
\[ \begin{array}{c|cccc} + & 0 & 1 & [x] & [x + 1] \\ \hline 0 & 0 & 1 & [x] & [x + 1] \\ 1 & 1 & 0 & [x + 1] & [x] \\ [x] & [x] & [x + 1] & 0 & 1 \\ [x + 1] & [x + 1] & [x] & 1 & 0 \\ \end{array} \] \[ \begin{array}{c|cccc} \times & 0 & 1 & [x] & [x + 1] \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & [x] & [x + 1] \\ [x] & 0 & [x] & [x + 1] & 1 \\ [x + 1] & 0 & [x + 1] & 1 & [x] \\ \end{array} \]We now have a ring that has \(\mathbb{Z}_2\) as a subset. If this procedure makes you a bit uneasy (is \(\mathbb{Z}_2\) really a subset?), you can use the following alternate route to the same end. Let \(E\) be any four-element set that actually contains \(\mathbb{Z}_2\) as a subset, say \(E = \{0, 1, r, s\}\). Define addition and multiplication by
\[ \begin{array}{c|cccc} + & 0 & 1 & r & s \\ \hline 0 & 0 & 1 & r & s \\ 1 & 1 & 0 & r & s \\ r & r & s & 0 & 1 \\ s & s & r & 1 & 0 \\ \end{array} \] \[ \begin{array}{c|cccc} - & 0 & 1 & r & s \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & r & s \\ r & 0 & r & s & 1 \\ s & 0 & s & 1 & r \\ \end{array} \]A comparison of the tables for \(\mathbb{Z}_2[x]/(x^2 + x + 1)\) and those for \(E\) shows that these two rings are isomorphic (replacing \([x]\) by \(r\) and \([x + 1]\) by \(s\) rearranges one set of tables into the other). Therefore, \(E\) is essentially the same ring we obtained before. However, \(E\) does contain \(\mathbb{Z}_2\) as an honest-to-goodness subset, without any identification.
What was done in the preceding example can be done in the general case. Given a field \(F\) and a polynomial \(p(x)\) in \(F[x]\), we can construct a ring that contains \(F\) as a subset. The customary way to do this is to identify \(F\) with its isomorphic copy \(F^*\) inside \(F[x]/(p(x))\) and to consider \(F\) to be a subset of \(F[x]/(p(x))\). If doing this makes you uncomfortable, keep in mind that you can always build a ring isomorphic to \(F[x]/(p(x))\) that genuinely contains \(F\) as a subset, as in the preceding example. Because this latter process is slightly more cumbersome, we shall follow the usual custom and identify \(F\) with \(F^*\) hereafter. Consequently, when \(a \in F\), we shall write \(a[x]\) instead of \([a][x]\) and \(a + b[x]\) instead of \([a] + [b][x] = [a + b]\). Then Theorem 5.7 can be reworded:
Theorem 5.8
Let \(F\) be a field and \(p(x)\) a nonconstant polynomial in \(F[x]\). Then \(F[x]/(p(x))\) is a commutative ring with identity that contains \(F\).
If \(a\) and \(n\) are integers such that \(\gcd(a, n) = 1\), then by Theorem 2.10, \([a]\) is a unit in \(\mathbb{Z}_n\). Here is the analogue for polynomials. \(\blacksquare\)
Theorem 5.9
Let \(F\) be a field and \(p(x)\) a nonconstant polynomial in \(F[x]\). If \(f(x) \in F[x]\) and \(f(x)\) is relatively prime to \(p(x)\), then \([f(x)]\) is a unit in \(F[x]/(p(x))\).
Proof
By Theorem 4.8, there are polynomials \(u(x)\) and \(v(x)\) such that \(f(x)u(x) + p(x)v(x) = 1\). Hence, \([f(x)][u(x)] = 1 = [p(x)][v(x)]\), which implies that \([f(x)][u(x)] = [1]\) by Theorem 5.3. Therefore, \([f(x)][u(x)] = [1]\), so that \([f(x)]\) is a unit in \(F[x]/(p(x))\). \(\blacksquare\)
Example 4
Since \(x^2 - 2\) is irreducible in \(\mathbb{Q}[x]\), \(2x + 5\) and \(x^2 - 2\) are relatively prime in \(\mathbb{Q}[x]\) (Why?). Hence, \([2x + 5]\) is a unit in the ring \(\mathbb{Q}[x]/(x^2 - 2)\). The proof of Theorem 5.9 shows that its inverse is \([u(x)]\), where \((2x + 5)u(x) + (x^2 - 2)v(x) = 1\). Using the Euclidean Algorithm as in Exercise 15 of Section 1.2, we find that:
\[ (2x + 5)\left(\frac{2}{17}x + \frac{5}{17}\right) + (x^2 - 2)\left(\frac{4}{17}\right) = 1. \]Therefore, \(\left[\frac{2}{17}x + \frac{5}{17}\right]\) is the inverse of \([2x + 5]\) in \(\mathbb{Q}[x]/(x^2 - 2)\).