フェルマーの小定理の証明 - オタクof数理の共同ブログ

こんにちは、よねすけです。
今回はフェルマーの小定理を二通りで証明したいと思います。

フェルマーの小定理とは、素数 $p$ と $\gcd(a,p)=1$ なる整数 $a$ を考えたとき、
$\begin{equation} a^{p-1}\equiv 1(mod\ p) \end{equation}$

証明には数学的帰納法を用いるものと群の性質を用いるものがあります。

数学的帰納法による証明

まずは

$n^p\equiv n(mod\ n)$
となることを $n$ に関する数学的帰納法で示しましょう。 $n=1$ の時は明らかなので、ある $n$ でこの式が成立するとしましょう。
このとき二項展開の公式を用いて、
$\displaystyle (n+1)^p\equiv \sum_{i=0}^{p}{}_pC_{i}n^i\equiv n^p+1+\sum_{i=1}^{p-1}{}_pC_{i}n^i(mod\ p)$
いま $1\leq i\leq p-1$ のとき、 ${}_pC_{i}$ は $p$ の倍数であることが知られています。なぜなら
$\displaystyle {}_pC_i=\frac{p!}{i!(p-i)!}$
と表されており、 $p!$ は $p$ の倍数である一方、 $i!,(p-i)!$ は $p$ の倍数で無いからです。以上より帰納法の仮定を用いれば
$(n+1)^p\equiv n^p+1\equiv n+1(mod\ p)$
となり $n+1$ の場合も成り立つことが示されました。
$n$ が $p$ の倍数でないとき、すなわち $\gcd(n,p)=1$ のときは両辺を $n$ で割って
$n^{p-1}\equiv 1(mod\ p)$
が示されました。

群の性質を用いるもの

組み換え定理を用います。 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ を考えるならば、 $a\in (\mathbb{Z}/p\mathbb{Z})^{\times}$ によって以下の２つの集合が対等であることが分かります。

$\{\overline{1},\overline{2},\cdots,\overline{p-1}\}=\{\overline{a},\overline{2a},\cdots,\overline{(p-1)a}\}$
これを用いれば
$(p-1)!\equiv a\times 2a\times\cdots\times (p-1)a\equiv a^{p-1}(p-1)!(mod\ p)$
$(p-1)!$ は $p$ の倍数でないので(ウィルソンの定理によると $(p-1)!\equiv -1(mod\ p)$ )、両辺を $(p-1)!$ で割ると
$a^{p-1}\equiv 1(mod\ p)$
が得られました。

どちらも簡潔な証明で素晴らしいですね。
それでは。