フェルマーの小定理(Fermat's little theorem)
フェルマーといえば, 360年間もの間証明されなかったことで有名な「フェルマーの最終定理」があります.
まず, フェルマーの小定理の内容を紹介します.
つまり, を で割ると1余る, という意味です. (合同式についてはこちら).
証明
ここでは証明を3通り挙げておきます. 1つ目, 2つ目の方が分かりやすいですが, 3つ目の方法はこの定理の一般化であるオイラーの定理の証明に応用がききます. 1, 2つ目の方法は を示す方法です.
証明Ⅰ.
と が互いに素という条件があるので, 合同式の性質から,\begin{align*}
a^{p-1}\equiv 1\Leftrightarrow a^p\equiv a
\end{align*}
よって, を示すことにします.
まず自然数 について
\begin{align*}
(m+1)^p\equiv m^p+1
\end{align*}
が成り立つことを示します.
が素数なので が で割り切れることを用いて, を2項展開して合同変換すると,
\begin{align*}
(m+1)^p &= \sum_{k=0}^p {}_pC_k\cdot m^k\\
&\equiv {}_pC_0\cdot m^0+{}_pC_p\cdot m^p\\
&\equiv m^p+1
\end{align*}
となります.
後はこれを使って についての数学的帰納法で示します.
[1] のとき
より明らか.
[2] のとき成り立つ, つまり を仮定すると,
\begin{align*}
(k+1)^p &\equiv k^p+1\\
&\equiv k+1
\end{align*}
となり, のときも成り立つ.
[1], [2]より任意の自然数 に対して が成り立ち, 特に と が互いに素のとき .
証明Ⅱ.
証明Ⅰ. 同様に, を示します. 証明Ⅰと雰囲気は似ています.( を 個足したものと考える)
なので,
を多項定理により展開することを考えます. 展開した各項は,
但し.
となりますが, は素数なので, のうち1つが で残りがすべて の場合を除いて, この値は の倍数です. 一方, 1つが で残りが のときは になります. よって,
\begin{align*}
a^p &= (1+1+\cdots+1)^p\\
&\equiv 1+1+\cdots+1\\
&\equiv a
\end{align*}
となり示されました.
証明Ⅰにおいて, コンビネーション が に対して の倍数になることを使いましたが, それと同じような考え方をしています.
証明Ⅲ.
(補題1). を で割った余りはすべて異なる.
(証明)割った余りの同じものが存在すると仮定すると, を満たす で .ところで と は互いに素なので となるが,
かつ を満たす は存在しない.
がすべて と互いに素であることと(補題1)の内容から,
を で割った余りは と1対1対応することになるので, それらの積を で割った余りは等しくなります.
\begin{align*}
a\cdot 2a\cdots(p-1)a\equiv1\cdot2\cdots(p-1)
\end{align*}
\begin{align*}
(p-1)!a^{p-1}\equiv(p-1)!
\end{align*}
は素数なので は と互いに素であるから,
\begin{align*}
a^{p-1}\equiv 1
\end{align*}