フェルマーの小定理

この記事の所要時間: 517

フェルマーの小定理(Fermat’s little theorem)

フェルマーといえば, 360年間もの間証明されなかったことで有名な「フェルマーの最終定理」があります.

まず, フェルマーの小定理の内容を紹介します.

素数 \(p\) と自然数 \(a\) が互いに素であるとき,

\begin{align*}
a^{p-1}\equiv 1 \pmod{p}
\end{align*}

が成り立つ.

つまり, \(a^{p-1}\) を \(p\) で割ると1余る, という意味です. (合同式についてはこちら).

証明

ここでは証明を3通り挙げておきます. 1つ目, 2つ目の方が分かりやすいですが, 3つ目の方法はこの定理の一般化であるオイラーの定理の証明に応用がききます. 1, 2つ目の方法は \(a^p\equiv a\) を示す方法です.

証明Ⅰ.

\(a\) と \(p\) が互いに素という条件があるので, 合同式の性質から,

\begin{align*}
a^{p-1}\equiv 1\Leftrightarrow a^p\equiv a
\end{align*}

よって, \(a^p\equiv a\) を示すことにします.

まず自然数 \(m\) について

\begin{align*}
(m+1)^p\equiv m^p+1
\end{align*}

が成り立つことを示します.

\(p\) が素数なので \({}_pC_1, {}_pC_2, \ldots, {}_pC_{p-1}\) が \(p\) で割り切れることを用いて, \((m+1)^p\) を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*}

となります.

後はこれを使って \(a\) についての数学的帰納法で示します.

[1] \(a=1\)のとき

\(a^p=a=1\)より明らか.

[2] \(a=k\) のとき成り立つ, つまり\(k^p\equiv k\) を仮定すると,

\begin{align*}
(k+1)^p &\equiv k^p+1\\
&\equiv k+1
\end{align*}

となり, \(a=k+1\)のときも成り立つ.

[1], [2]より任意の自然数 \(a\) に対して \(a^p\equiv a\) が成り立ち, 特に \(a\) と \(p\) が互いに素のとき \(a^{p-1}\equiv 1\).

証明Ⅱ.

証明Ⅰ. 同様に, \(a^p\equiv a\) を示します. 証明Ⅰと雰囲気は似ています.

\(a=1+1+\cdots+1\)(\(1\) を \(a\) 個足したものと考える)

なので,

\[a^p=(1+1+\cdots+1)^p\]

を多項定理により展開することを考えます. 展開した各項は,

\[\frac{p!}{q_1!q_2!\cdots q_a!}\]

但し\(q_1+q_2+\cdots+q_a=p\).

となりますが, \(p\) は素数なので, \(q_1, q_2, \ldots, q_a\) のうち1つが \(p\) で残りがすべて \(0\) の場合を除いて, この値は \(p\) の倍数です. 一方, 1つが \(p\) で残りが \(0\) のときは \(1\) になります. よって,

\begin{align*}
a^p &= (1+1+\cdots+1)^p\\
&\equiv 1+1+\cdots+1\\
&\equiv a
\end{align*}

となり示されました.

証明Ⅰにおいて, コンビネーション \({}_pC_{k}\) が \(k=1,2,\ldots,p-1\) に対して \(p\) の倍数になることを使いましたが, それと同じような考え方をしています.

証明Ⅲ.

(補題1). \(a, 2a, \ldots, (p-1)a\) を \(p\) で割った余りはすべて異なる.

(証明)割った余りの同じものが存在すると仮定すると, \(1\leqq\alpha<\beta\leqq p-1\) を満たす \(\alpha, \beta\) で \(\alpha a\equiv \beta a\).

ところで \(a\)と\(p\) は互いに素なので \(\alpha\equiv \beta\) となるが,

\(1\leqq\alpha<\beta\leqq p-1\) かつ \(\alpha\equiv \beta\) を満たす \(\alpha, \beta\) は存在しない.

\(a, 2a, \ldots, (p-1)a\) がすべて \(p\) と互いに素であることと(補題1)の内容から,

\(a, 2a, \ldots, (p-1)a\) を \(p\) で割った余りは \(1, 2, \ldots, p-1\) と1対1対応することになるので, それらの積を \(p\) で割った余りは等しくなります.

\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*}

\(p\) は素数なので \((p-1)!\) は \(p\) と互いに素であるから,

\begin{align*}
a^{p-1}\equiv 1
\end{align*}

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください