Finite fields
The integers mod a prime p form a field with p elements. Is there a field with 4 elements, or 6, and when there is one, how many different ones are there?
Where you are 5 in Fields
Why this exists
For a prime p, \mathbb{Z}_p is a field (Relations, equivalence classes and partitions), and Kronecker’s construction (Field extensions and degree, Theorem 3) turns an irreducible polynomial of degree n over it into a field with p^n elements. Which sizes occur? Does every degree have an irreducible polynomial? Do two of the same degree give different fields? The answers are: the prime powers, yes, and no.
Definition
In plain words: a finite field is a field with finitely many elements, and its Frobenius map raises every element to the power p, the characteristic.
- A finite field is a field F with |F| finite. Its prime subfield is \{k \cdot 1 : k \in \mathbb{Z}\}.
- For a commutative ring R with \operatorname{char} R = p prime, the Frobenius map is \operatorname{Fr} : R \to R, \operatorname{Fr}(a) = a^p. Its powers are \operatorname{Fr}^k = \operatorname{Fr} \circ \cdots \circ \operatorname{Fr} (k times), with \operatorname{Fr}^0 = \mathrm{id}_R.
- A generator of a finite field F is a generator of the group F^\times: every nonzero element is a power of it.
Theorem 3 shows that any two fields with q elements are isomorphic, so from here on \mathbb{F}_q means a field with q elements, and \mathbb{F}_p = \mathbb{Z}_p for a prime p. We write k for [k] throughout.
Intuition
Under addition, \mathbb{F}_{p^n} is an n-dimensional vector space over \mathbb{F}_p, hence its size p^n. Under multiplication, its nonzero elements are the powers of one generator, so multiplying is adding exponents mod p^n - 1. Frobenius, like complex conjugation, fixes the base field and moves each element among its conjugates. Every element satisfies a^{p^n} = a, so \mathbb{F}_{p^n} is exactly the set of roots of x^{p^n} - x, and its subfields sit inside it as the divisors of n sit inside n.
Results
Throughout, p is a prime and n \ge 1.
Theorem 1 (the size). Let F be a finite field. Then \operatorname{char} F is a prime p, the prime subfield P is isomorphic to \mathbb{F}_p and lies in every subfield of F, and |F| = p^n with n = [F : P].
Lemma 2 (Frobenius). Let R be a commutative ring with \operatorname{char} R = p. Then (a + b)^p = a^p + b^p for all a, b \in R, so \operatorname{Fr} is a ring homomorphism, and \operatorname{Fr}^k(a) = a^{p^k}. If R is a field, \operatorname{Fr} is injective; if R is a finite field, \operatorname{Fr} is an automorphism fixing every element of the prime subfield.
Theorem 3 (existence and uniqueness). Let q = p^n. (a) In a field F with q elements, a^q = a for every a \in F, and x^q - x = \prod_{a \in F}(x - a) in F[x]. (b) A splitting field of x^q - x over \mathbb{F}_p has exactly q elements, which are the roots of x^q - x, all distinct. (c) Any two fields with q elements are isomorphic.
Theorem 4 (the multiplicative group is cyclic). Let K be a field and G a finite subgroup of K^\times. Then G is cyclic. In particular \mathbb{F}_q^\times is cyclic of order q - 1.
Corollary 5. If \beta generates \mathbb{F}_{p^n}, then \mathbb{F}_{p^n} = \mathbb{F}_p(\beta) and m_\beta is irreducible of degree n. So \mathbb{F}_p[x] has an irreducible polynomial of every degree n \ge 1.
Theorem 6 (subfields). Let F = \mathbb{F}_{p^n}. (a) Every subfield of F has p^d elements for some positive divisor d of n. (b) For each positive divisor d of n, F has exactly one subfield with p^d elements, namely \{a \in F : a^{p^d} = a\}. (c) For positive divisors d, e of n, the subfield with p^d elements lies in the one with p^e elements if and only if d \mid e.
Theorem 7 (automorphisms and conjugates). (a) The automorphisms of \mathbb{F}_{p^n} are \mathrm{id}, \operatorname{Fr}, \dots, \operatorname{Fr}^{n-1}, and these n maps are distinct. (b) If a \in \mathbb{F}_{p^n} and d = [\mathbb{F}_p(a) : \mathbb{F}_p], then a, a^p, \dots, a^{p^{d-1}} are distinct, and m_a = (x - a)(x - a^p)\cdots(x - a^{p^{d-1}}). These are the conjugates of a.
Theorem 8 (factoring x^{p^n} - x). In \mathbb{F}_p[x], x^{p^n} - x is the product of all monic irreducible polynomials whose degree divides n, each once. So if N_p(d) is the number of monic irreducible polynomials of degree d in \mathbb{F}_p[x], then
Why it is true
“FE”, “AE” and “SF” refer to Field extensions and degree, Algebraic elements and minimal polynomials and Splitting fields.
Proof of Theorem 1. As F is finite, k \mapsto k \cdot 1 is not injective on \mathbb{Z}, so \operatorname{char} F > 0; a field is an integral domain, so the characteristic is a prime p (Rings and integral domains, Theorems 5 and 9). By Ring homomorphisms, Corollary 7, P \cong \mathbb{Z}_p and P lies in every subring. F is a vector space over P spanned by the finite set F, so n = [F : P] is finite and |F| = p^n (FE Theorem 1(c)). \square
Proof of Lemma 2. By the binomial theorem in the commutative ring R, (a + b)^p = \sum_{j=0}^{p} \binom{p}{j} a^j b^{p-j}. For 0 < j < p, the prime p divides p! = \binom{p}{j}\, j!\,(p - j)! but not j!\,(p - j)!, so p \mid \binom{p}{j} (The binomial theorem, Every number has exactly one prime factorization), and that term is 0 as pr = 0 in R. With (ab)^p = a^pb^p and 1^p = 1, \operatorname{Fr} is a ring homomorphism, and \operatorname{Fr}^k(a) = a^{p^k} by induction on k. In a field the kernel is an ideal without 1, hence \{0\} (Ideals and quotient rings, Corollary 3); an injective map of a finite set to itself is onto; and \operatorname{Fr}(k \cdot 1) = k \cdot 1. \square
Proof of Theorem 3. (a) F^\times is a group of order q - 1, so a^{q-1} = 1 for a \ne 0 (Lagrange's theorem, Corollary 2), and a^q = a for every a, 0 included. So the q elements of F are distinct roots of x^q - x, and \prod_{a \in F}(x - a) divides it (Polynomial rings and the division algorithm, Theorem 6). Both are monic of degree q, so they are equal.
(b) Let E be a splitting field of g = x^q - x over \mathbb{F}_p and K \subseteq E the set of roots of g. As \operatorname{Fr}^n(a) = a^q is a ring homomorphism (Lemma 2), K = \{a : \operatorname{Fr}^n(a) = a\} contains 0 and 1 and is closed under sums, products and negatives, and (a^{-1})^q = (a^q)^{-1} = a^{-1} for a \ne 0. So K is a subfield of E containing \mathbb{F}_p and every root, and K = E, as the roots generate E. For a root a,
and h(a) = q\,a^{q-1} - 1 = -1, as q \cdot 1 = 0. So (x - a)^2 \nmid g, the q roots in g = \prod (x - a_i) are distinct, and |E| = |K| = q.
(c) Let |F| = q, with prime subfield P and \theta : \mathbb{F}_p \to P, k \mapsto k \cdot 1 (Theorem 1). By (a), x^q - x splits over F and its roots are all of F, so F is a splitting field of x^q - x over P. As (x^q - x)^\theta = x^q - x, SF Theorem 4 extends \theta to an isomorphism from the field E of (b) onto F. So every field with q elements is isomorphic to E. \square
Proof of Theorem 4. Let |G| = m and, for d \mid m, let c(d) be the number of elements of G of order d. Every order divides m (Lagrange), so \sum_{d \mid m} c(d) = m. If c(d) > 0, take a of order d. The d elements of \langle a \rangle are roots of x^d - 1, which has at most d roots in K (Polynomial rings and the division algorithm, Theorem 6), so every element of order d lies in \langle a \rangle, which has exactly \varphi(d) of them (Cyclic groups, Corollary 9). So c(d) \le \varphi(d) for every d \mid m, while \sum_{d \mid m} \varphi(d) = m (Cyclic groups, Exercise 16). Hence c(d) = \varphi(d) for all d, and c(m) = \varphi(m) \ge 1: an element of order m generates G. \square
Proof of Corollary 5. Every nonzero element is a power of \beta, so \mathbb{F}_p(\beta) = \mathbb{F}_{p^n}, of degree n (Theorem 1), and m_\beta is irreducible of degree n (AE Theorem 1). By Theorems 3 and 4, \mathbb{F}_{p^n} and \beta exist for every n. \square
Proof of Theorem 6. (a) A subfield K contains the prime subfield (Theorem 1), so |K| = p^d and, with e = [F : K], p^n = (p^d)^e (FE Theorem 1(c)): d \mid n. (b) If |K| = p^d, every a \in K has a^{p^d} = a (Theorem 3(a)), so K lies in the set R_d of roots of x^{p^d} - x in F, which has at most p^d elements; so K = R_d. Conversely R_d is a subfield, by the argument of Theorem 3(b) with \operatorname{Fr}^d. To count it, write n = de and s = p^d - 1. As y - 1 \mid y^e - 1, s divides p^n - 1, and x^s - 1 divides x^{p^n - 1} - 1; multiplying by x, x^{p^d} - x divides x^{p^n} - x = \prod_{a \in F}(x - a). By unique factorization in F[x] (Unique factorization domains) it is a product of p^d of these distinct factors, so |R_d| = p^d. (c) If R_d \subseteq R_e, apply (a) to R_e = \mathbb{F}_{p^e}: d \mid e. If d \mid e and a^{p^d} = a, applying \operatorname{Fr}^d another e/d - 1 times gives a^{p^e} = a. \square
Proof of Theorem 7. (a) An automorphism sends 1 to 1, so it fixes \mathbb{F}_p. \mathbb{F}_{p^n} is a splitting field of x^{p^n} - x over \mathbb{F}_p (Theorem 3(a)), so SF Corollary 5 allows at most n automorphisms, and each \operatorname{Fr}^k is one (Lemma 2). \operatorname{Fr}^n = \mathrm{id} by Theorem 3(a); if \operatorname{Fr}^k = \mathrm{id} with 1 \le k < n, all p^n elements would be roots of x^{p^k} - x, which has at most p^k. So \operatorname{Fr} has order n, its powers \mathrm{id}, \dots, \operatorname{Fr}^{n-1} are distinct (Cyclic groups, Theorem 4), and they are all the automorphisms.
(b) L = \mathbb{F}_p(a) has p^d elements. \operatorname{Fr} fixes the coefficients of m_a, so m_a(a^{p^i}) = \operatorname{Fr}^i(m_a(a)) = 0. If a^{p^i} = a^{p^j} with 0 \le i < j < d, apply \operatorname{Fr}^{d-i}: as \operatorname{Fr}^d is the identity on L (Theorem 3(a)), this gives a = a^{p^k} with k = j - i, 1 \le k < d. The elements of L with b^{p^k} = b form a subfield containing \mathbb{F}_p and a, hence all of L, and p^d > p^k elements cannot all be roots of x^{p^k} - x. So m_a, of degree d, has the d distinct roots a^{p^i} and equals their product. \square
Proof of Theorem 8. Let F = \mathbb{F}_{p^n} and g = x^{p^n} - x = \prod_{a \in F}(x - a). If a monic irreducible f \in \mathbb{F}_p[x] of degree d divides g, it has a root a \in F, so f = m_a (AE Theorem 1(d)) and d = [\mathbb{F}_p(a) : \mathbb{F}_p] divides n by the tower law (FE Theorem 6). If d \mid n, then K = \mathbb{F}_p[x]/\langle f \rangle has p^d elements (FE Theorem 3), its root \alpha has \alpha^{p^d} = \alpha, hence \alpha^{p^n} = \alpha as in Theorem 6(c), and f = m_\alpha divides g (AE Theorem 1(c)). No f divides g twice, or a root a of f would give (x - a)^2 \mid g. Unique factorization of the monic g in \mathbb{F}_p[x] gives the product, and comparing degrees gives the sum. \square
Worked examples
Arithmetic in a field with 25 elements
Let F = \mathbb{Z}_5[x]/\langle x^2 - 3 \rangle and \alpha = x + \langle x^2 - 3 \rangle. Show that F is a field with 25 elements, find \operatorname{ord}(\alpha), show that \beta = 1 + \alpha generates F, and find \beta^{-1}.
SolutionThe squares in \mathbb{Z}_5 are 0, 1, 4, so x^2 - 3 has no root and, being quadratic, is irreducible. FE Theorem 3 makes F a field with basis (1, \alpha), so |F| = 5^2 = 25. Now \alpha^2 = 3, \alpha^4 = 9 = -1 and \alpha^8 = 1, so \operatorname{ord}(\alpha) = 8, and \alpha does not generate the cyclic group F^\times of order 24.
The order of \beta divides 24, and a proper divisor of 24 divides 12 or 8, so it suffices that \beta^{12} \ne 1 and \beta^8 \ne 1. Squaring with \alpha^2 = 3:
and \beta^{12} = \beta^8\beta^4 = (2 + \alpha)(3 + \alpha) = 6 + 5\alpha + 3 = -1. So \operatorname{ord}(\beta) = 24, and the generators of F are the \varphi(24) = 8 powers \beta^k with \gcd(k, 24) = 1. For the inverse, (1 + \alpha)(1 - \alpha) = 1 - 3 = 3 and 3^{-1} = 2, so \beta^{-1} = 2(1 - \alpha) = 2 + 3\alpha. Check: (1 + \alpha)(2 + 3\alpha) = 2 + 5\alpha + 9 = 1.
Frobenius and conjugates in the same field
In F of Example 1, find \operatorname{Fr}(a + b\alpha), the automorphisms of F, and the minimal polynomials over \mathbb{F}_5 of 1 + \alpha and 2 + \alpha.
Solution\alpha^5 = \alpha \cdot \alpha^4 = -\alpha, and a^5 = a for a \in \mathbb{F}_5 (Fermat's little theorem). As \operatorname{Fr} is a ring homomorphism, \operatorname{Fr}(a + b\alpha) = a - b\alpha. It fixes exactly the elements with b = 0, and by Theorem 7(a) the automorphisms of F are \mathrm{id} and \operatorname{Fr}.
By Theorem 7(b), the conjugates of 1 + \alpha are 1 \pm \alpha, so
The conjugates of 2 + \alpha are 2 \pm \alpha, with sum 4 and product 4 - 3 = 1, so m_{2 + \alpha} = x^2 - 4x + 1 = x^2 + x + 1. As x^3 - 1 = (x - 1)(x^2 + x + 1), 2 + \alpha has order 3. The 20 elements of F \setminus \mathbb{F}_5 fall into conjugate pairs, one pair for each of the N_5(2) = 10 monic irreducible quadratics (Theorem 8: 25 = 5 + 2 \cdot 10).
Two models of the field with 16 elements
Show that f = x^4 + x^3 + 1 and g = x^4 + x^3 + x^2 + x + 1 are irreducible over \mathbb{F}_2, and write down an isomorphism \mathbb{F}_2[x]/\langle g \rangle \to \mathbb{F}_2[x]/\langle f \rangle.
SolutionNeither has a root, as both take the value 1 at 0 and at 1. A quartic with no root that factors is a product of two irreducible quadratics, and x^2 + x + 1 is the only one, with (x^2 + x + 1)^2 = x^4 + x^2 + 1, neither f nor g. So both are irreducible, and both quotients have 16 elements.
Let \delta = x + \langle f \rangle, so \delta^4 = \delta^3 + 1. Then \delta^5 = \delta^4 + \delta = \delta^3 + \delta + 1 \ne 1 and \delta^3 \ne 1, so \operatorname{ord}(\delta) = 15 and \delta^3 has order 5. Since x^5 - 1 = (x - 1)g and \delta^3 \ne 1, g(\delta^3) = 0. By SF Lemma 3, with \rho = x + \langle g \rangle, there is an isomorphism \mathbb{F}_2(\rho) \to \mathbb{F}_2(\delta^3) fixing \mathbb{F}_2 with \rho \mapsto \delta^3, and \mathbb{F}_2(\delta^3) has degree 4, so it is the whole field. Reducing \delta^6 = \delta^3 + \delta^2 + \delta + 1 and \delta^9 = \delta^2 + 1,
Here \rho^5 = 1, so \rho is not a generator, yet \mathbb{F}_2[x]/\langle g \rangle is still \mathbb{F}_{16}.
Counting irreducible polynomials
Find N_2(6) and N_3(4).
SolutionTheorem 8 with p = 2, n = 1, 2, 3 gives 2 = N_2(1), 4 = 2 + 2N_2(2) and 8 = 2 + 3N_2(3), so N_2(2) = 1 and N_2(3) = 2. Then
so N_2(6) = 54/6 = 9. For p = 3: N_3(1) = 3, 9 = 3 + 2N_3(2) gives N_3(2) = 3, and 81 = 3 + 2 \cdot 3 + 4N_3(4) gives N_3(4) = 72/4 = 18.
The subfields of \mathbb{F}_{2^{12}}
List the subfields of F = \mathbb{F}_{2^{12}}, find the intersection of the subfields with 2^4 and 2^6 elements and the smallest subfield containing both, and say which subfields contain a root of x^3 + x^2 + 1.
SolutionBy Theorem 6 there is one subfield \mathbb{F}_{2^d} for each d \in \{1, 2, 3, 4, 6, 12\}, ordered as the divisors are (figure). A subfield of both \mathbb{F}_{2^4} and \mathbb{F}_{2^6} has 2^d elements with d \mid 4 and d \mid 6, so d \mid 2, and \mathbb{F}_{2^2} lies in both: the intersection is \mathbb{F}_4. A subfield containing both has 2^e elements with 4 \mid e, 6 \mid e and e \mid 12, so it is F itself. The cubic x^3 + x^2 + 1 has no root in \mathbb{F}_2, so it is irreducible, and a root a has [\mathbb{F}_2(a) : \mathbb{F}_2] = 3; so a \in \mathbb{F}_{2^d} exactly when \mathbb{F}_8 \subseteq \mathbb{F}_{2^d}, that is for d = 3, 6, 12.
When -1 is a square
Let q be odd. Prove that -1 is a square in \mathbb{F}_q if and only if q \equiv 1 \pmod{4}.
SolutionProof. By Theorem 4, \mathbb{F}_q^\times = \langle \beta \rangle with \operatorname{ord}(\beta) = q - 1, an even number. As p is odd, -1 \ne 1, and the only roots of x^2 - 1 are \pm 1; since \beta^{(q-1)/2} is a root other than 1, it equals -1. The squares of nonzero elements are the \beta^{2k}, that is the \beta^j with j even, a condition that does not depend on the choice of j modulo the even number q - 1. So -1 = \beta^{(q-1)/2} is a square exactly when (q - 1)/2 is even, that is when 4 \mid q - 1. \square For example, 2^2 = -1 in \mathbb{F}_5.
Boundaries
- Unique, but not canonically. Two fields with p^n elements are isomorphic in n ways (Theorem 7(a) composed with one isomorphism), so no element of one has a preferred partner in the other.
- \mathbb{F}_{p^n} is not \mathbb{Z}_{p^n}. For n \ge 2, \mathbb{Z}_{p^n} has the zero divisor p, and the additive group of \mathbb{F}_{p^n} is not cyclic, as every nonzero element has order p.
- Theorem 4 needs commutativity. In the quaternions, where every nonzero element is a unit but multiplication does not commute, Q_8 = \{\pm 1, \pm i, \pm j, \pm k\} is a finite multiplicative subgroup that is not cyclic: there x^2 + 1 has more than two roots.
- Infinite fields of characteristic p. \operatorname{Fr} is injective on every field of characteristic p but need not be onto (Exercise 16).
Where this goes next
Field automorphisms and the Galois group calls the group of Theorem 7(a) the Galois group of \mathbb{F}_{p^n} over \mathbb{F}_p, cyclic of order n and generated by \operatorname{Fr}. Its subgroups, one for each divisor of n, match the subfields of Theorem 6: the first full case of the The fundamental theorem of Galois theory. Theorem 4 with K = \mathbb{F}_p gives Primitive roots modulo a prime.
Exercises
Computing in a finite field
Let K = \mathbb{Z}_7[x]/\langle x^2 + 1 \rangle and \gamma = x + \langle x^2 + 1 \rangle.
- Show that K is a field with 49 elements, and find \operatorname{ord}(\gamma) and \operatorname{ord}(1 + \gamma).
- Show that 2 + \gamma generates K.
- Find (2 + \gamma)^{-1} in the form a + b\gamma.
- At a symposium, Yuna builds a field with 49 elements as K, and Hiro builds his as \mathbb{Z}_7[x]/\langle x^2 - 3 \rangle, with \rho = x + \langle x^2 - 3 \rangle. Write down an isomorphism from Hiro’s field to Yuna’s that fixes \mathbb{Z}_7.
- Find \operatorname{Fr}(a + b\gamma) in K, and the minimal polynomials of 1 + \gamma and 2 + \gamma over \mathbb{F}_7.
- In \mathbb{F}_2(\delta) of Example 3, find the conjugates and the minimal polynomials over \mathbb{F}_2 of \delta^7 and of \delta^5.
Counting
- Find N_2(5), N_7(2) and N_3(6).
- Find N_2(8).
- How many elements of \mathbb{F}_{125} lie in no proper subfield? Deduce N_5(3).
Subfields and splitting
- List the subfields of \mathbb{F}_{3^{20}}. Which contain \mathbb{F}_9? What is the intersection of the subfields with 3^4 and 3^{10} elements?
- How many elements has a splitting field over \mathbb{F}_2 of (x^2 + x + 1)(x^3 + x^2 + 1)(x^4 + x^3 + 1)?
Proofs
- Prove that every element of a finite field of characteristic p is a pth power of exactly one element.
- Prove that the elements of \mathbb{F}_q sum to 0 when q \ge 3, and that the product of its nonzero elements is -1.
- Let f \in \mathbb{F}_p[x] be irreducible of degree d. Prove that f has a root in \mathbb{F}_{p^n} if and only if d \mid n, and that it then splits over \mathbb{F}_{p^n}.
- Prove that x^4 + 1 is reducible over \mathbb{F}_p for every prime p.
- Refute with a counterexample: for every field F of characteristic p, the Frobenius map of F is onto.
Answers
- By Example 6, -1 is not a square in \mathbb{F}_7, as 7 \equiv 3 \pmod{4}, so x^2 + 1 is irreducible and |K| = 7^2 = 49. \gamma^2 = -1, so \operatorname{ord}(\gamma) = 4. (1 + \gamma)^2 = 2\gamma, (1 + \gamma)^4 = -4 = 3 and (1 + \gamma)^8 = 2, so (1 + \gamma)^{24} = 2^3 = 1, while (1 + \gamma)^8 \ne 1 and (1 + \gamma)^{12} = 2 \cdot 3 = -1. A proper divisor of 24 divides 8 or 12, so \operatorname{ord}(1 + \gamma) = 24.
- The order divides 48, and a proper divisor of 48 divides 24 or 16. (2 + \gamma)^2 = 3 + 4\gamma, (2 + \gamma)^4 = 3\gamma, (2 + \gamma)^8 = 5, (2 + \gamma)^{16} = 4 \ne 1, and (2 + \gamma)^{24} = 4 \cdot 5 = -1 \ne 1. So the order is 48.
- (2 + \gamma)(2 - \gamma) = 5 and 5^{-1} = 3, so (2 + \gamma)^{-1} = 3(2 - \gamma) = 6 + 4\gamma. Check: (2 + \gamma)(6 + 4\gamma) = 12 + 14\gamma - 4 = 1.
- (2\gamma)^2 = -4 = 3, so 2\gamma is a root of x^2 - 3 in K. SF Lemma 3 gives the isomorphism a + b\rho \mapsto a + 2b\gamma onto \mathbb{F}_7(2\gamma) = K.
- \gamma^7 = \gamma(\gamma^2)^3 = -\gamma, so \operatorname{Fr}(a + b\gamma) = a - b\gamma. Conjugates 1 \pm \gamma give m_{1 + \gamma} = x^2 - 2x + 2 = x^2 + 5x + 2; conjugates 2 \pm \gamma give m_{2 + \gamma} = x^2 - 4x + 5 = x^2 + 3x + 5.
- \operatorname{ord}(\delta) = 15. Doubling exponents mod 15, the conjugates of \delta^7 are \delta^7, \delta^{14}, \delta^{13}, \delta^{11}, the inverses of the conjugates \delta^8, \delta, \delta^2, \delta^4 of \delta; so m_{\delta^7} = x^4 f(1/x) = x^4 + x + 1. The conjugates of \delta^5 are \delta^5, \delta^{10}, with sum (\delta^3 + \delta + 1) + (\delta^3 + \delta) = 1 and product \delta^{15} = 1: m_{\delta^5} = x^2 + x + 1.
- 32 = 2 + 5N_2(5) gives N_2(5) = 6. 49 = 7 + 2N_7(2) gives N_7(2) = 21. With N_3(1) = 3, N_3(2) = 3, N_3(3) = (27 - 3)/3 = 8: 729 = 3 + 6 + 24 + 6N_3(6), so N_3(6) = 116.
- N_2(1) = 2, N_2(2) = 1, N_2(4) = (16 - 4)/4 = 3, and 256 = 2 + 2 + 12 + 8N_2(8), so N_2(8) = 30.
- The only proper subfield is \mathbb{F}_5, so 120 elements. Each has degree 3, and by Theorem 7(b) they fall into sets of 3 conjugates, one set per monic irreducible cubic: N_5(3) = 40.
- One \mathbb{F}_{3^d} for each d \in \{1, 2, 4, 5, 10, 20\}. Those containing \mathbb{F}_9 have 2 \mid d: d = 2, 4, 10, 20. The intersection has d \mid \gcd(4, 10) = 2 and contains \mathbb{F}_9: it is \mathbb{F}_9.
- The factors are irreducible (Examples 3 and 5; x^2 + x + 1 has no root). A splitting field E is some \mathbb{F}_{2^m}; each factor has a root in E, so 2, 3 and 4 divide m (Exercise 14) and \mathbb{F}_{2^{12}} \subseteq E. All three split over \mathbb{F}_{2^{12}} (Exercise 14) and the roots generate E, so E = \mathbb{F}_{2^{12}}, with 2^{12} = 4096 elements.
- Proof. By Lemma 2, \operatorname{Fr} is a bijection of the field: each b is a^p for exactly one a. \square
- Proof. x^q - x = \prod_{a \in \mathbb{F}_q}(x - a) (Theorem 3(a)). The coefficient of x^{q-1} on the right is -\sum a, and on the left it is 0 as q - 1 \ge 2. Cancelling x in the domain \mathbb{F}_q[x], x^{q-1} - 1 = \prod_{a \ne 0}(x - a); constant terms give -1 = (-1)^{q-1}\prod_{a \ne 0} a. If q is odd, (-1)^{q-1} = 1; if q is even, -1 = 1. Either way the product is -1. \square
- Proof. If a \in \mathbb{F}_{p^n} is a root, f is a constant times m_a, so d = [\mathbb{F}_p(a) : \mathbb{F}_p] divides n by the tower law. If d \mid n, the monic multiple of f divides \prod_{a \in \mathbb{F}_{p^n}}(x - a) (Theorem 8), so by unique factorization in \mathbb{F}_{p^n}[x] it is a product of d of these linear factors. \square
- Proof. Over \mathbb{F}_2, x^4 + 1 = (x + 1)^4 (Lemma 2). For odd p, p^2 - 1 = (p - 1)(p + 1) is a product of consecutive even numbers, one divisible by 4, so 8 \mid p^2 - 1, and the cyclic group \mathbb{F}_{p^2}^\times has an element \zeta of order 8 (Cyclic groups, Theorem 10). Then (\zeta^4)^2 = 1 and \zeta^4 \ne 1, so \zeta^4 = -1, and \zeta is a root of x^4 + 1. Its minimal polynomial over \mathbb{F}_p has degree [\mathbb{F}_p(\zeta) : \mathbb{F}_p] \le 2 and divides x^4 + 1, a proper factor. \square
- Take F = \mathbb{F}_p(t), the field of fractions of \mathbb{F}_p[t] (Unique factorization domains). If t = (g/h)^p with g, h \in \mathbb{F}_p[t] and h \ne 0, then t\,h^p = g^p, and the degrees give 1 + p\deg h = p\deg g, impossible modulo p. So t is not in the image of \operatorname{Fr}.