素数$p$に対して$\F_p=\{0,1,2,\cdots,p-1\}$とすると，$\bmod p$での演算によって$\F_p$内で和・差・積・（$0$でない元による）商を定義することができる．このように集合に四則演算が定まっている構造のことを，現代数学の言葉では「体」と呼ぶ．上述の$\F_p$の他に，有理数全体$\mathbb{Q}$や実数全体$\mathbb{R}$，複素数全体$\mathbb{C}$なども体の例である．
$\F_p$は$\mathbb{Q}$や$\mathbb{R}$と違って有限個（$p$個）の元からなる．このような体を有限体という．実は$\F_p$の他にも，元の個数が素冪$p^n$であるような有限体$\F_{p^n}$が存在するのだが，その構成法は$\F_p$に比べて少々難しいので，大学で数学を学んだ人以外にはあまり知られていないと思う．そこで本記事ではこれらの有限体$\F_{p^n}$の構成法およびその使い道について解説する．
有限体$\F_{p^n}$は$\bF_p$という大きな（有限体ではない）体から構成することができる．この体$\bF_p$は$\F_p$の代数閉包と呼ばれるものであり，大雑把に言えば$\bmod p$の世界における複素数体$\mathbb{C}$のようなものである．具体的には，$\bF_p$は次のような性質を持っている：
$\bF_p$の具体的な構成法は少々難しく，またそれほど重要ではないので割愛する．以下の説明では上記の$3$つの性質のみを用いる．
$\F_5$係数の多項式$x^2-3$は$\F_5$の中に根を持たないので，$\F_5$係数の範囲ではこれ以上因数分解できないが，$\bF_5$係数の範囲では
$$
x^2-3=(x-\alpha)(x-\beta)\quad (\alpha,\beta\in \bF_p)
$$
と因数分解される．係数を比較すると$\alpha+\beta=0$となるため，$\alpha$を$\sqrt{3}$と書くことにすると$\beta=-\sqrt{3}$と表せる．
$\bF_p$について考える上で重要なのが$p$乗写像
$$
F\colon \bF_p\to \bF_p;\quad F(x)=x^p
$$
である．これをFrobenius写像という．明らかにFrobenius写像は積および商を保つが，実は和と差も保っている：
任意の$x,y\in \bF_p$に対して$(x+y)^p=x^p+y^p$および$(x-y)^p=x^p-y^p$が成り立つ．
二項定理より
$$(x+y)^p=\sum_{i=0}^p\binom{p}{i}x^iy^{p-i}$$
が成り立つ．$i=1,2,\cdots,p-1$に対して$\dbinom{p}{i}$は$p$の倍数なので$\F_p$において$0$である．よって$(x+y)^p=x^p+y^p$となる．
$$
((x-y)+y)^p=(x-y)^p+y^p
$$
を移項すれば$(x-y)^p=x^p-y^p$も得られる．
Frobenius写像$F\colon \bF_p\to \bF_p;\;F(x)=x^p$は全単射である．
$a\in \bF_p$に対して方程式$x^p=a$は$\bF_p$内に解を持つので$F$は全射である．また
$$
y^p=z^p\implies (y-z)^p=0\implies y=z
$$
より$F$は単射である．
任意の$x\in \F_p$に対して$x^p=x$が成り立つというのがFermatの小定理であった．これは次のように一般化される：
任意の$x\in \bF_p$に対し，ある正整数$n$が存在して$x^{p^n}=x$となる．
$x$はある$\F_p$係数多項式の根なので
$$
x^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0=0
$$
を満たす$a_0,a_1,\dots,a_{d-1}\in \F_p$が存在する．この式より，$x^i$の形の元は全て
$$
b_{d-1}x^{d-1}+\cdots+b_1x+b_0\quad(b_0,b_1,\dots,b_{d-1}\in \F_p)
$$
と表せる．特に$S=\{x,x^p,x^{p^2},x^{p^3},\cdots\}$は有限集合である．写像$F\colon S\to S;\;F(y)=y^p$は単射なので全単射となる．特に$F^n(x)=x$となる正整数$n$が存在するのでよい．
$\bF_p$の元$x$に対し，$x^{p^n}=x$となる正整数$n$の最小値を$x$の次数と呼ぶ．
Fermatの小定理より$\F_p$の元の次数は$1$である．次数$1$の元は$x^p-x=0$の解なので高々$p$個しか存在しない．よって$\F_p$は次数$1$の元全体に等しい．
$\bF_5$における$x^2-3=0$の解を$1$つ取って$\sqrt{3}$と書く．このとき
\begin{align*}
&\sqrt{3}^5 = 9\sqrt{3}=-\sqrt{3},\\
&\sqrt{3}^{25}=(-\sqrt{3})^5=\sqrt{3}
\end{align*}
となる．つまり$\sqrt{3}$の次数は$2$である．
後で使うために，$\bF_p$係数の多項式の微分を定義しておく：
$\bF_p$係数多項式$f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0$に対して
$$
f'(x)=da_dx^{d-1}+(d-1)a_{d-1}x^{d-2}+\cdots+a_1
$$
と定める．
$\bF_p$係数多項式$f(x),g(x)$に対して$(f(x)g(x))'=f'(x)g(x)+f(x)g'(x)$が成り立つ．
展開することで$f(x)=ax^d,\;g(x)=bx^e$の場合に帰着できる．この場合は容易である．
素冪$p^n$に対し，$\F_{p^n}=\{x\in \bF_p\mid x^{p^n}=x\}$と定める．つまり，$\F_{p^n}$は次数が$n$の約数であるような$\bF_p$の元全体からなる集合である．
Fermatの小定理より$\F_p\subset\F_{p^n}$が成り立つ．また命題2より，任意の$\bF_p$の元はある$\F_{p^n}$に含まれる．
$x,y\in \F_{p^n}$に対し，$x+y,\;x-y,\;xy\in \F_{p^n}$が成り立つ．さらに$y\neq 0$ならば$x/y\in \F_{p^n}$も成り立つ．
命題1より$(x+y)^{p^n}=x^{p^n}+y^{p^n}=x+y$となるので$x+y\in \F_{p^n}$である．残りの主張も同様に示される．
命題5より$\F_{p^n}$は体をなす．体$\F_{p^n}$を位数$p^n$の有限体と呼ぶ．
$\F_{p^n}$の元の個数は$p^n$である．
$\F_{p^n}$は方程式$x^{p^n}-x=0$の$\bF_p$における解全体である．$\bF_p$係数の範囲で
$$
x^{p^n}-x = \prod_{i=1}^{p^n}(x-\alpha_i)
$$
と因数分解すると，$\F_{p^n}=\{\alpha_1,\dots,\alpha_{p^n}\}$である．よって$\alpha_1,\dots,\alpha_{p^n}$が相異なることを示せばよい．上の式の両辺を微分すると，$\bF_p$において$p^n=0$なので
$$
-1 = \sum_{i=1}^{p^n}\prod_{j\neq i}(x-\alpha_j)
$$
となる．この式に$x=\alpha_i$を代入すると
$$
\prod_{j\neq i}(\alpha_i-\alpha_j) = -1
$$
となるので，$\alpha_1,\dots,\alpha_{p^n}$が相異なることがわかる．
$\bF_5$における$x^2-3=0$の解を$1$つ取って$\sqrt{3}$と書くと，例3で見たように$\sqrt{3}\in\F_{25}$である．命題5より
$$
a+b\sqrt{3}\quad (a,b\in \F_5)
$$
という形の元は全て$\F_{25}$に属する．またこれらの元は相異なることが容易に示せる．$\F_{25}$は$25$個の元からなるので，結局
$$
\F_{25}= \{a+b\sqrt{3}\mid a,b\in \F_5\}
$$
となることがわかる．
$\F_{p^n}\subset \F_{p^m}\iff n\mid m$.
$n\mid m$ならば$\F_{p^n}\subset \F_{p^m}$であることは定義から明らかである．逆に$\F_{p^n}\subset \F_{p^m}$であると仮定して$n\mid m$を示そう．$n$を割り切る素冪$l^k$に対して$l^k\mid m$を示せばよいので，$n=l^k$の場合に帰着される．命題6より，$\F_{p^{l^k}}$に含まれるが$\F_{p^{l^{k-1}}}$に含まれない元$x$を取ることができる．このとき$x$の次数はちょうど$l^k$なので，$x\in \F_{p^m}$より$l^k\mid m$が得られる．
命題7より，小さい$n$に対する$\F_{p^n}$の包含関係は以下のようになっている（矢印は包含写像）：
$$
\xymatrix{
\F_{p^4}&\F_{p^6}\\
\F_{p^2}\ar[u]\ar[ur]&\F_{p^3}\ar[u]&\F_{p^5}\\
&\F_p\ar[u]\ar[ul]\ar[ur]
}
$$
具体的な$\bF_p$の元の次数を求めるには，以下の命題を用いるのが便利である：
$f(x)$を$\F_p$係数の$n$次多項式とし，$\alpha$を$\bF_p$における$f(x)$の根とする．$f(x)$が$\F_p$上既約（$\F_p$係数の範囲でこれ以上因数分解できない）ならば，$\alpha$の次数は$n$であり，$\bF_p$における$f(x)$の根は$\alpha,\alpha^p,\alpha^{p^2},\dots,\alpha^{p^{n-1}}$である．
$f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0\;(a_i\in \F_p)$とする．$\beta\in \bF_p$が$f(x)$の根ならば
$$
a_d\beta^d+a_{d-1}\beta^{d-1}+\cdots+a_1\beta+a_0 = 0
$$
であるが，両辺にFrobenius写像を適用すると，$a_i^p=a_i$より
$$
a_d\beta^{dp}+a_{d-1}\beta^{(d-1)p}+\cdots+a_1^p\beta+a_0 = 0
$$
となるので，$\beta^p$も$f(x)$の根である．つまり，$\bF_p$における$f(x)$の根全体の集合を$S$とすると，写像$F\colon S\to S;\;F(x)=x^p$が定まる．$F$は単射なので全単射である．$F^k(\alpha)=\alpha$となる正整数$k$のうち最小のものを取る．$T=\{\alpha,\alpha^p,\dots,\alpha^{p^{k-1}}\}$と定めると，$F$は全単射$T\to T$に制限できる．
$$
g(x)=a_d\prod_{\beta\in T} (x-\beta)
$$
と定めると，$g(x)$の係数はFrobenius写像で不変なので，$g(x)$は$\F_p$係数多項式となる．定義より$g(x)$は$f(x)$を割り切るので，$f(x)$が既約であるという仮定より$g(x)=f(x)$となる．よって$k=n,\;T=S$である．
有限体の応用例として，Fibonacci数の$\bmod p$での振る舞いについて調べる．Fibonacci数列は
$$
F_1=F_2=1,\quad F_{n+2}=F_{n+1}+F_n
$$
により定まる数列であり，その一般項は
$$
F_n=\dfrac{\phi^n-\overline{\phi}^n}{\phi-\overline{\phi}}\quad\left(\phi=\dfrac{1+\sqrt{5}}{2},\;\overline{\phi}=\dfrac{1-\sqrt{5}}{2}\right)
$$
で与えられる．これの「$\bmod p$版」を考えよう．$\bF_p$における$x^2-5=0$の解を$1$つ取って$\sqrt{5}$と書く．
$p$を素数とする．
(1) $p=2$ならば$\sqrt{5}=1$である．
(2) $p=5$ならば$\sqrt{5}=0$である．
(3) $p\equiv 1,4\pmod{5}$ならば$\sqrt{5}\in \F_p$である．
(4) $p\equiv 2,3\pmod{5},\;p\neq 2$ならば$\sqrt{5}\in \F_{p^2}\setminus\F_p$であり，$\sqrt{5}^p=-\sqrt{5}$である．
(1),(2)は明らかである．以下$p$は$2,5$でないとする．平方剰余の相互法則より，$p\equiv 1,4\pmod{5}$ならば$p$は$\bmod 5$で平方剰余であり，$p\equiv 2,3\pmod{5}$ならば$p$は$\bmod 5$で平方非剰余である．前者の場合，$x^2-5=0$は$\F_p$に解を持つので$\sqrt{5}\in \F_p$となる．後者の場合，$x^2-5$は$\F_p$上既約なので，命題8より$\sqrt{5}$の次数は$2$であり，$\sqrt{5}^p=-\sqrt{5}$となる．
以下では$p\neq 2,5$とする．$\bF_p$の元$\alpha,\beta$を
$$
\alpha = \dfrac{1+\sqrt{5}}{2},\quad \beta = \dfrac{1-\sqrt{5}}{2}
$$
により定める．また$\bF_p$の元$u_n$を
$$
u_n = \dfrac{\alpha^n-\beta^n}{\alpha-\beta}
$$
により定める．すると$u_1=1,\;u_2=\alpha+\beta=1$であり，また$\alpha^{n+2}=\alpha^{n+1}+\alpha^n$および$\beta^{n+2}=\beta^{n+1}+\beta^n$より
$$
u_{n+2} = u_{n+1} + u_n
$$
が成り立つ．すなわち，$u_n$は$F_n$を$\bmod p$で考えたものに他ならない．これを用いると次のような事実が示せる．
素数$p\neq 2,5$に対して$F_{n+2p}=F_{n+p}+F_n\pmod{p}$が成り立つ．
$\alpha^2=\alpha+1$にFrobenius写像を適用すると$\alpha^{2p}=\alpha^p+1$となり，$\alpha^{n+2p}=\alpha^{n+p}+\alpha^n$が得られる．同様に$\beta^{n+2p}=\beta^{n+p}+\beta^n$も成り立つので，$u_{n+2p}=u_{n+p}=u_n$が得られる．
$p$を$2,5$以外の素数とする．
(1) $p\equiv 1,4\pmod{5}$ならば$F_{n+p-1}\equiv F_n\pmod{p}$が成り立つ．
(2) $p\equiv 2,3\pmod{5}$ならば$F_{n+p+1}\equiv -F_n\pmod{p}$が成り立つ．
$p\equiv 1,4\pmod{5}$ならば命題9より$\alpha,\beta\in \F_p$なので$\alpha^{n+p-1}=\alpha^n,\;\beta^{n+p-1}=\beta^n$である．よって$u_{n+p-1}=u_n$が得られる．$p\equiv 2,3\pmod{5}$ならば命題9より$\alpha,\beta\in \F_{p^2}\setminus\F_p$であり，$\alpha^p=\beta,\;\beta^p=\alpha$である．よって
$$
\alpha^{n+p+1}=\alpha^n(\alpha\beta)=-\alpha^n
$$
であり，同様に$\beta^{n+p+1}=-\beta^n$も成り立つので，$u_{n+p+1}=-u_n$が得られる．