Section 15.7. Finite Fields
Exercise 15.7.1 The construction (15.7.2) shows that \(\mathbb{F}_4^+ \cong C_2 \times C_2 \cong V_4\).
Exercise 15.7.2 The eight elements of \(\mathbb{F}_8\) are roots of \(x^8 - x\), whose factorization into irreducibles over \(\mathbb{F}_2\) is shown by (15.7.7). Each element of \(\mathbb{F}_8\) therefore has as its minimal polynomial the factor on the right-hand side of (15.7.7) that it satisfies. Clearly the minimal polynomials of 0 and 1 are respectively \(x\) and \(x - 1\), and we are given that \(\beta\) is a root of \(x^3 + x + 1\). Direct computation shows that \begin{align*} (1 + \beta)^3 &= \beta^2 \\ (\beta^2)^3 &= 1 + \beta^2 \\ (1 + \beta^2)^3 &= \beta + \beta^2 \\ (\beta + \beta^2)^3 &= 1 + \beta + \beta^2 \\ (1 + \beta + \beta^2)^3 &= \beta \end{align*} so \(\beta, \beta^2, \beta + \beta^2\) satisfy \(x^3 + x + 1 = 0\) and therefore have the latter as their minimal polynomial, and by process of elimination, the minimal polynomial of \(1 + \beta, 1 + \beta^2, 1 + \beta + \beta^2\) must be \(x^3 + x^2 + 1\).
Exercise 15.7.3 Computation in \(\mathbb{F}_{13}\) is just computation in the integers modulo 13, so one way to solve this problem is to observe that Fermat's little theorem gives \(2^{12} \cong 1 \pmod{13}\) so that \(2^{13} \cong 2 \pmod{13}\), and 2 is a 13th root of 2 in \(\mathbb{F}_{13}\). Equivalently, in terms of the results of this chapter, each element of \(\mathbb{F}_{13}\) satisfies the polynomial \(x^{13} - x = 0\), so in particular \(2^{13} - 2 = 0\), so 2 is its own 13th root.
Exercise 15.7.4 The polynomial \(x^{27} - x\) factors over \(\mathbb{F}_3\) into a product of the irreducible polynomials over \(\mathbb{F}_3\) of degree 1 or 3, according to Theorem 15.7.3(b). There are three irreducible polynomials of degree 1, namely \(x, x+1, x+2\), so the product of the irreducible cubic polynomials must have degree 24, so there are exactly 8 of them.
The same logic applied to \(x^{125} - x\) shows that there are 40 irreducible cubic polynomials over \(\mathbb{F}_5\).
Exercise 15.7.5 The irreducible factors of \(x^9 - x\) over \(\mathbb{F}_3\) will be the irreducible polynomials of degree 1 or 2 over \(\mathbb{F}_3\) according to Theorem 15.7.3(b). There are three irreducible polynomials of degree 1, namely \(x, x+1, x+2\). The quadratic polynomials obtained by multiplying two of these linear polynomials will not be irreducible; these are \(x^2, x^2 + x, x^2 + 2x, x^2 + 2x + 1, x^2 + 2, x^2 + x + 1\). The other three, namely \(x^2 + 1, x^2 + x + 2, x^2 + 2x + 2\), must be irreducible. So the factorization is: \[ x^9 - x = x(x+1)(x+2)(x^2+1)(x^2+x+2)(x^2+2x+2) \]
A similar exercise can be performed for \(x^{27} - x\); the idea is to find all cubic polynomials that are irreducible over \(\mathbb{F}_3\); there should be 8 of them. Details are left for the reader.
Exercise 15.7.6 Over \(\mathbb{F}_2\) we have the factorization (15.7.9), \[ x^{16} - x = x(x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^4+x^3+1)(x^4+x+1) \] The first three factors on the RHS are the factors of \(x^4 - x\). Over \(\mathbb{F}_4\), \(x^4 - x\) splits as the product of the four distinct monic linear polynomials (Theorem 15.7.3(a)). Some of the quartic factors may also split further in \(\mathbb{F}_4\). Indeed, as \(\mathbb{F}_{16}\) contains \(\mathbb{F}_4\) as a subfield (Theorem 15.7.3(e)), the cardinalities show that it is a quadratic extension, so each element of \(\mathbb{F}_{16}\) or equivalently root of \(x^{16} - x\) has degree 1 or 2 over \(\mathbb{F}_4\). Since we have already identified the four elements of degree 1, the remaining twelve elements must have degree 2, and the three quartic factors of \(x^{16} - x\) must split into two irreducible quadratics each. In fact, trial and error produces \begin{align*} x^4 + x + 1 &= (x^2 + x + \alpha)(x^2 + x + \alpha + 1) \\ x^4 + x^3 + 1 &= (x^2 + \alpha x + \alpha) (x^2 + (\alpha + 1)x + \alpha + 1) \\ x^4 + x^3 + x^2 + x + 1 &= (x^2 + \alpha x + 1)(x^2 + (\alpha + 1)x + 1) \end{align*} where \(\alpha\) is as in (15.7.2). So the full factorization over \(\mathbb{F}_4\) is \[ x^{16} - x = x(x-1)(x-\alpha)(x-\alpha-1)(x^2+x+\alpha)(x^2+x+\alpha+1) (x^2+\alpha x+\alpha)(x^2+(\alpha+1)x+\alpha+1) (x^2+\alpha x + 1)(x^2 + (\alpha+1)x + 1) \]
Now let \(\beta\) be an element of \(\mathbb{F}_{16}\) of degree \(d\) over \(\mathbb{F}_2\) with \(d = 2\) or \(d = 4\), and let \(\gamma\) be an element of \(\mathbb{F}_8\) of degree 3 over \(\mathbb{F}_2\), so that \(\mathbb{F}_8 = \mathbb{F}_2(\gamma)\). Since 2 and 4 are relatively prime to 3, we have \([\mathbb{F}_2(\beta, \gamma) : \mathbb{F}_2] = 3d\). This implies that \([\mathbb{F}_2(\beta, \gamma) : \mathbb{F}_2(\gamma)] = d\), so the degree of \(\beta\) is the same over \(\mathbb{F}_8\) as it is over \(\mathbb{F}_2\). Therefore, the factorization of \(x^{16} - x\) into irreducibles over \(\mathbb{F}_8\) is the same as over \(\mathbb{F}_2\).
Exercise 15.7.7 In the proof of Theorem 15.7.3(a) it was shown that the \(q - 1\) nonzero elements of \(\mathbb{F}_q\) are roots of \(x^{q-1} - 1\). Therefore \[ x^{q-1} - 1 = \prod_{\alpha \in K^\times} (x - \alpha) \] Now the constant term of the RHS is just \(\prod_{\alpha \in K^\times} \alpha\), so this equals the constant term of the LHS, which is \(-1\).
Exercise 15.7.8 The fields \(K\) and \(L\) are finite fields of order 8. Let \(\beta\) be a root of \(x^3 + x + 1\) in \(K\). As worked out in Exercise 15.7.2, the element \(1 + \beta\) is a root of \(x^3 + x^2 + 1\), and it also has degree 3 over \(\mathbb{F}_2\), so \(K = \mathbb{F}_2(1 + \beta)\). Let \(\gamma\) be a root of \(x^3 + x^2 + 1\) in \(L\), so that \(L = \mathbb{F}_2(\gamma)\). The field extensions \(K\) and \(L\) of \(\mathbb{F}_2\) are isomorphic according to Proposition 15.2.8, since \(1 + \beta\) and \(\gamma\) have the same minimal polynomial over \(\mathbb{F}_2\). The isomorphism fixes \(0\) and \(1\) and sends \(1 + \beta\) to \(\gamma\). Since \(1 + \beta\) generates \(\mathbb{F}_8\), this determines the isomorphism uniquely and constructively.
Since there is only one finite field of order 8 up to isomorphism, the number of isomorphisms of \(K\) and \(L\) is just the number of automorphisms of \(\mathbb{F}_8\). Again, letting \(\beta\) denote a root of \(x^3 + x + 1\) in \(\mathbb{F}_8\), each automorphism must map \(\beta\) to some root of \(x^3 + x + 1\), of which there are three, namely \(\beta, \beta^2, \beta + \beta^2\), as we found in Exercise 15.7.2. Proposition 15.2.8 guarantees that any of these choices can be extended to an automorphism of \(\mathbb{F}_2(\beta)\), which is just \(\mathbb{F}_8\); obviously this automorphism will be unique. So there are three automorphisms of \(\mathbb{F}_8\), or equivalently three isomorphisms of \(K\) and \(L\).
Exercise 15.7.9
- The reducible monic quadratic polynomials in \(F[x]\) must split completely; they take the form \((x - a)(x - b)\) with \(a, b \in F\). There are \(p(p+1)/2\) such quadratics, taking into account the fact that \((x - a)(x - b)\) is the same as \((x - b)(x - a)\). There are a total of \(p^2\) monic quadratic polynomials in \(F[x]\). So the irreducibles number \(p^2 - p(p+1)/2 = p(p-1)/2\).
- By Lemma 15.6.2, \(K = F[x]/(f)\) is a field and the residue of \(x\), call it \(\alpha\), is a root of \(f\) in \(K\). \(\alpha\) must have degree 2 over \(F\) since \(f\) is irreducible, therefore \(K/F\) is a quadratic extension so \(K\) has order \(p^2\). By Proposition 15.2.7, \(\{1, \alpha\}\) is a basis for \(K\) over \(F\). Moreover, each element of \(K\) has degree 1 or 2 by Corollary 15.3.6(a), and the elements of the form \(a + b\alpha\) with \(b \ne 0\) are not in \(F\), so they have degree 2, and each is the root of an irreducible quadratic polynomial with coefficients in \(F\).
- Let \(S\) denote the set of irreducible monic quadratic polynomials in \(F[x]\). We found in part (a) that \(|S| = p(p-1)/2\). Suppose \(g \in S\). The set \(S \setminus \{g\}\) consists of \(p(p-1)/2 - 1\) quadratics, which may therefore have a total of at most \(p(p-1) - 2\) roots in \(K\) among them. The set \(K \setminus F\) has cardinality \(p(p-1)\), so it contains at least two elements that are not the root of any polynomial in \(S\). However, in part (b), we found that each such element is the root of some element in \(S\). (we may always divide out the leading coefficient to get a monic polynomial). Therefore they are roots of \(g\). This holds for all \(g \in S\), so all quadratic polynomials that are irreducible over \(F[x]\) have a root in \(K\). The same is obviously true for those that are reducible.
- Let \(K = F[x]/(f)\) and \(L = F[x]/(g)\) where \(f, g\) are irreducible quadratics in \(F[x]\). Let \(\alpha\) be the residue of \(x\) in \(K\). As proven in part (c), \(L\) contains a root of \(f\), which of course does not belong to \(F\); call this root \(\beta\). By Proposition 15.2.8, \(F(\alpha)\) is isomorphic to \(F(\beta)\). But \(K = F(\alpha)\) and since \([L : F] = 2\) and \(\beta \notin F\), we also have \(L = F(\beta)\). Therefore \(K\) and \(L\) are isomorphic.
Exercise 15.7.10 Let us first verify that Theorem 15.7.3(b) applies in the case where \(F\) is any finite field, not necessarily one of prime order. This will be the crucial ingredient in the solution. Suppose \(|F| = q\), suppose \(s, k\) are positive integers such that \(k \divides s\), and suppose \(f \in F[x]\) is irreducible of degree \(k\). Let \(K = \mathbb{F}_{q^s}\). Let \(\beta\) be a root of \(f\) in an extension of \(F\). Then \([F(\beta): F] = k\), so \(|F(\beta)| = q^k\). If \(q = p^r\) where \(p = \char F\), then \(|F(\beta)| = p^{kr}\) and \(|K| = p^{rs}\), and since \(kr \divides rs\), Theorem 15.7.3(e) implies that \(K\) contains a subfield isomorphic to \(F(\beta)\). Therefore \(f\) has a root in \(K\), and Proposition 15.6.4(f) implies that \(f \divides x^{q^s} - x\).
Now the solution is straightforward. Again, suppose \(|F| = q\). Given some irreducible \(f \in F[x]\), we may produce an extension field \(K\) that contains a root of \(f\), so that \([K : F] = \deg f\). Successive extensions produce a field \(L\) over which \(f\) splits completely, and as each extension can be chosen to be generated by a root of \(f\), the index \([L : F]\) is finite. This implies that \(|L| = q^s\) for some positive integer \(s\) and the degree of \(f\) divides \(s\). By the stronger version of Theorem 15.7.3(b) proven above, \(f \divides x^{q^s} - x\). The latter has no multiple roots in \(L\), therefore \(f\) has no multiple roots. This implies that \(f\) and \(f'\) are relatively prime, so in particular \(f' \ne 0\).
Exercise 15.7.11 Using \(f' = 2ax + b\) to eliminate first the quadratic then the linear term of \(f\), we obtain \(-4af + (2ax + b)f' = b^2 - 4ac\).
Exercise 15.7.12
Let \(m, n\) be positive integers and let \(p\) be prime. Then
- \(p^m - 1 \divides p^n - 1\) in \(\Z\) iff \(m \divides n\)
- \(x^m - 1 \divides x^n - 1\) in \(\Z[x]\) iff \(m \divides n\)
Suppose \(m \divides n\). Then \[ x^n - 1 = (x^m - 1)(x^{n-m} + x^{n-2m} + \ldots + x^m + 1) \] so \(x^m - 1 \divides x^n - 1\) in \(\Z[x]\). Substitution of \(x = p\) shows that \(p^m - 1 \divides p^n - 1\) in \(\Z\). Conversely, suppose \(m \ndivides n\). Write \(n = am + b\) where \(1 \le b \le m - 1\). Then \[ p^n - 1 = p^n - p^b + p^b - 1 = p^b(p^{am} - 1) + p^b - 1 \] Now \(p^m - 1 \divides p^{am} - 1\) but \(p^m - 1 \ndivides p^b - 1\) since \(p^b - 1\) is a positive integer that is strictly less than \(p^m - 1\). Therefore \(p^m - 1 \ndivides p^n - 1\) in the integers. This implies that \(x^m - 1 \ndivides x^n - 1\) in \(\Z[x]\).
We can now answer the stated exercise easily. When \(k \divides r\), it follows that \(p^k - 1 \divides p^r - 1\), or in other words \(q' - 1 \divides q - 1\), so \(x^{q' - 1} - 1 \divides x^{q-1} - 1\), so \(x^{q'} - x \divides x^q - x\). Conversely, if \(k \ndivides r\), then \(p^k - 1 \ndivides p^r - 1\), that is, \(q' - 1 \ndivides q - 1\), so \(x^{q'-1} - 1 \ndivides x^{q-1} - 1\), and since \(\Z[x]\) is an integral domain, this implies \(x^{q'} - x \ndivides x^q - x\).
Remark: Using the content of this chapter, it's possible to give an alternative proof that \(x^{q'} - x \ndivides x^q - x\) in \(\mathbb{F}_p[x]\) when \(k \ndivides r\), which implies that \(x^{q'} - x \ndivides x^q - x\) in \(\Z[x]\). However, showing that \(x^{q'} - x \divides x^q - x\) in \(\mathbb{F}_p[x]\) when \(k \divides r\) does not carry over easily into \(\Z[x]\).
Exercise 15.7.13 The proof of Theorem 15.7.3(c) also works for this case. Explicitly, let \(G\) be a finite subgroup of \(F^\times\); write \(G = H_1 \oplus \ldots \oplus H_k\) where all \(H_i\)'s are cyclic, \(|H_i|\) divides \(|H_{i+1}|\), and all elements of \(G\) satisfy \(x^{|H_k|} = 1\). But this polynomial has at most \(|H_k|\) roots in \(F\), and since \(G \subseteq F\), it follows that \(|G| \le |H_k|\), so in fact \(|G| = |H_k|\) and \(G = H_k\).
Exercise 15.7.14 Let \(N_p(n)\) denote the number of irreducible polynomials of degree \(n\) over \(\mathbb{F}_p\). The polynomial \(x^{p^n} - x\) factors over \(\mathbb{F}_p\) into the product of all irreducible polynomials of degrees dividing \(n\). By equating degrees, we find \[ p^n = \sum_{d \divides n} dN_p(d) \] The function \(N_p\) can be recovered by the Möbius inversion: \[ nN_p(n) = \sum_{d \divides n} \mu(d) p^{n/d} \] Artin asks for a formula in terms of Euler's \(\phi\) function; perhaps this is a typo.