読者です 読者をやめる 読者になる 読者になる

オタクof数理の共同ブログ

京大情報学科数理工学コースの学生4人による共同ブログです

フェルマーの小定理の証明

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

フェルマーの小定理とは、素数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の場合も成り立つことが示されました。
npの倍数でないとき、すなわち\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}によって以下の2つの集合が対等であることが分かります。

\{\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)

が得られました。

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