Brian Bi

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 24 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

1. 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$$.
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$$.
3. 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.
4. 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

1. $$p^m - 1 \divides p^n - 1$$ in $$\Z$$ iff $$m \divides n$$
2. $$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.