フェルマーの小定理

この記事の所要時間: 513

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

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

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

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

(1) \begin{equation*} a^{p-1}\equiv 1 \pmod{p} \end{equation*}

が成り立つ.

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

証明

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

証明Ⅰ.

apが互いに素という条件があるので, 合同式の性質から,

(2) \begin{equation*} a^{p-1}\equiv 1\Leftrightarrow a^p\equiv a \end{equation*}

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

まず自然数mについて

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

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

pが素数なので{}_pC_1, {}_pC_2, \ldots, {}_pC_{p-1}pで割り切れることを用いて, (m+1)^pを2項展開して合同変換すると,

(4) \begin{eqnarray*} (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{eqnarray*}

となります.

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

[1] a=1のとき

a^p=a=1より明らか.

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

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

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

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

証明Ⅱ.

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

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

なので,

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

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

\displaystyle \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になります. よって,

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

となり示されました.

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

証明Ⅲ.

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

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

ところでapは互いに素なので\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)apで割った余りは1, 2, \ldots, p-1と1対1対応することになるので, それらの積をpで割った余りは等しくなります.

(7) \begin{equation*} a\cdot 2a\cdots(p-1)a\equiv1\cdot2\cdots(p-1) \end{equation*}

(8) \begin{equation*} (p-1)!a^{p-1}\equiv(p-1)! \end{equation*}

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

(9) \begin{equation*} a^{p-1}\equiv 1 \end{equation*}

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

コメントをどうぞ

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