\chapter{Finite fields}
\label{ch:finite_fields}
In this short chapter, we classify all fields with finitely many elements
and compute the Galois groups.
Nothing in here is very hard, and so most of the proofs are just sketches;
if you like, you should check the details yourself.

The whole point of this chapter is to prove:
\begin{itemize}
	\ii A finite field $F$ must have order $p^n$, with $p$ prime and $n$ an integer.
	\ii In this case, $F$ has characteristic $p$.
	\ii All such fields are isomorphic,
	so it's customary to use the notation $\FF_{p^n}$
	for ``the'' finite field of order $p^n$ if we only care up to isomorphism.
	\ii The extension $F/\FF_p$ is Galois, and $\Gal(F/\FF_p)$ is a cyclic group of order $n$.
	The generator is the automorphism \[ \sigma \colon F \to F \quad\text{by}\quad x \mapsto x^p. \]
\end{itemize}
If you're in a hurry you can just remember these results and skip to the next chapter.

\section{Example of a finite field}
Before diving in, we give some examples.

Recall that the \emph{characteristic} of a field $F$
is the smallest positive integer $p$ such that
\[ \underbrace{1_F + \dots + 1_F}_{\text{$p$ times}} = 0 \]
or $0$ if no such integer $p$ exists.

\begin{example}[Base field]
	Let $\FF_p$ denote the field of integers modulo $p$.
	This is a field with $p$ elements, with characteristic $p$.
\end{example}

\begin{example}[The finite field of nine elements]
	Let
	\[ F \cong \FF_3[X]/(X^2+1) \cong \ZZ[i] / (3). \]
	We can think of its elements as \[ \left\{ a + bi \mid 0 \le a,b \le 2 \right\}. \]
	Since $(3)$ is prime in $\ZZ[i]$, the ring of integers of $\QQ(i)$,
	we see $F$ is a field with $3^2 = 9$ elements inside it.
	Note that, although this field has $9$ elements, every element $x$ has the property that
	\[ 3x = \underbrace{x + \dots + x}_{\text{$3$ times}} = 0. \]
	In particular, $F$ has characteristic $3$.
\end{example}

\section{Finite fields have prime power order}
\begin{lemma}
	If the characteristic of a field $F$ isn't zero,
	it must be a prime number.
\end{lemma}
\begin{proof}
	Assume not, so $n = ab$ for $a,b < n$.
	Then let
	\[ A = \underbrace{1_F + \dots + 1_F}_{\text{$a$ times}} \neq 0 \]
	and
	\[ B = \underbrace{1_F + \dots + 1_F}_{\text{$b$ times}} \neq 0. \]
	Then $AB = 0$, contradicting the fact that $F$ is a field.
\end{proof}

We like fields of characteristic zero, but unfortunately for finite fields
we are doomed to have nonzero characteristic.

\begin{lemma}
	[Finite fields have prime power orders]
	Let $F$ be a finite field.
	Then
	\begin{enumerate}[(a)]
		\ii Its characteristic is nonzero, and hence some prime $p$.
		\ii The field $F$ is a finite extension of $\FF_p$,
		and in particular it is an $\FF_p$-vector space.
		\ii We have $\left\lvert F \right\rvert = p^n$ for some prime $p$, integer $n$.
	\end{enumerate}
\end{lemma}
\begin{proof}
	Very briefly, since this is easy:
	\begin{enumerate}[(a)]
		\ii Apply Lagrange's theorem (or pigeonhole principle!)
		to $(F, +)$ to get the characteristic isn't zero.
		\ii The additive subgroup of $(F,+)$ generated
		by $1_F$ is an isomorphic copy of $\FF_p$.
		\ii Since it's a field extension,
		$F$ is a finite-dimensional vector space over $\FF_p$,
		with some basis $e_1, \dots, e_n$.
		It follows that there are $p^n$ elements of $F$. \qedhere
	\end{enumerate}
\end{proof}
\begin{remark}
	An amusing alternate proof of (c) by contradiction:
	if a prime $q \neq p$ divides $\left\lvert F \right\rvert$, then
	by Cauchy's theorem (\Cref{thm:cauchy_group}) on $(F, +)$
	there's a (nonzero) element $x$ of order $q$.
	Evidently \[ x \cdot ( \underbrace{1_F + \dots + 1_F}_{\text{$q$ times}} ) = 0 \]
	then, but $x \neq 0$, and hence the characteristic of $F$ also divides $q$,
	which is impossible.
\end{remark}

An important point in the above proof is that
\begin{lemma}[Finite fields are field extensions of $\FF_p$]
	If $\left\lvert F \right\rvert = p^n$ is a finite field,
	then there is an isomorphic copy of $\FF_p$ sitting inside $F$.
	Thus $F$ is a field extension of $\FF_p$.
