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\}$.
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.
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. ∎
| $+$ | $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 Multiplicative Group Is Cyclic
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).
- $\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$.
- 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$.
- 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.
- (Wilson's theorem for $\mathbb{F}_q$.) $\prod_{a\in\mathbb{F}_q^\times}a=-1$.
- 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$. ∎
| $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$ |
Existence and Uniqueness of $\mathbb{F}_{p^n}$
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. ∎
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
- Every subfield of $\mathbb{F}_{p^n}$ has $p^d$ elements for some divisor $d$ of $n$.
- 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\}$.
- 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. ∎
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.
- $\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.
- $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}.$$
- 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. ∎
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$.
The same reasoning answers the question left open in §7.3: how does a cyclotomic polynomial factor modulo $p$?
- $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$.
- 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. ∎
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.
- $\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$.
- ($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$.
- $\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$.
- 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$.
- 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$.
- 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,+)$.
- 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$.
- $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.
- 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$.
- 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.
- 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$).
- 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$.
- 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.
- 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
- 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 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 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 (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.
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$.
E2. CSIR Part B The number of subfields of a field with $3^{12}$ elements is (A) $4$; (B) $6$; (C) $7$; (D) $12$.
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$.
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$.
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$.
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.
Suggested plan — 3 lectures × 60 min.
- 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$.
- 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$).
- 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 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.
- 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).
- 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.
- Build log/antilog tables with a generator and use them to invert the byte $\texttt{0x53}$. Check your answer by multiplying back.
- 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.
🧪 Self-check quiz
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