数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

フェルマーの小定理(Fermat's Little Theorem)


スポンサードリンク

フェルマーの小定理(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*}