\end{lemma}

We want to refer a lot to this copy of $\FF_p$, so in what follows:
\begin{abuse}
	Every integer $n$ can be identified as an element of $F$, namely
	\[ n \defeq \underbrace{1_F + \dots + 1_F}_{\text{$n$ times}}. \]
	Note that (as expected) this depends only on $n \pmod p$.
\end{abuse}

This notation makes it easier to think about statements like the following.
\begin{theorem}
	[Freshman's dream]
	For any $a,b \in F$ we have
	\[ (a+b)^p = a^p + b^p. \]
\end{theorem}
\begin{proof}
	Use the Binomial theorem, and the fact that $\binom pi$ is divisible by $p$ for $0 < i < p$.
\end{proof}
\begin{exercise}
	Convince yourself that this proof works.
\end{exercise}

\section{All finite fields are isomorphic}
We next proceed to prove ``Fermat's little theorem'':
\begin{theorem}
	[Fermat's little theorem in finite fields]
	Let $F$ be a finite field of order $p^n$.
	Then every element $x \in F$ satisfies
	\[ x^{p^n} - x = 0. \]
\end{theorem}
\begin{proof}
	If $x = 0$ it's true; otherwise, use Lagrange's theorem
	on the abelian group $(F, \times)$ to get $x^{p^n-1} = 1_F$.
\end{proof}

We can now prove the following result,
which is the ``main surprise'' about finite fields:
that there is a unique one up to isomorphism for each size.
\begin{theorem}[Complete classification of finite fields]
	A field $F$ is a finite field with $p^n$ elements if and only if
	it is a splitting field of $x^{p^n}-x$ over $\FF_p$.
\end{theorem}
\begin{proof}
	By ``Fermat's little theorem'', all the elements of $F$ satisfy this polynomial.
	So we just have to show that the roots of this polynomial are distinct
	(i.e.\ that it is separable).

	To do this, we use the derivative trick again: the derivative of this polynomial is
	\[ p^n \cdot x^{p^n-1} - 1  = -1 \]
	which has no roots at all, so the polynomial cannot have any double roots. \qedhere
\end{proof}

\begin{definition}
	For this reason, it's customary to denote \emph{the}
	field with $p^n$ elements by $\FF_{p^n}$.
\end{definition}

Note that the polynomial $x^{p^n}-x \pmod p$ is far from irreducible, but
the computation above shows that it's separable.
\begin{example}[The finite field of order nine again]
	The polynomial $x^9-x$ is separable modulo $3$ and has factorization
	\[ x(x+1)(x+2)(x^2+1)(x^2+x+2)(x^2+2x+2) \pmod 3. \]

	So if $F$ has order $9$, then we intuitively expect it to be the field
	generated by adjoining all the roots: $0$, $1$, $2$, as well as
	$\pm i$, $1 \pm i$, $2 \pm i$.
	Indeed, that's the example we had at the beginning of this chapter.

	(Here $i$ denotes \emph{an} element of $\FF_9$ satisfying $i^2=-1$.
	The notation is deliberately similar to the usual imaginary unit.)
\end{example}

\section{The Galois theory of finite fields}
Retain the notation $\FF_{p^n}$ now (instead of $F$ like before).
By the above theorem, it's the splitting field of a separable polynomial,
hence we know that $\FF_{p^n} /\FF_p$ is a Galois extension.
We would like to find the Galois group.

In fact, we are very lucky: it is cyclic.
First, we exhibit one such element $\sigma_p \in \Gal(\FF_{p^n} /\FF_p)$:

\begin{theorem}[The $p$th power automorphism]
	The map $\sigma_p \colon \FF_{p^n} \to \FF_{p^n}$ defined by
	\[ \sigma_p(x) = x^p \]
	is an automorphism, and moreover fixes $\FF_p$.
\end{theorem}
This is called the Frobenius automorphism, and will re-appear later on in \Cref{ch:frobenius-element}.
\begin{proof}
	It's a homomorphism since it fixes $1$,
	respects multiplication,
	and respects addition.
	\begin{ques}
		Why does it respect addition?
	\end{ques}
	Next, we claim that it is injective. To see this, note that
	\[ x^p = y^p
		\iff x^p - y^p = 0
		\iff (x-y)^p = 0
		\iff x=y.
	\]
	Here we have again used the Freshman's Dream.
	Since $\FF_{p^n}$ is finite, this injective map is automatically bijective.
	The fact that it fixes $\FF_p$ is Fermat's little theorem.
\end{proof}

Now we're done:
\begin{theorem}
	[Galois group of the extension $\FF_{p^n}/\FF_p$]
	We have $\Gal(\FF_{p^n}/\FF_p) \cong \Zc n$ with generator $\sigma_p$.
\end{theorem}
\begin{proof}
	Since $[\FF_{p^n}:\FF_p] = n$, the Galois group $G$ has order $n$.
	So we just need to show $\sigma_p \in G$ has order $n$.

	Note that $\sigma_p$ applied $k$ times gives $x \mapsto x^{p^k}$.
	Hence, $\sigma_p$ applied $n$ times is the identity,
	as all elements of $\FF_{p^n}$ satisfy $x^{p^n}=x$.
	But if $k < n$, then $\sigma_p$ applied $k$ times
	cannot be the identity or $x^{p^k}-x$ would have too many roots.
\end{proof}

We can see an example of this again with the finite field of order $9$.
\begin{example}
	[Galois group of finite field of order $9$]
	Let $\FF_9$ be the finite field of order $9$,
	and represent it concretely by $\FF_9 = \ZZ[i]/(3)$.
	Let $\sigma_3 \colon \FF_9 \to \FF_9$ be $x \mapsto x^3$.
	We can witness the fate of all nine elements:
	\begin{center}
	\begin{tikzcd}
		0 & 1 & 2
			& i \ar[d, leftrightarrow, "\sigma"]
			& 1+i \ar[d, leftrightarrow, "\sigma"]
			& 2+i \ar[d, leftrightarrow, "\sigma"] \\
		&&& -i & 1-i & 2-i
	\end{tikzcd}
	\end{center}
	(As claimed, $0$, $1$, $2$ are the fixed points,
	so I haven't drawn arrows for them.)
	As predicted, the Galois group has order two:
	\[ \Gal(\FF_9/\FF_3) = \left\{ \id, \sigma_3 \right\} \cong \Zc 2. \]
\end{example}

This concludes the proof of all results stated at the beginning of this chapter.

\section{Extra: The multiplicative group of a finite field}

In this section we prove a result which is interesting by its own right, even though it is not used
in the following chapters.

Consider the field $F$ of order $p = 17$. We may want to ask the following questions about $F$:
\begin{itemize}
	\ii How many nonzero elements in $F$ are quadratic residues (can be written as a square of
	another element in $F$)?
	\ii Is there any element $x$ in $F$ such that $x^2 = -1$?
\end{itemize}

With the following proposition, the questions above become easy.
\begin{proposition}
	Let $F$ be a finite field, then the multiplicative group $F^\times$ is a cyclic group.
\end{proposition}

Essentially, it says that the multiplicative group $F^\times$ is as nice as possible --- the cyclic
group is the simplest Abelian group!

If we look back at the examples above, we can see how this knowledge can help us.

\begin{example}[The multiplicative group of $\FF_{17}$]
The group $F^\times$ is cyclic of order $16$, so there is some element $g \in F^\times$ such
that all of the elements in $F$ are
\[ 0, g^0 = 1, g^1, g^2, \dots, g^{15}.  \]
Using this knowledge, if we square the nonzero elements, we can easily see that the result are the
following (note that $g^{16} = g^0 = 1$):
\[ g^0, g^2, g^4, \dots, g^{14}, g^0, g^2, \dots, g^{14}.  \]
As such, exactly half of the elements --- 8 elements --- in $F^\times$ are quadratic residues!

Checking whether there is an element $x$ such that $x^2 = -1$ isn't much harder.
First, where may $-1$ appear in the sequence $\{g^0, g^1, \dots, g^{15} \}$?
If you find an explicit value of $g$ (you can pick $g = 3$ for instance), you will see that $g^8 =
-1$. But, even without an explicit calculation, you can still see that, because:
\begin{ques}
	Note that the equation $x^2 = 1$ has only $2$ roots, $1$ and $-1$.
	Using group operations in the group $F^\times$, what does the equation say?
\end{ques}
We have $g^8 = -1$, so $(g^4)^2 = (g^{12})^2 = -1$, so we're done.
\end{example}

So, why is the proposition true? Consider a finite field $F$ of order a prime power $q$.

First, using an idea similar to the above, we have:
\begin{ques}
	Show that, for any positive $d < |F^\times| = q-1$, then there are at most $d$ elements $x$ such
	that $x^d = 1$.
\end{ques}
The rest is easily handled using group theory.
Recall from \Cref{thm:fund_fg_abelian_group}, because $F^\times$ is a finite Abelian group, it is
in particular finitely generated, and can be written in the form
\[ F^\times \cong \ZZ^{\oplus r} \oplus \Zc{q_1} \oplus \Zc{q_2} \oplus
	\dots \oplus \Zc{q_m}.  \]
Of course, $r = 0$ here.

Now, assume $F^\times$ is not cyclic, so the least common multiple of all the $q_i$ values is
less than $|F^\times|$.
Then, for all $x \in F^\times$, $x^{\lcm(q_1, \dots, q_m)} = 1$, which gives a contradiction.

\begin{remark}
	If you look up an elementary proof of why there are exactly $\frac{p-1}{2}$ quadratic residues modulo $p$,
	most of the time, you will get some argument using ``$x^d-1$ has at most $d$ roots'' similar to
	the proof above, but by not going all the way and show the structure of the multiplicative
	group, it hides the spirit of what is really going on.

	The proposition above takes a step further --- now, without any calculation, you know
	for instance the finite field $\FF_{17^2}$ has exactly $\frac{17^2-1}{2} = 144$ nonzero
	quadratic residues.
\end{remark}

\section\problemhead
\begin{dproblem}[HMMT 2017]
	\onechili
	What is the period of the Fibonacci sequence modulo $127$?
	\begin{hint}
	The Fibonacci sequence is given by
	$F_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$
	where $\alpha = \frac{1 + \sqrt5}{2}$ and $\beta = \frac{1 - \sqrt5}{2}$
	are the two roots of $P(X) \overset{\text{def}}{=} X^2-X-1$.
	Show the polynomial $P(X)$ is irreducible modulo $127$;
	then work in the splitting field of $P$, namely $\FF_{p^2}$.

	Show that $F_p=-1$, $F_{p+1}=0$, $F_{2p+1}=1$, $F_{2p+2}=0$.
	(Look at the action of $\Gal(\FF_{p^2}/\FF_p)$
	on the roots of $P$.)
	\end{hint}
	\begin{sol}
	Recall that the Fibonacci sequence is given by
	\[ F_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} \]
	where $\alpha = \frac{1 + \sqrt5}{2}$ and $\beta = \frac{1 - \sqrt5}{2}$
	are the two roots of $P(X) \defeq X^2-X-1$.

	Let $p = 127$ and work modulo $p$.
	As \[ \left( \frac5p \right) = \left( \frac p5 \right) = \left( \frac 25
		\right) = -1 \]
	we see $5$ is not a quadratic residue mod $127$.
	Thus the polynomial $P(X)$,
	viewed as a polynomial in $\FF_p[X]$, is irreducible
	(intuitively, $\alpha$ and $\beta$ are not elements of $\FF_p$).
	Accordingly we will work in the finite field $\FF_{p^2}$,
	which is the $\FF_p$-splitting field of $P(X)$.
	In other words we interpret $\alpha$ and $\beta$ as elements
	of $\FF_{p^2}$ which do not lie in $\FF_p$.

	Let $\sigma \colon \FF_{p^2} \to \FF_{p^2}$ by $t \mapsto t^p$
	be the nontrivial element of
	$\opname{Gal}\left( \FF_{p^2} / \FF_p \right)$;
	in other words, $\sigma$ is the non-identity automorphism of $\FF_{p^2}$.
	Since the fixed points of $\sigma$ are the elements of $\FF_p$,
	this means $\sigma$ does not fix either root of $P$; thus we must have
	\begin{align*}
		\alpha^p = \sigma(\alpha) &= \beta \\
		\beta^p = \sigma(\beta) &= \alpha.
	\end{align*}
	Now, compute
	\begin{align*}
		F_{p} &= \frac{\alpha^{p} - \beta^{p}}{\alpha-\beta} =
		\frac{\beta-\alpha}{\alpha-\beta} = -1. \\
		F_{p+1} &= \frac{\alpha^{p+1} - \beta^{p+1}}{\alpha-\beta} =
		\frac{\alpha\beta-\beta\alpha}{\alpha-\beta} = 0. \\
		F_{2p+1} &= \frac{\alpha^{2p+1} - \beta^{2p+1}}{\alpha-\beta}
			= \frac{\beta^2\alpha-\alpha^2\beta}{\alpha-\beta}
			= - \alpha \beta = 1.  \\
		F_{2p+2} &= \frac{\alpha^{2p+2} - \beta^{2p+2}}{\alpha-\beta}
			= \frac{\beta^2\alpha^2-\alpha^2\beta^2}{\alpha-\beta} = 0.
	\end{align*}
	Consequently, the period must divide $2p+2$ but not $p+1$.

	We now use for the first time the exact numerical value $p=127$
	to see the period divides $2p+2 = 256 = 2^8$,
	but not $p+1 = 128 = 2^7$.
	(Previously we only used the fact that $(5/p)=-1$.)
	Thus the period must be exactly $256$.
	\end{sol}
\end{dproblem}
