Chapter 8 · Fields and Galois Theory

8.2 Finite Fields

Every finite field has $p^n$ elements, for each prime power there is exactly one, its multiplicative group is cyclic, its subfields correspond to the divisors of $n$, and the Frobenius map $a\mapsto a^p$ organises everything — with hands-on arithmetic in $\mathbb{F}_4$, $\mathbb{F}_8$, $\mathbb{F}_9$ and $\mathbb{F}_{16}$.

The integers modulo a prime, $\mathbb{F}_p=\mathbb{Z}_p$, are the first finite fields one meets. Are there others? $\mathbb{Z}_4$ is not a field ($2\cdot2=0$), and a field with $6$ elements turns out not to exist at all. Yet §7.3 produced fields such as $\mathbb{F}_2[x]/\langle x^2+x+1\rangle$ with $4$ elements and $\mathbb{F}_3[x]/\langle x^2+1\rangle$ with $9$. In 1830 the eighteen-year-old Évariste Galois computed with "imaginary" roots of irreducible congruences modulo $p$ and in effect discovered all finite fields; in 1893 E. H. Moore proved that the list is complete. The answer is strikingly clean: a finite field has $p^n$ elements for a prime $p$, for each prime power $q=p^n$ there is exactly one field $\mathbb{F}_q$ up to isomorphism, its nonzero elements form a cyclic group, and its subfields are the $\mathbb{F}_{p^d}$ with $d\mid n$. All of this follows from the field theory of §8.1 together with one map, the Frobenius map $a\mapsto a^p$.

Finite fields are everywhere in modern technology. The block cipher AES, which encrypts most of the world's internet traffic, computes inverses in $\mathbb{F}_{256}=\mathbb{F}_2[x]/\langle x^8+x^4+x^3+x+1\rangle$; QR codes, CDs and deep-space probes correct errors with Reed–Solomon codes over $\mathbb{F}_{256}$; elliptic-curve cryptography runs over $\mathbb{F}_p$ and $\mathbb{F}_{2^m}$. In CSIR NET, finite fields are a steady source of Part B questions with a numerical answer (how many subfields, generators, primitive polynomials, elements of a given order, irreducible factors of $x^{p^n}-x$) and of Part C questions mixing true and false statements about subfields, the multiplicative group and the Frobenius map. All of them reduce to the theorems of this section.

Characteristic, Prime Subfield and the Size of a Finite Field

Recall from §7.1 that the characteristic of a field is $0$ or a prime, and from §8.1 (Theorem 8.1) that every field contains a smallest subfield, its prime subfield, isomorphic to $\mathbb{Q}$ or to $\mathbb{F}_p$. A finite field cannot contain $\mathbb{Q}$, so its characteristic is a prime $p$ and its prime subfield is $\mathbb{F}_p=\{0,1,2\cdot1,\dots,(p-1)\cdot1\}$.

📐 Theorem 8.18 — A finite field has $p^n$ elements
Let $F$ be a finite field. Then $\operatorname{char}F=p$ is prime, $F$ is a vector space over its prime subfield $\mathbb{F}_p$ of finite dimension $n=[F:\mathbb{F}_p]$, and $$|F|=p^n.$$ The additive group $(F,+)$ is isomorphic to $\mathbb{Z}_p^{\,n}=\mathbb{Z}_p\times\cdots\times\mathbb{Z}_p$; in particular it is cyclic only when $n=1$. More generally, if $E\subseteq F$ is a subfield with $|E|=q$, then $|F|=q^{[F:E]}$.

Proof. $F$ is finite, so it is a finite-dimensional vector space over $\mathbb{F}_p$; choosing a basis $e_1,\dots,e_n$, the map $(c_1,\dots,c_n)\mapsto\sum c_ie_i$ is a bijection $\mathbb{F}_p^{\,n}\to F$, so $|F|=p^n$, and it is an isomorphism of additive groups. Every nonzero element of $\mathbb{Z}_p^{\,n}$ has additive order $p$, so for $n\ge2$ no element generates a group of order $p^n$. The same argument over $E$ gives $|F|=q^{[F:E]}$. ∎

So there is no field with $6$, $10$, $12$, $15$, $18$, $20$, $100$ … elements: the possible orders are $2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,\dots$ — exactly the prime powers. The engine of the whole theory is the following map.

📘 Definition 8.7 — The Frobenius map
For a field $F$ of characteristic $p$, the Frobenius map is $\sigma=\sigma_p:F\to F$, $\sigma(a)=a^p$. Its iterates are $\sigma^k(a)=a^{p^k}$. For a power $q=p^m$ we also write $\sigma_q(a)=a^q$.
📐 Theorem 8.19 — The freshman's dream and the Frobenius automorphism
Let $F$ have characteristic $p$. Then for all $a,b\in F$ and $k\ge1$: $$(a+b)^p=a^p+b^p,\qquad (a+b)^{p^k}=a^{p^k}+b^{p^k},\qquad (ab)^p=a^pb^p.$$ So $\sigma$ is an injective ring homomorphism $F\to F$; it fixes every element of $\mathbb{F}_p$; and if $F$ is finite, $\sigma$ is an automorphism of $F$. The elements of $F$ fixed by $\sigma$ are exactly the elements of the prime subfield $\mathbb{F}_p$.

Proof. By the binomial theorem $(a+b)^p=\sum_{j=0}^{p}\binom pja^jb^{p-j}$, and for $0\lt j\lt p$ the prime $p$ divides $\binom pj=\tfrac{p!}{j!(p-j)!}$ (it divides the numerator but not the denominator), so these terms vanish in characteristic $p$. Iterating gives the $p^k$ version; multiplicativity is commutativity. Hence $\sigma$ is a ring homomorphism with $\sigma(1)=1$, injective by Theorem 8.1; if $F$ is finite, an injective map $F\to F$ is bijective. By Fermat's little theorem (§5.2) $c^p=c$ for all $c\in\mathbb{F}_p$. Conversely the fixed points of $\sigma$ are roots of $x^p-x$, which has at most $p$ roots in the field $F$; the $p$ elements of $\mathbb{F}_p$ are already roots, so there are no others. ∎

✏️ Example 1 — The field with four elements
(a) Write the addition and multiplication tables of $\mathbb{F}_4=\mathbb{F}_2[x]/\langle x^2+x+1\rangle=\{0,1,\omega,\omega+1\}$, $\omega=\bar x$. (b) Show that neither $\mathbb{Z}_4$ nor the ring $\mathbb{Z}_2\times\mathbb{Z}_2$ is a field, although both have four elements. (c) Describe the Frobenius map of $\mathbb{F}_4$.
(a) $x^2+x+1$ has no root in $\mathbb{F}_2$, so it is irreducible and the quotient is a field (§7.3). The only rule needed is $\omega^2=\omega+1$ (signs do not matter in characteristic $2$). Addition is coordinatewise mod $2$: $a+a=0$ for all $a$, $1+\omega=\omega+1$, $\omega+(\omega+1)=1$. Multiplication: $\omega\cdot\omega=\omega+1$, $\omega(\omega+1)=\omega^2+\omega=1$, $(\omega+1)^2=\omega^2+1=\omega$.
Tables
$+$$0$$1$$\omega$$\omega+1$
$0$$0$$1$$\omega$$\omega+1$
$1$$1$$0$$\omega+1$$\omega$
$\omega$$\omega$$\omega+1$$0$$1$
$\omega+1$$\omega+1$$\omega$$1$$0$
$\times$$1$$\omega$$\omega+1$
$1$$1$$\omega$$\omega+1$
$\omega$$\omega$$\omega+1$$1$
$\omega+1$$\omega+1$$1$$\omega$
The additive group is $\mathbb{Z}_2\times\mathbb{Z}_2$; the multiplicative group $\{1,\omega,\omega^2=\omega+1\}$ is cyclic of order $3$.
(b) In $\mathbb{Z}_4$, $2\cdot2=0$; in $\mathbb{Z}_2\times\mathbb{Z}_2$, $(1,0)(0,1)=(0,0)$. Both have zero divisors. Note that $(\mathbb{F}_4,+)\cong\mathbb{Z}_2\times\mathbb{Z}_2$ as groups, but the multiplication of $\mathbb{F}_4$ is not the componentwise one.
(c) $\sigma(a)=a^2$: $0\mapsto0$, $1\mapsto1$, $\omega\mapsto\omega+1$, $\omega+1\mapsto\omega$. It swaps the two roots of $x^2+x+1$, fixes exactly $\mathbb{F}_2$, and $\sigma^2=\mathrm{id}$.

The Multiplicative Group Is Cyclic

📐 Theorem 8.20 — Finite subgroups of $F^\times$ are cyclic
Let $F$ be any field and $G$ a finite subgroup of the multiplicative group $F^\times$. Then $G$ is cyclic. In particular, for every finite field $\mathbb{F}_q$, $$\mathbb{F}_q^{\times}\cong\mathbb{Z}_{q-1}.$$

Proof. Let $|G|=n$. Every element has order dividing $n$ (Lagrange, §6.1). For $d\mid n$ let $\psi(d)$ be the number of elements of $G$ of order exactly $d$. Claim: $\psi(d)\in\{0,\varphi(d)\}$. If $\psi(d)\gt0$, pick $a$ of order $d$. The $d$ distinct elements $1,a,\dots,a^{d-1}$ are roots of $x^d-1$, which has at most $d$ roots in the field $F$ (§7.3). So every element of order $d$ — being a root of $x^d-1$ — lies in the cyclic group $\langle a\rangle$, which contains exactly $\varphi(d)$ elements of order $d$ (§6.1). Now count $G$ by orders, and use Gauss's identity $\sum_{d\mid n}\varphi(d)=n$ (§5.3): $$n=\sum_{d\mid n}\psi(d)\le\sum_{d\mid n}\varphi(d)=n.$$ Equality forces $\psi(d)=\varphi(d)$ for every $d\mid n$; in particular $\psi(n)=\varphi(n)\ge1$, so $G$ has an element of order $n$. ∎

The essential input is that a polynomial of degree $d$ over a field has at most $d$ roots. In the quaternions, $x^2+1$ has infinitely many roots, and indeed the finite subgroup $Q_8$ of $\mathbb{H}^\times$ is not cyclic. Applied to $\mathbb{F}_p$ itself, Theorem 8.20 is the existence of primitive roots modulo a prime (§5.3).

📘 Definition 8.8 — Primitive elements and primitive polynomials of a finite field
A generator of the cyclic group $\mathbb{F}_q^\times$ is a primitive element of $\mathbb{F}_q$. A monic irreducible $f\in\mathbb{F}_p[x]$ of degree $n$ is called a primitive polynomial (in the coding-theory sense) if its roots are primitive elements of $\mathbb{F}_{p^n}$ — equivalently, if $\bar x$ generates the multiplicative group of $\mathbb{F}_p[x]/\langle f\rangle$. (Not to be confused with the primitive polynomials of Gauss's lemma in §7.3, whose coefficients have gcd $1$.)
📐 Theorem 8.21 — Arithmetic consequences of cyclicity
Let $q$ be a prime power and $\gamma$ a primitive element of $\mathbb{F}_q$.
  1. $\mathbb{F}_q=\{0,1,\gamma,\gamma^2,\dots,\gamma^{q-2}\}$, and $\gamma^k$ has order $\tfrac{q-1}{\gcd(k,q-1)}$. There are $\varphi(q-1)$ primitive elements, and exactly $\varphi(d)$ elements of order $d$ for each $d\mid q-1$.
  2. For $n\ge1$ the equation $x^n=1$ has exactly $\gcd(n,q-1)$ solutions in $\mathbb{F}_q$. Hence $\mathbb{F}_q$ contains a primitive $n$-th root of unity iff $n\mid q-1$.
  3. Let $d=\gcd(n,q-1)$. An element $a\ne0$ is an $n$-th power in $\mathbb{F}_q$ iff $a^{(q-1)/d}=1$; there are $(q-1)/d$ nonzero $n$-th powers. In particular, for odd $q$ exactly $\tfrac{q-1}2$ nonzero elements are squares, and $-1$ is a square iff $q\equiv1\pmod4$; for even $q$ every element is a square.
  4. (Wilson's theorem for $\mathbb{F}_q$.) $\prod_{a\in\mathbb{F}_q^\times}a=-1$.
  5. For an integer $k\ge1$: $\sum_{a\in\mathbb{F}_q}a^k=-1$ if $(q-1)\mid k$, and $=0$ otherwise.

Proof. (1) $\mathbb{F}_q^\times=\langle\gamma\rangle\cong\mathbb{Z}_{q-1}$, and these facts hold in every cyclic group (§6.1). (2) $\gamma^k$ satisfies $x^n=1$ iff $(q-1)\mid kn$ iff $\tfrac{q-1}{d}\mid k$, $d=\gcd(n,q-1)$ — that is, for the $d$ values $k=0,\tfrac{q-1}d,\dots,(d-1)\tfrac{q-1}d$ in $[0,q-2]$. An element of order $n$ exists iff $n$ divides the group order $q-1$ (part (1)). (3) The homomorphism $a\mapsto a^n$ of $\mathbb{F}_q^\times$ has kernel of size $d$ by (2), so its image has $(q-1)/d$ elements; the image is contained in $\{a:a^{(q-1)/d}=1\}$ (if $a=b^n$, then $a^{(q-1)/d}=(b^{q-1})^{n/d}=1$), which also has $(q-1)/d$ elements by (2) applied to the exponent $\tfrac{q-1}d$ — so they are equal. For $n=2$, $q$ odd: $d=2$, and $-1=\gamma^{(q-1)/2}$ is a square iff $(-1)^{(q-1)/2}=1$ iff $4\mid q-1$. For $q$ even, $d=\gcd(2,q-1)=1$: squaring is a bijection (it is the Frobenius map). (4) In the cyclic group every element except $1$ and $-1$ is paired with its inverse $\ne$ itself (the only solutions of $a^2=1$ are $\pm1$); the product is $1\cdot(-1)=-1$ (if $q$ is even, $-1=1$ and the product is $1=-1$). (5) $0^k=0$. If $(q-1)\mid k$, every $a\ne0$ has $a^k=1$, and the sum is $q-1=-1$. Otherwise $c=\gamma^k\ne1$ and $\sum_{j=0}^{q-2}\gamma^{jk}=\dfrac{c^{q-1}-1}{c-1}=0$. ∎

Interactive 1 — Powers of an Element: Who Generates $\mathbb{F}_q^\times$?

The $q-1$ nonzero elements of the field sit on a circle in the order $1,\varepsilon,\varepsilon^2,\dots$ of a fixed primitive element $\varepsilon$ (found by the program; it exists by Theorem 8.20). Pick an element $g$ and press Play: the path $1\to g\to g^2\to\cdots$ jumps $\log_\varepsilon g$ places at a time and closes after $\operatorname{ord}(g)=\tfrac{q-1}{\gcd(\log_\varepsilon g,\,q-1)}$ steps. It visits every point exactly when $g$ is primitive. Compare $x$ in $\mathbb{F}_3[x]/\langle x^2+1\rangle$ (order $4$) with $x$ in $\mathbb{F}_3[x]/\langle x^2+x+2\rangle$ (order $8$).

current power—
g^k—
ord(g)—
primitive elements φ(q − 1)—
✏️ Example 2 — Arithmetic in $\mathbb{F}_8$ with a logarithm table
Let $\mathbb{F}_8=\mathbb{F}_2[x]/\langle x^3+x+1\rangle$ and $\alpha=\bar x$. (a) Make the table of powers of $\alpha$. (b) Compute $(\alpha^2+1)(\alpha^2+\alpha)$, $(\alpha^2+\alpha+1)^{-1}$ and solve $(\alpha+1)y+\alpha^2=1$. (c) Find the roots of $x^3+x+1$ and of $x^3+x^2+1$ in $\mathbb{F}_8$, and use them to write down an isomorphism $\mathbb{F}_2[y]/\langle y^3+y^2+1\rangle\to\mathbb{F}_8$.
(a) Using $\alpha^3=\alpha+1$:
$k$$0$$1$$2$$3$$4$$5$$6$
$\alpha^k$$1$$\alpha$$\alpha^2$$\alpha+1$$\alpha^2+\alpha$$\alpha^2+\alpha+1$$\alpha^2+1$
e.g. $\alpha^5=\alpha\cdot\alpha^4=\alpha^3+\alpha^2=\alpha^2+\alpha+1$ and $\alpha^7=\alpha^3+\alpha=1$. All seven nonzero elements appear, so $\alpha$ is primitive; this is automatic, since $7$ is prime and $\alpha\ne1$.
(b) Multiply by adding logarithms mod $7$: $(\alpha^2+1)(\alpha^2+\alpha)=\alpha^6\alpha^4=\alpha^{10}=\alpha^3=\alpha+1$. $(\alpha^2+\alpha+1)^{-1}=\alpha^{-5}=\alpha^2$ (check: $\alpha^5\alpha^2=\alpha^7=1$). For the equation, $(\alpha+1)y=1+\alpha^2=\alpha^6$, so $y=\alpha^6/\alpha^3=\alpha^3=\alpha+1$. Check: $(\alpha+1)^2+\alpha^2=\alpha^2+1+\alpha^2=1$.
(c) By the Frobenius map (Theorem 8.25 below), the roots of $x^3+x+1$ are $\alpha,\alpha^2,\alpha^4$. The remaining elements of degree $3$, $\alpha^3,\alpha^6,\alpha^{12}=\alpha^5$, are the roots of the other irreducible cubic $x^3+x^2+1$. Check for $\alpha^3=\alpha+1$: $(\alpha+1)^3+(\alpha+1)^2+1=(\alpha^3+\alpha^2+\alpha+1)+(\alpha^2+1)+1=\alpha^3+\alpha+1=0$. Hence (Theorem 8.6) $\bar y\mapsto\alpha+1$ defines an isomorphism $\mathbb{F}_2[y]/\langle y^3+y^2+1\rangle\to\mathbb{F}_8$, $a+b\bar y+c\bar y^2\mapsto a+b(\alpha+1)+c(\alpha^2+1)$. There are three such isomorphisms (one for each root).
✏️ Example 3 — Two models of $\mathbb{F}_9$
Let $\mathbb{F}_9=\mathbb{F}_3[x]/\langle x^2+1\rangle=\{a+bi:a,b\in\mathbb{F}_3\}$ with $i=\bar x$, $i^2=-1$. (a) Find the orders of all nonzero elements and the primitive elements. (b) Find the squares, and solve $z^2=i$. (c) Find a root of $y^2+y+2$ in $\mathbb{F}_9$ and hence an isomorphism $\mathbb{F}_3[y]/\langle y^2+y+2\rangle\cong\mathbb{F}_3[x]/\langle x^2+1\rangle$.
(a) $\mathbb{F}_9^\times\cong\mathbb{Z}_8$: one element of order $1$, one of order $2$, two of order $4$ and $\varphi(8)=4$ of order $8$. Here $-1=2$ has order $2$, $\pm i$ have order $4$, so the primitive elements are $\pm1\pm i$. With $g=1+i$: $g^2=2i$, $g^3=1+2i$, $g^4=2$, $g^5=2+2i$, $g^6=i$, $g^7=2+i$, $g^8=1$. (So $x$ is not a primitive element of $\mathbb{F}_3[x]/\langle x^2+1\rangle$: $x^2+1$ is irreducible but not a primitive polynomial.)
(b) The nonzero squares are the even powers of $g$: $g^2=2i$, $g^4=2$, $g^6=i$, $g^8=1$ — four of them, as Theorem 8.21(3) predicts; every element of $\mathbb{F}_3$ (including $2=-1$) is a square in $\mathbb{F}_9$. Since $i=g^6$, $z=\pm g^3=\pm(1+2i)$, i.e. $z\in\{1+2i,\,2+i\}$. Check: $(1+2i)^2=1+4i+4i^2=-3+4i=i$.
(c) By the quadratic formula (valid in characteristic $\ne2$), $y=\tfrac{-1\pm\sqrt{1-8}}{2}=\tfrac{-1\pm\sqrt{-7}}2$, and $-7\equiv2=-1$, so $\sqrt{-7}=\pm i$ and $y=(-1\pm i)\cdot2^{-1}=2(-1\pm i)=1\pm2i$ (as $2^{-1}=2$). Check $y=1+2i$: $y^2+y+2=i+1+2i+2=3+3i=0$. So $\bar y\mapsto1+2i$ is an isomorphism. In the second model $\bar y=1+2i=g^3$ is primitive ($\gcd(3,8)=1$): $y^2+y+2$ is a primitive polynomial.

Existence and Uniqueness of $\mathbb{F}_{p^n}$

📐 Theorem 8.22 — Every element of $\mathbb{F}_q$ is a root of $x^q-x$
If $F$ is a field with $q$ elements, then $a^q=a$ for every $a\in F$, and $$x^q-x=\prod_{a\in F}(x-a),\qquad x^{q-1}-1=\prod_{a\in F^\times}(x-a)\qquad\text{in }F[x].$$

Proof. $F^\times$ is a group of order $q-1$, so $a^{q-1}=1$ for $a\ne0$ (Lagrange), hence $a^q=a$; also $0^q=0$. Thus $x^q-x$, of degree $q$, has the $q$ distinct roots $a\in F$, and by the factor theorem it is divisible by $\prod_a(x-a)$, which is monic of the same degree. Divide by $x$ for the second identity. ∎

📐 Theorem 8.23 — Existence and uniqueness of finite fields (Galois, Moore)
For every prime $p$ and every $n\ge1$ there is a field with exactly $q=p^n$ elements, namely the splitting field of $x^q-x$ over $\mathbb{F}_p$, which consists precisely of the $q$ roots of $x^q-x$. Any two fields with $q$ elements are isomorphic. We write $\mathbb{F}_q$ (or $\mathrm{GF}(q)$, "Galois field") for this field. Concretely, $\mathbb{F}_{p^n}\cong\mathbb{F}_p[x]/\langle f\rangle$ for every irreducible $f\in\mathbb{F}_p[x]$ of degree $n$.

Proof. Existence. Let $K$ be a splitting field of $g=x^q-x$ over $\mathbb{F}_p$ (Theorem 8.11), and $R\subseteq K$ the set of roots of $g$. Since $g'=qx^{q-1}-1=-1$ (as $q=0$ in $K$), $\gcd(g,g')=1$ and $g$ has $q$ distinct roots (Theorem 8.15): $|R|=q$. $R$ is a subfield: it contains $0,1$; if $a,b\in R$ then $(a\pm b)^q=a^q\pm b^q=a\pm b$ (Theorem 8.19 applied $n$ times; note $(-b)^q=-b^q$, also when $p=2$), $(ab)^q=ab$, and $(a^{-1})^q=a^{-1}$ for $a\ne0$. So $R$ is a field containing all roots of $g$ — hence $R=K$ (a splitting field is generated by the roots), and $|K|=q$.

Uniqueness. Let $F$ be any field with $q$ elements. Its characteristic is $p$ (Theorem 8.18), so $F\supseteq\mathbb{F}_p$, and by Theorem 8.22 $g$ splits over $F$ with roots exactly the elements of $F$. Thus $F$ is a splitting field of $g$ over $\mathbb{F}_p$, and any two splitting fields are isomorphic (Theorem 8.12).

Concrete models. If $f$ is irreducible of degree $n$, then $\mathbb{F}_p[x]/\langle f\rangle$ is a field with $p^n$ elements (§7.3), hence isomorphic to $\mathbb{F}_{p^n}$; irreducible polynomials of every degree exist by Gauss's formula for $N_p(n)$ (§7.3). ∎

Uniqueness is why one says "the field with $q$ elements". Its elements look different in different models — in Examples 2 and 3 we found explicit isomorphisms between models — but every algebraic statement true in one model is true in all.

Subfields, the Frobenius Automorphism and Irreducible Polynomials

📐 Theorem 8.24 — The subfields of $\mathbb{F}_{p^n}$
  1. Every subfield of $\mathbb{F}_{p^n}$ has $p^d$ elements for some divisor $d$ of $n$.
  2. Conversely, for each $d\mid n$ there is exactly one subfield with $p^d$ elements, namely $\{a\in\mathbb{F}_{p^n}:a^{p^d}=a\}$.
  3. Hence the subfields correspond to the divisors of $n$ — there are $\tau(n)$ of them — and $\mathbb{F}_{p^d}\subseteq\mathbb{F}_{p^e}$ inside $\mathbb{F}_{p^n}$ iff $d\mid e$. Also $\mathbb{F}_{p^d}\cap\mathbb{F}_{p^e}=\mathbb{F}_{p^{\gcd(d,e)}}$, and the smallest subfield containing both is $\mathbb{F}_{p^{\operatorname{lcm}(d,e)}}$.

Proof. Lemma: for integers $a,b\ge1$ and $m\ge2$, $m^a-1$ divides $m^b-1$ iff $a\mid b$. Write $b=sa+r$ with $0\le r\lt a$. Then $m^b-1=m^r(m^{sa}-1)+(m^r-1)$, and $m^a-1$ divides $m^{sa}-1$ (as $y-1\mid y^s-1$ with $y=m^a$). So $m^b-1\equiv m^r-1\pmod{m^a-1}$ with $0\le m^r-1\lt m^a-1$; this is $0$ iff $r=0$. Applying the lemma twice (with $m=p$, then with $m=x$ in $\mathbb{F}_p[x]$, where the same division argument works): $d\mid n$ $\iff$ $p^d-1\mid p^n-1$ $\iff$ $x^{p^d-1}-1\mid x^{p^n-1}-1$ $\iff$ $x^{p^d}-x\mid x^{p^n}-x$.

(1) If $E$ is a subfield, $\mathbb{F}_p\subseteq E\subseteq\mathbb{F}_{p^n}$, then $|E|=p^d$ with $d=[E:\mathbb{F}_p]$, and $n=[\mathbb{F}_{p^n}:E]\,d$ by the tower law.

(2) Let $d\mid n$ and $E_d=\{a:a^{p^d}=a\}$, the set of fixed points of the automorphism $\sigma^d$; it is a subfield (the argument of Theorem 8.23). Since $x^{p^d}-x$ divides $x^{p^n}-x$, which splits over $\mathbb{F}_{p^n}$ with distinct roots (Theorem 8.22), $x^{p^d}-x$ has $p^d$ distinct roots in $\mathbb{F}_{p^n}$: $|E_d|=p^d$. If $E$ is any subfield with $p^d$ elements, then $a^{p^d}=a$ for all $a\in E$ (Theorem 8.22), so $E\subseteq E_d$, and equal sizes give $E=E_d$.

(3) If $d\mid e$, then $a^{p^d}=a$ implies $a^{p^e}=a$ (iterate), so $E_d\subseteq E_e$; conversely $E_d\subseteq E_e$ makes $E_e$ an extension of $E_d$, so $p^e=(p^d)^{[E_e:E_d]}$ and $d\mid e$. The intersection $E_d\cap E_e$ is a subfield $E_c$ with $c\mid d$, $c\mid e$, and it contains $E_{\gcd(d,e)}$; it is therefore $E_{\gcd(d,e)}$. Similarly for the lcm. ∎

𝔽₄₀₉₆ (d = 12)𝔽₁₆ (d = 4)𝔽₆₄ (d = 6)𝔽₄ (d = 2)𝔽₈ (d = 3)𝔽₂ (d = 1)
The six subfields of $\mathbb{F}_{2^{12}}$: a line joins $\mathbb{F}_{2^d}$ (below) to $\mathbb{F}_{2^e}$ (above) when $d\mid e$ and $e/d$ is prime. $\mathbb{F}_{2^8}$, $\mathbb{F}_{2^5}$ are not subfields.

The lattice of subfields of $\mathbb{F}_{p^n}$ is the lattice of divisors of $n$; for instance $\mathbb{F}_{2^{12}}$ has the six subfields $\mathbb{F}_{2^d}$, $d\in\{1,2,3,4,6,12\}$, with $\mathbb{F}_{2^4}\cap\mathbb{F}_{2^6}=\mathbb{F}_{2^2}$ and $\mathbb{F}_{2^4}\mathbb{F}_{2^6}=\mathbb{F}_{2^{12}}$ — and $\mathbb{F}_{2^8}$, although smaller than $\mathbb{F}_{2^{12}}$, is not among them.

📐 Theorem 8.25 — Irreducible polynomials over $\mathbb{F}_q$ and their roots
Let $q$ be a prime power and $f\in\mathbb{F}_q[x]$ monic irreducible of degree $d$, with a root $\alpha$ in some extension field.
  1. $\mathbb{F}_q(\alpha)$ is a field with $q^d$ elements, and the roots of $f$ are the $d$ distinct elements $\alpha,\alpha^q,\alpha^{q^2},\dots,\alpha^{q^{d-1}}$, all in $\mathbb{F}_q(\alpha)$. So $f$ is separable and $\mathbb{F}_q(\alpha)\cong\mathbb{F}_{q^d}$ is its splitting field.
  2. $f$ divides $x^{q^n}-x$ iff $d\mid n$. Consequently, in $\mathbb{F}_q[x]$, $$x^{q^n}-x=\prod_{d\mid n}\ \prod_{\substack{f\text{ monic irreducible}\\ \deg f=d}}f,\qquad q^n=\sum_{d\mid n}d\,N_q(d),\qquad N_q(n)=\frac1n\sum_{d\mid n}\mu(d)\,q^{n/d}.$$
  3. The degree over $\mathbb{F}_q$ of an element $\beta\in\mathbb{F}_{q^n}$ is the least $d\ge1$ with $\beta^{q^d}=\beta$, i.e. the size of its orbit $\{\beta,\beta^q,\beta^{q^2},\dots\}$ under $\sigma_q$; the minimal polynomial of $\beta$ is $\prod(x-\gamma)$ over that orbit. In $\mathbb{F}_{p^n}$ there are $n\,N_p(n)$ elements of degree exactly $n$ over $\mathbb{F}_p$, and $\dfrac{\varphi(p^n-1)}{n}$ primitive polynomials of degree $n$ over $\mathbb{F}_p$.

Proof. (1) $[\mathbb{F}_q(\alpha):\mathbb{F}_q]=d$ (Theorem 8.5), so $|\mathbb{F}_q(\alpha)|=q^d$ (Theorem 8.18). The map $\tau(a)=a^q$ is an automorphism of $\mathbb{F}_q(\alpha)$ fixing $\mathbb{F}_q$ (Theorems 8.19, 8.22), so $f(\alpha^{q^i})=\tau^i(f(\alpha))=0$: every $\alpha^{q^i}$ is a root. Suppose $\alpha^{q^i}=\alpha^{q^j}$ with $0\le i\lt j\le d-1$; applying $\tau^{d-j}$ and using $\alpha^{q^d}=\alpha$ (Theorem 8.22 in $\mathbb{F}_q(\alpha)$) gives $\alpha^{q^m}=\alpha$ with $m=d-j+i\in[1,d-1]$. Then $\alpha$ lies in the subfield $\{a:a^{q^m}=a\}$, which also contains $\mathbb{F}_q$ and has at most $q^m$ elements — but it must contain $\mathbb{F}_q(\alpha)$, which has $q^d\gt q^m$ elements. Contradiction; so the $d$ listed roots are distinct, and they are all the roots of $f$.

(2) $f\mid x^{q^n}-x$ iff $\alpha^{q^n}=\alpha$ (Theorem 8.4: $f=m_\alpha$) iff $\tau^n$ fixes $\alpha$ iff $\tau^n=\mathrm{id}$ on $\mathbb{F}_q(\alpha)$ (an automorphism fixing $\mathbb{F}_q$ and $\alpha$ fixes $\mathbb{F}_q(\alpha)$). Now $\tau^m=\mathrm{id}$ on $\mathbb{F}_{q^d}$ means that all $q^d$ elements are roots of $x^{q^m}-x$, which forces $m\ge d$ for $m\ge1$; so $\tau$ has order exactly $d$, and $\tau^n=\mathrm{id}\iff d\mid n$. Since $x^{q^n}-x$ is separable ($g'=-1$), it is the product of its distinct monic irreducible factors — precisely those of degree dividing $n$. Comparing degrees gives $q^n=\sum_{d\mid n}dN_q(d)$, and Möbius inversion (§5.3) gives $N_q(n)$, exactly as in Gauss's formula of §7.3.

(3) $m_\beta$ is irreducible over $\mathbb{F}_q$ with root $\beta$; by (1) its degree is the number of distinct elements $\beta^{q^i}$, which is the least $d$ with $\beta^{q^d}=\beta$, and its roots are exactly that orbit. The elements of degree exactly $n$ in $\mathbb{F}_{p^n}$ are the roots of the $N_p(n)$ irreducible polynomials of degree $n$, $n$ roots each. A primitive element $\gamma$ of $\mathbb{F}_{p^n}$ has degree $n$ (it generates $\mathbb{F}_{p^n}$ over $\mathbb{F}_p$), and all $n$ roots of $m_\gamma$, being images of $\gamma$ under automorphisms, are primitive too; so the $\varphi(p^n-1)$ primitive elements fall into $\varphi(p^n-1)/n$ minimal polynomials. ∎

📐 Theorem 8.26 — The automorphisms of $\mathbb{F}_{p^n}$
The Frobenius map $\sigma(a)=a^p$ is an automorphism of $\mathbb{F}_{p^n}$ of order exactly $n$; the fixed points of $\sigma^d$ ($d\mid n$) form the subfield $\mathbb{F}_{p^d}$; and every automorphism of $\mathbb{F}_{p^n}$ is a power of $\sigma$. Thus $\operatorname{Aut}(\mathbb{F}_{p^n})=\{\mathrm{id},\sigma,\dots,\sigma^{n-1}\}\cong\mathbb{Z}_n$ has exactly $[\mathbb{F}_{p^n}:\mathbb{F}_p]=n$ elements.

Proof. The order of $\sigma$ is $n$ by the argument in the proof of Theorem 8.25(2) with $q=p$, $d=n$; the fixed fields are Theorem 8.24(2). Let $\tau$ be any automorphism. It fixes $1$, hence every element of the prime subfield $\mathbb{F}_p$. Let $\gamma$ be a primitive element; then $\mathbb{F}_{p^n}=\mathbb{F}_p(\gamma)$ and $m_\gamma$ has degree $n$ with roots $\gamma^{p^i}=\sigma^i(\gamma)$, $0\le i\lt n$ (Theorem 8.25(1)). Since $\tau(\gamma)$ is a root of $m_\gamma$ (Theorem 8.6(3)), $\tau(\gamma)=\sigma^i(\gamma)$ for some $i$, and then $\tau$ and $\sigma^i$ agree on $0$ and on every power $\gamma^k$, i.e. on all of $\mathbb{F}_{p^n}$. ∎

In the language of §8.3, $\mathbb{F}_{p^n}/\mathbb{F}_p$ is a Galois extension with cyclic Galois group generated by Frobenius, and Theorem 8.24 is the fundamental theorem of Galois theory for it: subgroups $\langle\sigma^d\rangle$ of $\mathbb{Z}_n$ $\leftrightarrow$ subfields $\mathbb{F}_{p^d}$. Interactive 2 shows the orbits of $\sigma$ — they are exactly the sets of roots of the irreducible factors of $x^{q}-x$.

Interactive 2 — Frobenius Orbits, Minimal Polynomials and Subfields

The point at angle $2\pi k/(q-1)$ is $\alpha^k$, where $\alpha=\bar x$ is a primitive element of $\mathbb{F}_p[x]/\langle f\rangle$; the centre is $0$. Frobenius sends $\alpha^k\mapsto\alpha^{pk}$, so its orbits are the sets $\{k,pk,p^2k,\dots\}$ of exponents modulo $q-1$. Play steps through the orbits: each orbit is the set of roots of one monic irreducible factor of $x^q-x$, whose degree is the orbit length (Theorem 8.25). Choose a subfield $\mathbb{F}_{p^d}$ to highlight it: its elements are $0$ and the $\alpha^k$ with $\tfrac{q-1}{p^d-1}\mid k$ — a union of orbits of length dividing $d$.

orbit (exponents k)—
degree = orbit length—
minimal polynomial—
orbits so far—
✏️ Example 4 — Subfields and counting in $\mathbb{F}_{2^{12}}$ and $\mathbb{F}_{3^6}$
(a) List the subfields of $\mathbb{F}_{2^{12}}$. How many elements $\beta$ satisfy $\mathbb{F}_2(\beta)=\mathbb{F}_{2^{12}}$, and how many monic irreducible polynomials of degree $12$ are there over $\mathbb{F}_2$? (b) How many elements of $\mathbb{F}_{3^6}$ lie in no proper subfield? (c) How many primitive elements and how many primitive polynomials of degree $6$ are there over $\mathbb{F}_2$? (d) How many elements of order $9$ does $\mathbb{F}_{64}^\times$ contain, and in which subfield do they lie?
(a) One subfield $\mathbb{F}_{2^d}$ for each $d\in\{1,2,3,4,6,12\}$. $\beta$ generates $\mathbb{F}_{2^{12}}$ iff it lies in no maximal proper subfield, i.e. not in $\mathbb{F}_{2^6}\cup\mathbb{F}_{2^4}$. By inclusion–exclusion, with $\mathbb{F}_{2^6}\cap\mathbb{F}_{2^4}=\mathbb{F}_{2^2}$: $4096-(64+16-4)=4020$. These are the roots of the irreducibles of degree $12$, so $N_2(12)=4020/12=335$. (Möbius: $\tfrac1{12}(2^{12}-2^6-2^4+2^2)=335$.)
(b) Maximal proper subfields of $\mathbb{F}_{3^6}$: $\mathbb{F}_{3^3}$ and $\mathbb{F}_{3^2}$, meeting in $\mathbb{F}_3$. Answer $729-(27+9-3)=696=6\,N_3(6)$, so $N_3(6)=116$ (as in the table of §7.3).
(c) $\varphi(63)=\varphi(9)\varphi(7)=6\cdot6=36$ primitive elements of $\mathbb{F}_{64}$, hence $36/6=6$ primitive polynomials of degree $6$ — out of $N_2(6)=9$ irreducible ones. The $54$ elements of degree $6$ are those whose order divides $63$ but neither $2^3-1=7$ nor $2^2-1=3$: orders $63$ ($36$ elements), $21$ ($\varphi(21)=12$) and $9$ ($\varphi(9)=6$). So the three non-primitive irreducible sextics are two with roots of order $21$ and one with roots of order $9$.
(d) $9\mid63$, so there are $\varphi(9)=6$ elements of order $9$. An element of order $9$ lies in $\mathbb{F}_{2^d}$ iff $9\mid2^d-1$, i.e. $\operatorname{ord}_9(2)=6\mid d$: they lie in no proper subfield, so they have degree $6$ and are the roots of one irreducible sextic (it is $\Phi_9=x^6+x^3+1$ reduced mod $2$, by Theorem 8.27 below). Check of (c): $\varphi(9)+\varphi(21)+\varphi(63)=6+12+36=54=64-8-4+2$.

The same reasoning answers the question left open in §7.3: how does a cyclotomic polynomial factor modulo $p$?

📐 Theorem 8.27 — Cyclotomic polynomials over finite fields
Let $q$ be a prime power and $n\ge1$ with $\gcd(n,q)=1$, and let $m=\operatorname{ord}_n(q)$ be the multiplicative order of $q$ modulo $n$. Then:
  1. $x^n-1$ is separable over $\mathbb{F}_q$, its splitting field is $\mathbb{F}_{q^m}$, and the roots of $\Phi_n$ (reduced into $\mathbb{F}_q[x]$) are exactly the elements of order $n$ in $\mathbb{F}_{q^m}^\times$.
  2. Over $\mathbb{F}_q$, $\Phi_n$ is a product of $\varphi(n)/m$ distinct monic irreducible polynomials, each of degree $m$. In particular $\Phi_n$ is irreducible over $\mathbb{F}_q$ iff $q$ generates $U(n)$ (i.e. $q$ is a primitive root mod $n$).

Proof. (1) $(x^n-1)'=nx^{n-1}$ with $n\ne0$ in $\mathbb{F}_q$; its only root $0$ is not a root of $x^n-1$, so $x^n-1$ is separable. $\mathbb{F}_{q^e}^\times$ is cyclic of order $q^e-1$, so it contains $n$ distinct $n$-th roots of unity iff $n\mid q^e-1$ (Theorem 8.21(2)); the least such $e$ is $m$, so the splitting field is $\mathbb{F}_{q^m}$. The identity $x^n-1=\prod_{d\mid n}\Phi_d$ of §7.3 holds in $\mathbb{Z}[x]$, hence after reduction in $\mathbb{F}_q[x]$. By induction on $n$, the roots of $\Phi_d$ for $d\lt n$, $d\mid n$, are the elements of order $d$; since the roots of $x^n-1$ are distinct and are exactly the elements of order dividing $n$, the roots of $\Phi_n$ are the remaining ones — those of order exactly $n$.

(2) Let $\zeta$ have order $n$. By Theorem 8.25(3) its degree over $\mathbb{F}_q$ is the least $e$ with $\zeta^{q^e}=\zeta$, i.e. $\zeta^{q^e-1}=1$, i.e. $n\mid q^e-1$: the degree is $m$, the same for every root of $\Phi_n$. As $\Phi_n$ is separable, it is the product of the distinct minimal polynomials of its roots, each of degree $m$, and there are $\varphi(n)/m$ of them. ∎

✏️ Example 5 — Factorisations over $\mathbb{F}_2$ and $\mathbb{F}_3$
(a) Factor $x^9-x$ into irreducibles over $\mathbb{F}_3$. (b) Into how many irreducible factors, of which degrees, does $\Phi_{13}$ split over $\mathbb{F}_3$? over $\mathbb{F}_2$? (c) Factor $x^{11}-1$ over $\mathbb{F}_2$ and over $\mathbb{F}_3$ (degrees only). (d) For which primes $p$ is $x^2+1$ irreducible over $\mathbb{F}_p$?
(a) By Theorem 8.25(2) with $q=3$, $n=2$: the product of the $3$ monic linear and $N_3(2)=3$ monic irreducible quadratics. A quadratic is irreducible iff it has no root; checking $x^2+ax+b$ at $0,1,2$ leaves $x^2+1$, $x^2+x+2$, $x^2+2x+2$. So $$x^9-x=x(x-1)(x-2)(x^2+1)(x^2+x+2)(x^2+2x+2).$$ Degrees: $1+1+1+2+2+2=9$.
(b) $\operatorname{ord}_{13}(3)=3$ ($3^3=27=2\cdot13+1$), so over $\mathbb{F}_3$, $\Phi_{13}$ (degree $12$) is a product of $12/3=4$ irreducible cubics. (They are $x^3+2x+2$, $x^3+x^2+2$, $x^3+x^2+x+2$, $x^3+2x^2+2x+2$.) Over $\mathbb{F}_2$: $\operatorname{ord}_{13}(2)=12$ ($2^6=64\equiv-1$), so $\Phi_{13}$ is irreducible.
(c) $x^{11}-1=(x-1)\Phi_{11}$. $\operatorname{ord}_{11}(2)=10$ ($2^5=32\equiv-1$), so over $\mathbb{F}_2$ it is $(x+1)\cdot$ (irreducible of degree $10$). $\operatorname{ord}_{11}(3)=5$ ($3^5=243=22\cdot11+1$), so over $\mathbb{F}_3$ it is $(x-1)\cdot$ (two irreducible quintics).
(d) For $p=2$, $x^2+1=(x+1)^2$. For odd $p$, $x^2+1=\Phi_4$ and $\operatorname{ord}_4(p)$ is $1$ if $p\equiv1\pmod4$ (two linear factors) and $2$ if $p\equiv3\pmod4$ (irreducible). This is again "$-1$ is a square in $\mathbb{F}_p$ iff $p\equiv1\pmod4$".
✏️ Example 6 — Inside $\mathbb{F}_{16}$
Let $\mathbb{F}_{16}=\mathbb{F}_2[x]/\langle x^4+x+1\rangle$, $\alpha=\bar x$. (a) Show that $\alpha$ is primitive. (b) Find the minimal polynomials over $\mathbb{F}_2$ of $\alpha^3$, $\alpha^5$ and $\alpha^7$. (c) Which elements form the subfield $\mathbb{F}_4$? (d) List the primitive polynomials of degree $4$ over $\mathbb{F}_2$ and explain why $x^4+x^3+x^2+x+1$ is irreducible but not primitive.
(a) $x^4+x+1$ has no root in $\mathbb{F}_2$ and is not $(x^2+x+1)^2=x^4+x^2+1$, so it is irreducible (§7.3). The order of $\alpha$ divides $15$; $\alpha^3\ne1$ (it is $\bar x^3$, of degree $3\lt4$), and $\alpha^5=\alpha\cdot\alpha^4=\alpha(\alpha+1)=\alpha^2+\alpha\ne1$. So the order is $15$.
(b) Orbits of exponents under $k\mapsto2k\bmod15$: $\{3,6,12,9\}$, $\{5,10\}$, $\{7,14,13,11\}$. So $\alpha^5$ has degree $2$: it has order $3$, lies in $\mathbb{F}_4$, and its minimal polynomial is $x^2+x+1$. $\alpha^3$ has order $5$: its minimal polynomial is the irreducible quartic with roots of order $5$, i.e. $\Phi_5=x^4+x^3+x^2+x+1$. $\alpha^7$ has order $15$; its minimal polynomial is the reciprocal of that of $\alpha^{-7}=\alpha^8$ (same orbit as $\alpha$), namely $x^4+x^3+1$. Check by expanding $\prod_{k\in\{7,14,13,11\}}(x-\alpha^k)$ with the power table, or in Interactive 2.
(c) $\mathbb{F}_4=\{0\}\cup\{\alpha^k:5\mid k\}=\{0,1,\alpha^5,\alpha^{10}\}=\{0,1,\alpha^2+\alpha,\alpha^2+\alpha+1\}$.
(d) There are $\varphi(15)/4=2$: $x^4+x+1$ and $x^4+x^3+1$ (orbits of $1$ and of $7$). $x^4+x^3+x^2+x+1=\Phi_5$ is irreducible because $\operatorname{ord}_5(2)=4$, but its roots have order $5\ne15$. The three irreducible quartics over $\mathbb{F}_2$ are exactly these three.

The Trace, and Quadratics in Characteristic $2$

In characteristic $2$ the quadratic formula is useless (one cannot divide by $2$), and every element is a square. Whether $x^2+x+a$ has a root is decided instead by a linear map, the trace.

📘 Definition 8.9 — Trace
For $a\in\mathbb{F}_{q^n}$ the trace of $a$ over $\mathbb{F}_q$ is $$\operatorname{Tr}(a)=\operatorname{Tr}_{\mathbb{F}_{q^n}/\mathbb{F}_q}(a)=a+a^q+a^{q^2}+\cdots+a^{q^{n-1}},$$ the sum of the images of $a$ under the $n$ automorphisms $\sigma_q^i$ of $\mathbb{F}_{q^n}$ fixing $\mathbb{F}_q$.
📐 Theorem 8.28 — Properties of the trace; the equation $x^2+x=a$
  1. $\operatorname{Tr}$ takes values in $\mathbb{F}_q$, is $\mathbb{F}_q$-linear and surjective, and each $c\in\mathbb{F}_q$ is the trace of exactly $q^{n-1}$ elements. Also $\operatorname{Tr}(a^q)=\operatorname{Tr}(a)$, and $\operatorname{Tr}(c)=nc$ for $c\in\mathbb{F}_q$.
  2. ($q=2$.) For $a\in\mathbb{F}_{2^n}$ the equation $y^2+y=a$ has a solution in $\mathbb{F}_{2^n}$ iff $\operatorname{Tr}(a)=0$; then it has exactly two, $y$ and $y+1$. Hence $x^2+x+a$ is irreducible over $\mathbb{F}_{2^n}$ iff $\operatorname{Tr}(a)=1$.

Proof. (1) $\operatorname{Tr}(a)^q=a^q+a^{q^2}+\cdots+a^{q^n}=\operatorname{Tr}(a)$ because $a^{q^n}=a$; so $\operatorname{Tr}(a)\in\mathbb{F}_q$ (Theorem 8.24). Each $\sigma_q^i$ is additive and fixes $\mathbb{F}_q$, so $\operatorname{Tr}$ is $\mathbb{F}_q$-linear; $\operatorname{Tr}(a^q)$ is the same sum in a different order. $\operatorname{Tr}$ is not identically zero, since the polynomial $x+x^q+\dots+x^{q^{n-1}}$ has degree $q^{n-1}\lt q^n$ and so cannot vanish at all $q^n$ elements. A nonzero linear map from an $n$-dimensional space onto the $1$-dimensional space $\mathbb{F}_q$ is surjective with kernel of dimension $n-1$; every fibre is a coset of the kernel, of size $q^{n-1}$.

(2) $L(y)=y^2+y$ is $\mathbb{F}_2$-linear on $\mathbb{F}_{2^n}$ (Frobenius is additive) with kernel $\{0,1\}$, so its image has $2^{n-1}$ elements. The image lies in $\ker\operatorname{Tr}$, since $\operatorname{Tr}(y^2+y)=\operatorname{Tr}(y^2)+\operatorname{Tr}(y)=2\operatorname{Tr}(y)=0$; and $|\ker\operatorname{Tr}|=2^{n-1}$ by (1). So $\operatorname{image}(L)=\ker\operatorname{Tr}$. The solutions of $L(y)=a$ form a coset of $\ker L=\{0,1\}$. A quadratic is irreducible iff it has no root. ∎

Example: in $\mathbb{F}_8$ of Example 2, $\operatorname{Tr}(\alpha)=\alpha+\alpha^2+\alpha^4$ is the sum of the roots of $x^3+x+1$, i.e. minus the coefficient of $x^2$, which is $0$; so $y^2+y=\alpha$ is solvable (the solutions are $\alpha^2$ and $\alpha^2+1$), whereas $\operatorname{Tr}(1)=3\cdot1=1$, so $x^2+x+1$ stays irreducible over $\mathbb{F}_8$ — as it must, since $\mathbb{F}_4\not\subseteq\mathbb{F}_8$.

✏️ Example 7 — Finite fields: prove or disprove
Prove or disprove: (a) there is a field $F$ whose multiplicative group is isomorphic to $\mathbb{Z}_2\times\mathbb{Z}_2$; (b) $(\mathbb{F}_q,+)\cong(\mathbb{F}_q^\times,\cdot)$ for some $q$; (c) every irreducible polynomial of degree $4$ over $\mathbb{F}_2$ remains irreducible over $\mathbb{F}_8$; (d) in every finite field $F$, if $a,b\in F^\times$ and $c\in F$, the equation $ax^2+by^2=c$ has a solution $x,y\in F$; in particular every element of $F$ is a sum of two squares.
(a) False $F^\times$ would be a finite subgroup of $F^\times$, hence cyclic (Theorem 8.20); $\mathbb{Z}_2\times\mathbb{Z}_2$ is not.
(b) False The two groups have orders $q$ and $q-1$.
(c) True If $f$ is irreducible of degree $4$ and $\alpha$ a root, $\mathbb{F}_2(\alpha)=\mathbb{F}_{16}$. Over $\mathbb{F}_8$, the field $\mathbb{F}_8(\alpha)$ contains $\mathbb{F}_8$ and $\mathbb{F}_{16}$, so it is $\mathbb{F}_{2^{\operatorname{lcm}(3,4)}}=\mathbb{F}_{2^{12}}$, of degree $4$ over $\mathbb{F}_8$: $\alpha$ still has degree $4$, so $f=m_{\alpha,\mathbb{F}_8}$ is irreducible. (In general, an irreducible of degree $d$ over $\mathbb{F}_q$ splits over $\mathbb{F}_{q^k}$ into $\gcd(d,k)$ irreducibles of degree $d/\gcd(d,k)$; Exercise III.7.)
(d) True For $q$ even every element is a square (Theorem 8.21(3)), so take $y=0$ and $x$ a square root of $c/a$. For odd $q$, the sets $A=\{ax^2:x\in F\}$ and $B=\{c-by^2:y\in F\}$ each have $\tfrac{q+1}{2}$ elements ($\tfrac{q-1}2$ nonzero squares, plus $0$, scaled by $a\ne0$ or $-b\ne0$ and shifted). Since $|A|+|B|=q+1\gt q$, they meet (pigeonhole): $ax^2=c-by^2$. Taking $a=b=1$, every $c$ is a sum of two squares.
⚠️ Counterexamples and pitfalls
  1. $\mathbb{F}_{p^n}$ is not $\mathbb{Z}_{p^n}$. $\mathbb{Z}_4$, $\mathbb{Z}_9$ and the rings $\mathbb{Z}_2\times\mathbb{Z}_2$, $\mathbb{Z}_3\times\mathbb{Z}_3$ have zero divisors. $\mathbb{F}_4$ must be built as $\mathbb{F}_2[x]/\langle x^2+x+1\rangle$.
  2. Subfields need divisibility, not size. $\mathbb{F}_{p^m}\subseteq\mathbb{F}_{p^n}$ iff $m\mid n$: $\mathbb{F}_8\not\subseteq\mathbb{F}_{16}$, $\mathbb{F}_{16}\not\subseteq\mathbb{F}_{2^6}$, although $8\lt16$ and $16\lt64$. And $\mathbb{F}_{p^n}$ never contains $\mathbb{F}_{\ell^m}$ for a different prime $\ell$.
  3. Two meanings of "primitive polynomial". In §7.3: content $1$. Here: the root generates $\mathbb{F}_q^\times$. Irreducible does not imply primitive: $x^2+1$ over $\mathbb{F}_3$ and $x^4+x^3+x^2+x+1$ over $\mathbb{F}_2$ are irreducible, with roots of orders $4\ne8$ and $5\ne15$.
  4. The additive group is not cyclic for $n\ge2$: $(\mathbb{F}_{p^n},+)\cong\mathbb{Z}_p^{\,n}$. The multiplicative group is cyclic. Never confuse $\mathbb{F}_q^\times\cong\mathbb{Z}_{q-1}$ with $(\mathbb{F}_q,+)$.
  5. Polynomials are not functions. $x^q-x\ne0$ in $\mathbb{F}_q[x]$, but it vanishes at every element of $\mathbb{F}_q$; two different polynomials can define the same function on $\mathbb{F}_q$.
  6. $x^n-1$ can be highly inseparable. In characteristic $p$, $x^{p^k}-1=(x-1)^{p^k}$; $x^n-1$ is separable iff $p\nmid n$. Meanwhile $x^{p^n}-x$ is always separable.
  7. Irreducibility is not preserved upward. $x^2+1$ is irreducible over $\mathbb{F}_3$ but splits over $\mathbb{F}_9$; an irreducible of degree $d$ over $\mathbb{F}_q$ stays irreducible over $\mathbb{F}_{q^k}$ iff $\gcd(d,k)=1$.
  8. Characteristic $2$ is different. Every element is a square, $-1=1$, the quadratic formula fails, yet $x^2+x+1$ is irreducible over $\mathbb{F}_2$: solvability of $x^2+x=a$ is governed by the trace, not by squares.
  9. Counting traps. Elements of degree $n$ ($=nN_p(n)$) versus irreducible polynomials of degree $n$ ($N_p(n)$); primitive elements ($\varphi(q-1)$) versus primitive polynomials ($\varphi(q-1)/n$); monic versus all irreducibles (factor $q-1$).
  10. Frobenius is the identity only on $\mathbb{F}_p$. $a^p=a$ for all $a$ only in $\mathbb{F}_p$; on $\mathbb{F}_{p^n}$ the identity is $a^{p^n}=a$. And $(a+b)^p=a^p+b^p$ is false outside characteristic $p$, while for $p\ge3$, $(a+b)^{p-1}\ne a^{p-1}+b^{p-1}$ in general even in characteristic $p$.
  11. Finite fields are never algebraically closed (§8.1); the algebraic closure of $\mathbb{F}_p$ is the infinite union $\bigcup_{n}\mathbb{F}_{p^{n!}}$, every element of which lies in some finite field.
  12. An infinite field of characteristic $p$ exists. $\mathbb{F}_p(t)$ and $\overline{\mathbb{F}_p}$ have characteristic $p$; "characteristic $p$" does not mean "finite".

Exercises

I
Arithmetic in small fields.
  • 1 Show that $\mathbb{F}_2[x]/\langle x^2+1\rangle$ is not a field. For which $c\in\mathbb{F}_5$ is $x^2+c$ irreducible over $\mathbb{F}_5$?
  • 2 In $\mathbb{F}_8=\mathbb{F}_2[x]/\langle x^3+x+1\rangle$ (Example 2) compute $\alpha^{-1}$, $(\alpha^2+1)^{-1}$ and $(\alpha+1)(\alpha^2+\alpha+1)$.
  • 3 In the same $\mathbb{F}_8$, solve $y^2+y=\alpha$, and show that $y^2+y=1$ has no solution.
  • 4 In $\mathbb{F}_9=\mathbb{F}_3[i]$ (Example 3), solve $z^2=2i$ and $z^2=1+i$.
  • 5 In $\mathbb{F}_2[x]/\langle x^4+x^3+x^2+x+1\rangle$, show that $\bar x$ has order $5$ and that $\bar x+1$ is a primitive element.
  • 6 Let $\alpha$ be a root of $x^3+2x+1$ in $\mathbb{F}_{27}$ ($\alpha$ is primitive). Find the minimal polynomials over $\mathbb{F}_3$ of $\alpha^{13}$ and of $\alpha^2$.
  • 7 Let $\alpha$ be a root of $x^2+x+2$ in $\mathbb{F}_{25}$ ($\alpha$ is primitive). Without multiplying out, find $\alpha^{12}$; then find $\alpha^6$ (it lies in $\mathbb{F}_5$).
  • 8 Find an explicit isomorphism from $\mathbb{F}_2[y]/\langle y^4+y^3+1\rangle$ to $\mathbb{F}_2[x]/\langle x^4+x+1\rangle$.
  • 9 How many elements of $\mathbb{F}_{81}$ are squares? How many solutions does $x^{10}=1$ have in $\mathbb{F}_{31}$? in $\mathbb{F}_{125}$?
1 $x^2+1=(x+1)^2$ over $\mathbb{F}_2$, so $\bar x+1$ is a nonzero nilpotent. $x^2+c$ is irreducible iff $-c$ is not a square in $\mathbb{F}_5$; the squares are $0,1,4$, so $-c\in\{2,3\}$, i.e. $c\in\{3,2\}$: $x^2+2$ and $x^2+3$.
2 From the table of Example 2: $\alpha^{-1}=\alpha^6=\alpha^2+1$; $(\alpha^2+1)^{-1}=\alpha^{-6}=\alpha$ (check: $\alpha^3+\alpha=1$); $(\alpha+1)(\alpha^2+\alpha+1)=\alpha^3+1=\alpha$ (or $\alpha^3\alpha^5=\alpha^8=\alpha$).
3 $\operatorname{Tr}(\alpha)=0$, so there are two solutions; trying $y=\alpha^2$: $\alpha^4+\alpha^2=(\alpha^2+\alpha)+\alpha^2=\alpha$. So $y\in\{\alpha^2,\alpha^2+1\}$. $\operatorname{Tr}(1)=1+1+1=1\ne0$, so $y^2+y=1$ has no solution (Theorem 8.28); equivalently $x^2+x+1$ has no root because $\mathbb{F}_4\not\subseteq\mathbb{F}_8$.
4 With $g=1+i$: $2i=g^2$, so $z=\pm g=\pm(1+i)$, i.e. $z\in\{1+i,2+2i\}$. But $1+i=g^1$ is an odd power of a generator, hence not a square: $z^2=1+i$ has no solution (also: $(1+i)^4=g^4=-1\ne1$, Euler's criterion).
5 $x^5-1=(x-1)(x^4+x^3+x^2+x+1)$, so $\bar x^5=1$ and $\bar x\ne1$: order $5$. The order of $\beta=\bar x+1$ divides $15$; $\beta^3=\bar x^3+\bar x^2+\bar x+1=\bar x^4\ne1$, and $\beta^5=\beta^3\beta^2=\bar x^4(\bar x^2+1)=\bar x^6+\bar x^4=\bar x+\bar x^4\ne1$. So $\beta$ has order $15$.
6 $\alpha^{13}$ has order $26/\gcd(13,26)=2$, so $\alpha^{13}=-1$, with minimal polynomial $x+1$. $\alpha^2$: orbit of exponents $\{2,6,18\}$ under $k\mapsto3k\bmod26$, so degree $3$. If $f=x^3+2x+1$, then $f(x)f(-x)=1-(x^3+2x)^2=-(x^6+x^4+x^2-1)$ in $\mathbb{F}_3[x]$, which vanishes at $x=\alpha$; so $\alpha^2$ is a root of $y^3+y^2+y-1=y^3+y^2+y+2$, irreducible (degree $3$, it is the minimal polynomial).
7 $\alpha$ has order $24$, so $\alpha^{12}$ has order $2$: $\alpha^{12}=-1=4$. $\alpha^6$ has order $4$, and the elements of order $4$ in $\mathbb{F}_5^\times$ are $2$ and $3$. From $\alpha^2=-\alpha-2$: $\alpha^3=-\alpha^2-2\alpha=-\alpha+2$, $\alpha^6=(2-\alpha)^2=4-4\alpha+\alpha^2=4-4\alpha-\alpha-2=2-5\alpha=2$.
8 Find a root of $y^4+y^3+1$ in $\mathbb{F}_2[x]/\langle x^4+x+1\rangle$: by Example 6(b) the roots are $\alpha^7,\alpha^{11},\alpha^{13},\alpha^{14}$, and $\alpha^7=\alpha^3+\alpha+1$. So $\bar y\mapsto\alpha^3+\alpha+1$ extends to an isomorphism (Theorem 8.6).
9 $\tfrac{81-1}2+1=41$ squares (including $0$). In $\mathbb{F}_{31}$: $\gcd(10,30)=10$ solutions; in $\mathbb{F}_{125}$: $\gcd(10,124)=2$ solutions ($\pm1$).
II
Structure and counting.
  • 1 For which of the numbers $12$, $16$, $27$, $100$, $121$, $343$, $1000$, $1024$ is there a field with exactly that many elements?
  • 2 Describe the subfields of $\mathbb{F}_{3^8}$. How many elements of $\mathbb{F}_{3^8}$ generate it over $\mathbb{F}_3$, and what is $N_3(8)$?
  • 3 How many primitive elements do $\mathbb{F}_{27}$, $\mathbb{F}_{32}$ and $\mathbb{F}_{81}$ have?
  • 4 How many primitive polynomials of degree $4$ are there over $\mathbb{F}_3$? of degree $5$ over $\mathbb{F}_2$? Why is every irreducible quintic over $\mathbb{F}_2$ primitive?
  • 5 Find the smallest field of characteristic $2$, of characteristic $3$ and of characteristic $5$ containing a primitive $7$-th root of unity.
  • 6 Inside $\mathbb{F}_{2^{12}}$, find $\mathbb{F}_{2^6}\cap\mathbb{F}_{2^4}$ and the smallest subfield containing $\mathbb{F}_{2^6}\cup\mathbb{F}_{2^4}$.
  • 7 Into how many irreducible factors does $x^{81}-x$ split over $\mathbb{F}_3$? $x^{64}-x$ over $\mathbb{F}_2$? over $\mathbb{F}_4$?
  • 8 How many elements of $\mathbb{F}_{2^{10}}$ have degree exactly $10$ over $\mathbb{F}_2$? Deduce $N_2(10)$.
  • 9 For which $n\ge1$ is there a field whose multiplicative group is cyclic of order $n$? (Show first that a field with finite multiplicative group is finite.)
1 Exactly the prime powers: $16=2^4$, $27=3^3$, $121=11^2$, $343=7^3$, $1024=2^{10}$. Not $12$, $100$, $1000$.
2 $d\mid8$: $\mathbb{F}_3\subset\mathbb{F}_9\subset\mathbb{F}_{81}\subset\mathbb{F}_{3^8}$, a chain. Generators: the elements outside the unique maximal subfield $\mathbb{F}_{81}$: $6561-81=6480$. $N_3(8)=6480/8=810$.
3 $\varphi(26)=12$, $\varphi(31)=30$, $\varphi(80)=32$.
4 $\varphi(80)/4=8$ and $\varphi(31)/5=6$. Since $31$ is prime, every element of $\mathbb{F}_{32}^\times$ other than $1$ has order $31$, so every element of degree $5$ is primitive; indeed $N_2(5)=(32-2)/5=6$.
5 $\mathbb{F}_{p^m}$ with $m=\operatorname{ord}_7(p)$ (Theorem 8.21(2)): $\operatorname{ord}_7(2)=3$ gives $\mathbb{F}_8$; $\operatorname{ord}_7(3)=6$ gives $\mathbb{F}_{3^6}=\mathbb{F}_{729}$; $\operatorname{ord}_7(5)=6$ ($5^3=125\equiv-1$) gives $\mathbb{F}_{5^6}$.
6 $\mathbb{F}_{2^{\gcd(6,4)}}=\mathbb{F}_4$ and $\mathbb{F}_{2^{\operatorname{lcm}(6,4)}}=\mathbb{F}_{2^{12}}$ (Theorem 8.24(3)).
7 Theorem 8.25(2). Over $\mathbb{F}_3$, $81=3^4$: $N_3(1)+N_3(2)+N_3(4)=3+3+18=24$. Over $\mathbb{F}_2$, $64=2^6$: $N_2(1)+N_2(2)+N_2(3)+N_2(6)=2+1+2+9=14$. Over $\mathbb{F}_4$, $64=4^3$: $N_4(1)+N_4(3)=4+20=24$.
8 Exclude the maximal subfields $\mathbb{F}_{2^5}$ and $\mathbb{F}_{2^2}$, which meet in $\mathbb{F}_2$: $1024-32-4+2=990$, so $N_2(10)=99$.
9 If $F^\times$ is finite, $F=F^\times\cup\{0\}$ is finite. So $F=\mathbb{F}_q$, and $F^\times\cong\mathbb{Z}_{q-1}$ is always cyclic. Answer: exactly those $n$ for which $n+1$ is a prime power ($n=1,2,3,4,6,7,8,10,12,15,16,18,\dots$; not $5,9,11,13,14,\dots$).
III
Frobenius, roots and cyclotomic polynomials.
  • 1 Show that $\sigma(a)=a^2$ has order $4$ on $\mathbb{F}_{16}$, and identify the fixed points of $\sigma$ and of $\sigma^2$.
  • 2 In $\mathbb{F}_{16}=\mathbb{F}_2[x]/\langle x^4+x+1\rangle$, express the four roots of $x^4+x+1$ in the basis $1,\alpha,\alpha^2,\alpha^3$.
  • 3 Without factoring, find the degrees of the irreducible factors of $\Phi_7$ over $\mathbb{F}_{11}$, $\mathbb{F}_{13}$ and $\mathbb{F}_{29}$.
  • 4 Into how many irreducible factors, of which degree, does $\Phi_{21}$ split over $\mathbb{F}_2$? And $\Phi_{15}$?
  • 5 For which primes $p$ is $x^2+x+1$ irreducible over $\mathbb{F}_p$?
  • 6 Prove that $x^4+1$ is reducible over $\mathbb{F}_p$ for every prime $p$, although it is irreducible over $\mathbb{Q}$.
  • 7 Let $f\in\mathbb{F}_q[x]$ be irreducible of degree $d$ and $k\ge1$. Prove that over $\mathbb{F}_{q^k}$, $f$ is a product of $\gcd(d,k)$ irreducible polynomials, each of degree $d/\gcd(d,k)$.
  • 8 How many monic irreducible polynomials of degree $2$ and of degree $3$ are there over $\mathbb{F}_4$?
1 Theorem 8.26 with $n=4$: $\sigma^4=\mathrm{id}$ and $\sigma^2\ne\mathrm{id}$. Fixed points of $\sigma$: $\mathbb{F}_2$; of $\sigma^2$: $\mathbb{F}_4$ (Theorem 8.24).
2 $\alpha$, $\alpha^2$, $\alpha^4=\alpha+1$, $\alpha^8=(\alpha+1)^2=\alpha^2+1$. Check: their sum is $\alpha+\alpha^2+\alpha+1+\alpha^2+1=0$, minus the coefficient of $x^3$.
3 Degree $m=\operatorname{ord}_7(p)$ and $6/m$ factors: $11\equiv4$, $4^3=64\equiv1$: two cubics. $13\equiv-1$: order $2$, three quadratics. $29\equiv1$: six linear factors.
4 $\operatorname{ord}_{21}(2)=6$ ($2^6=64=3\cdot21+1$): $12/6=2$ sextics (namely $x^6+x^4+x^2+x+1$ and $x^6+x^5+x^4+x^2+1$). $\operatorname{ord}_{15}(2)=4$: $8/4=2$ quartics, $x^4+x+1$ and $x^4+x^3+1$ (Example 6).
5 $p=3$: $x^2+x+1=(x-1)^2$. Otherwise $x^2+x+1=\Phi_3$ and $\operatorname{ord}_3(p)=1$ if $p\equiv1\pmod3$, $2$ if $p\equiv2\pmod3$. So it is irreducible iff $p\equiv2\pmod3$ (including $p=2$).
6 $p=2$: $x^4+1=(x+1)^4$. For odd $p$, $x^4+1=\Phi_8$ and $p^2\equiv1\pmod8$, so $\operatorname{ord}_8(p)\le2$ and the irreducible factors have degree $\le2$ (Theorem 8.27).
7 Let $\alpha$ be a root; $\mathbb{F}_q(\alpha)=\mathbb{F}_{q^d}$. Then $\mathbb{F}_{q^k}(\alpha)$ is the smallest field containing $\mathbb{F}_{q^k}$ and $\mathbb{F}_{q^d}$, i.e. $\mathbb{F}_{q^{\operatorname{lcm}(d,k)}}$, so $\alpha$ has degree $\operatorname{lcm}(d,k)/k=d/\gcd(d,k)$ over $\mathbb{F}_{q^k}$. This holds for every root, and $f$ is separable, so its factors over $\mathbb{F}_{q^k}$ all have this degree; their number is $d\big/\tfrac{d}{\gcd(d,k)}=\gcd(d,k)$.
8 $N_4(2)=\tfrac{16-4}{2}=6$ and $N_4(3)=\tfrac{64-4}{3}=20$.
IV
Proofs, the trace and Artin–Schreier.
  • 1 (Euler's criterion.) For odd $q$ and $a\in\mathbb{F}_q^\times$, prove that $a$ is a square iff $a^{(q-1)/2}=1$, and $a^{(q-1)/2}=-1$ otherwise. Decide whether $2$ is a square in $\mathbb{F}_7$ and in $\mathbb{F}_5$.
  • 2 (Artin–Schreier.) Let $a\in\mathbb{F}_p$, $a\ne0$. Prove that $x^p-x-a$ is irreducible over $\mathbb{F}_p$.
  • 3 Compute $\operatorname{Tr}:\mathbb{F}_4\to\mathbb{F}_2$ on all four elements, and find the number of elements of $\mathbb{F}_{32}$ of trace $0$ over $\mathbb{F}_2$.
  • 4 Prove that $x^2+x+1$ is irreducible over $\mathbb{F}_{2^n}$ iff $n$ is odd, in two ways: by the trace, and by subfields.
  • 5 Prove that $x^{p^n}-x$ has exactly $p^{\gcd(m,n)}$ roots in $\mathbb{F}_{p^m}$.
  • 6 Let $q$ be odd. Show that every primitive element of $\mathbb{F}_q$ is a non-square, and that the primitive elements are all the non-squares iff $q-1$ is a power of $2$. Which $q\lt300$ have this property?
  • 7 Show that $\mathbb{F}_p[x]/\langle f\rangle\cong\mathbb{F}_p[x]/\langle g\rangle$ for any two irreducible $f,g$ of the same degree, and count the isomorphisms between them.
1 $b=a^{(q-1)/2}$ satisfies $b^2=1$, so $b=\pm1$. Theorem 8.21(3) with $n=2$: $a$ is a square iff $b=1$. In $\mathbb{F}_7$: $2^3=8\equiv1$, a square ($3^2=9\equiv2$). In $\mathbb{F}_5$: $2^2=4\equiv-1$, not a square.
2 Let $\beta$ be a root in some extension. For $c\in\mathbb{F}_p$, $(\beta+c)^p-(\beta+c)-a=\beta^p+c-\beta-c-a=0$ (freshman's dream and $c^p=c$), so the roots are $\beta,\beta+1,\dots,\beta+p-1$, all distinct; none lies in $\mathbb{F}_p$, since $c^p-c-a=-a\ne0$ for $c\in\mathbb{F}_p$. If $x^p-x-a=gh$ with $g$ monic of degree $k$, $0\lt k\lt p$, then $g=\prod_{c\in S}(x-\beta-c)$ for a $k$-element set $S$, and the coefficient of $x^{k-1}$ in $g$ is $-(k\beta+\sum_{c\in S}c)\in\mathbb{F}_p$. As $k$ is invertible mod $p$, $\beta\in\mathbb{F}_p$ — a contradiction.
3 $\operatorname{Tr}(a)=a+a^2$: $\operatorname{Tr}(0)=0$, $\operatorname{Tr}(1)=0$, $\operatorname{Tr}(\omega)=\omega+\omega+1=1$, $\operatorname{Tr}(\omega+1)=1$. In $\mathbb{F}_{32}$, $2^{5-1}=16$ elements have trace $0$ (Theorem 8.28(1)).
4 Trace: $\operatorname{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(1)=n\cdot1$, which is $1$ iff $n$ is odd; apply Theorem 8.28(2). Subfields: the roots of $x^2+x+1$ are the elements of order $3$, which generate $\mathbb{F}_4$; they lie in $\mathbb{F}_{2^n}$ iff $\mathbb{F}_4\subseteq\mathbb{F}_{2^n}$ iff $2\mid n$.
5 Work inside $L=\mathbb{F}_{p^{mn}}$, which contains a unique copy of $\mathbb{F}_{p^m}$ and of $\mathbb{F}_{p^n}$ (Theorem 8.24); the roots of $x^{p^n}-x$ in $L$ are exactly the elements of $\mathbb{F}_{p^n}$. So the roots lying in $\mathbb{F}_{p^m}$ form $\mathbb{F}_{p^m}\cap\mathbb{F}_{p^n}=\mathbb{F}_{p^{\gcd(m,n)}}$ (Theorem 8.24(3)): there are $p^{\gcd(m,n)}$ of them.
6 A primitive element is $\gamma^k$ with $\gcd(k,q-1)=1$; as $q-1$ is even, $k$ is odd, and the squares are the even powers. So the $\varphi(q-1)$ primitive elements lie among the $\tfrac{q-1}2$ non-squares, with equality iff $\varphi(q-1)=\tfrac{q-1}2$. Writing $q-1=2^am$ with $m$ odd, $\varphi(q-1)=2^{a-1}\varphi(m)$, which equals $2^{a-1}m$ iff $\varphi(m)=m$ iff $m=1$. For $q\lt300$: $q\in\{3,5,9,17,257\}$ (here $q-1=2,4,8,16,256$).
7 Both are fields with $p^n$ elements, $n=\deg f=\deg g$ (Theorem 8.23). An isomorphism is determined by the image of $\bar x$, which must be a root of $f$ in $\mathbb{F}_p[x]/\langle g\rangle$; $f$ has all its $n$ roots there (Theorem 8.25(1), since this field is $\mathbb{F}_{p^n}$), so there are exactly $n$ isomorphisms (Theorem 8.6) — matching $|\operatorname{Aut}\mathbb{F}_{p^n}|=n$.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA The number of generators of the cyclic group $\mathbb{F}_{49}^{\times}$ is (A) $8$; (B) $16$; (C) $24$; (D) $48$.

Idea $\mathbb{F}_{49}^\times\cong\mathbb{Z}_{48}$ (Theorem 8.20), which has $\varphi(48)$ generators.
Work $\varphi(48)=\varphi(16)\varphi(3)=8\cdot2=16$. (D) counts all nonzero elements; (C) counts the non-squares.
Answer (B).

E2. CSIR Part B The number of subfields of a field with $3^{12}$ elements is (A) $4$; (B) $6$; (C) $7$; (D) $12$.

Idea One subfield $\mathbb{F}_{3^d}$ for each divisor $d$ of $12$ (Theorem 8.24), counting $\mathbb{F}_3$ and the field itself.
Work $d\in\{1,2,3,4,6,12\}$: $\tau(12)=6$.
Answer (B).

E3. CSIR Part B The number of monic irreducible polynomials of degree $6$ over $\mathbb{F}_2$ whose roots generate the multiplicative group of $\mathbb{F}_{64}$ is (A) $6$; (B) $9$; (C) $36$; (D) $54$.

Idea Primitive polynomials: $\varphi(2^6-1)/6$ (Theorem 8.25(3)).
Work $\varphi(63)=36$ primitive elements, six per polynomial: $6$. (B) $=N_2(6)$ counts all irreducible sextics; (C) counts primitive elements; (D) counts elements of degree $6$.
Answer (A).

E4. CSIR Part C Let $F$ be a field with $64$ elements. Which of the following are true? (One or more options may be correct.) (A) $F$ has exactly $4$ subfields. (B) $F^\times$ has an element of order $18$. (C) The equation $x^7=1$ has exactly $7$ solutions in $F$. (D) Every element of $F$ is a cube in $F$.

(A) True $64=2^6$; subfields $\mathbb{F}_{2^d}$, $d\in\{1,2,3,6\}$.
(B) False $F^\times\cong\mathbb{Z}_{63}$ and $18\nmid63$.
(C) True $\gcd(7,63)=7$ solutions (Theorem 8.21(2)); they form $\mathbb{F}_8^\times$.
(D) False $\gcd(3,63)=3$, so $x\mapsto x^3$ is $3$-to-$1$ on $F^\times$ and only $21$ of the $63$ nonzero elements are cubes.
Answer (A) and (C).

E5. CSIR Part C GATE MA Let $f=x^4+x+1\in\mathbb{F}_2[x]$ and $K=\mathbb{F}_2[x]/\langle f\rangle$. Which of the following are true? (A) $K$ is a field with $16$ elements. (B) $\bar x$ generates the group $K^\times$. (C) $f$ splits into linear factors over $K$. (D) $x^2+x+1$ has no root in $K$.

(A) True $f$ is irreducible (no root; not $(x^2+x+1)^2$), so $K$ is a field with $2^4$ elements.
(B) True Example 6(a): $\bar x$ has order $15$.
(C) True Theorem 8.25(1): the roots $\bar x,\bar x^2,\bar x^4,\bar x^8$ all lie in $K$.
(D) False $2\mid4$, so $\mathbb{F}_4\subseteq K$, and the roots of $x^2+x+1$ are the two elements of order $3$, e.g. $\bar x^5=\bar x^2+\bar x$.
Answer (A), (B) and (C).

E6. CSIR Part C Which of the following statements are true? (A) For every prime $p$ and every $n\ge1$ there is an irreducible polynomial of degree $n$ in $\mathbb{F}_p[x]$. (B) A field with $16$ elements contains a subfield with $8$ elements. (C) The polynomial $x^{p^n}-1\in\mathbb{F}_p[x]$ has $p^n$ distinct roots in its splitting field. (D) Any two fields with $25$ elements are isomorphic.

(A) True $N_p(n)\ge1$ (Gauss's formula, §7.3); equivalently, $\mathbb{F}_{p^n}=\mathbb{F}_p(\gamma)$ for a primitive element $\gamma$, whose minimal polynomial has degree $n$.
(B) False $3\nmid4$ (Theorem 8.24).
(C) False $x^{p^n}-1=(x-1)^{p^n}$ in characteristic $p$: a single root. (Contrast $x^{p^n}-x$, which is separable.)
(D) True Theorem 8.23.
Answer (A) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Size and Frobenius; the cyclic group. Theorem 8.18 (why $6$ is impossible), Definition 8.7 and Theorem 8.19, Example 1 built live on the board. Theorem 8.20 with the full counting proof; Definition 8.8; Theorem 8.21 parts (1)–(3). Project Interactive 1: first $\mathbb{F}_8$ (every $g\ne1$ is primitive — why?), then the two models of $\mathbb{F}_9$.
  2. Computing; existence and uniqueness. Examples 2 and 3 with log tables (students compute, the teacher checks with Interactive 1). Theorems 8.22–8.23. Ask the class to construct $\mathbb{F}_{25}$ themselves (find an irreducible quadratic over $\mathbb{F}_5$).
  3. Subfields, Frobenius orbits, counting. Theorem 8.24 with the lattice figure; Theorems 8.25–8.26 with Interactive 2 on $\mathbb{F}_{16}$ and $\mathbb{F}_{64}$ (highlight $\mathbb{F}_4$ and $\mathbb{F}_8$ in turn). Examples 4–6, Theorem 8.27, the trace (Theorem 8.28) if time allows. Finish with E2, E4 and E5 done live.

Discussion questions. (1) $\mathbb{F}_9$ has two different-looking models. In what precise sense are they "the same field", and what is not the same? (2) Why must every finite subgroup of $\mathbb{C}^\times$ be a group of roots of unity — and how does the proof of Theorem 8.20 show it is cyclic? (3) Why do the orbits of $\alpha^k\mapsto\alpha^{pk}$ count irreducible polynomials, and what does an orbit of length $1$ correspond to?

Misconceptions to watch for. Identifying $\mathbb{F}_{p^n}$ with $\mathbb{Z}_{p^n}$; believing $\mathbb{F}_{p^m}\subseteq\mathbb{F}_{p^n}$ whenever $m\lt n$; assuming that $\bar x$ always generates $(F[x]/\langle f\rangle)^\times$; confusing the additive and multiplicative groups; confusing elements with polynomials in counting questions; using the quadratic formula in characteristic $2$.

Suggested homework. I(1, 3, 4, 6, 7), II(2, 4, 5, 7, 9), III(3, 5, 6, 7), IV(1, 2, 4); Exam corner E1, E3, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. The encryption standard AES works in $\mathbb{F}_{256}=\mathbb{F}_2[x]/\langle x^8+x^4+x^3+x+1\rangle$, while QR codes use $\mathbb{F}_2[x]/\langle x^8+x^4+x^3+x^2+1\rangle$. Both are "the" field with $256$ elements — so why did the designers choose different polynomials, and what changes in practice?

Why it matters. AES (adopted as a US federal standard in 2001 and now used worldwide in browsers, phones and banking) builds its non-linear "S-box" from the map $a\mapsto a^{-1}$ on $\mathbb{F}_{256}$; Reed–Solomon codes in QR codes, CDs and deep-space links evaluate polynomials over $\mathbb{F}_{256}$. Implementations multiply bytes either by shift-and-reduce or with logarithm tables, and log tables need a primitive element — exactly Theorem 8.20 and Definition 8.8 at work.

What to do.

  1. Represent bytes as integers $0$–$255$ (bit $i$ = coefficient of $x^i$) and write a function multiplying two bytes modulo a given degree-$8$ polynomial (shift, and XOR with the modulus when bit $8$ appears).
  2. For the AES modulus, compute the multiplicative order of the byte $\texttt{0x02}$ ($=\bar x$) and of $\texttt{0x03}$ ($=\bar x+1$). Which one generates $\mathbb{F}_{256}^\times$? Repeat for the QR-code modulus.
  3. Build log/antilog tables with a generator and use them to invert the byte $\texttt{0x53}$. Check your answer by multiplying back.
  4. Count how many of the $256$ bytes are generators, and how many degree-$8$ primitive polynomials exist over $\mathbb{F}_2$ (Theorem 8.25(3)). Compare with the number $N_2(8)$ of irreducible ones.

Tools: Python (or a spreadsheet with a BITXOR function); the published AES specification (FIPS 197) for the S-box table, to compare with your inverses.

Hand in: Your multiplication and log-table code, the orders found in step 2, the inverse of $\texttt{0x53}$, and a paragraph explaining why both choices of modulus give isomorphic fields but different byte-level arithmetic.

Going further. Find an explicit isomorphism between the two models of $\mathbb{F}_{256}$ (find a root of one modulus inside the other field — Exercise IV.7 says there are $8$ choices), and read about "tower field" implementations of AES that use $\mathbb{F}_{256}\cong\mathbb{F}_{16}[y]/\langle g\rangle$ for compact hardware.

Instructor note (checked in Python): with the AES modulus $\texttt{0x11B}$, $\texttt{0x02}$ has order $51$ (so $x^8+x^4+x^3+x+1$ is irreducible but not primitive) while $\texttt{0x03}$ has order $255$; with the QR modulus $\texttt{0x11D}$, $\texttt{0x02}$ already has order $255$. $\log_{\texttt{0x03}}\texttt{0x53}=48$ and $\texttt{0x53}^{-1}=\texttt{0xCA}$ (as in FIPS 197). There are $\varphi(255)=128$ generators, $\varphi(255)/8=16$ primitive polynomials of degree $8$, and $N_2(8)=30$ irreducible ones.

🧪 Self-check quiz

0/5 correct

Q1. There is a field with exactly

Q2. The multiplicative group of $\mathbb{F}_{25}$ is isomorphic to

Q3. Which of the following is not a subfield of $\mathbb{F}_{2^6}$?

Q4. The Frobenius automorphism $a\mapsto a^3$ of $\mathbb{F}_{3^5}$ has order

Q5. In $\mathbb{F}_{16}=\mathbb{F}_2[x]/\langle x^4+x+1\rangle$ with $\alpha=\bar x$, the degree of $\alpha^5$ over $\mathbb{F}_2$ is