フェルマーの小定理の証明
【命題】
ｐを素数、ａをｐで割り切れない整数とする。
このとき、
$$a^{p-1}\,\equiv\,1\quad(mod\;p)$$
が成り立つ。
【メモ1】
・ 以下、ˆはべき乗（冪乗）記号とし、例えばａˆ(ｐ-1)はａを(ｐ-1)回掛けることを表わす。
・ ≡ (mod ｐ)は合同式といい、左辺と右辺をｐで割った余りが等しいことを表わす。
・ 上記の式は、つまり、ａを(ｐ-1)回掛けた数をｐで割ると余りが1になることを示す。
例えば、ｐ＝7,ａ＝3とすると、
3ˆ(7-1)＝3ˆ(6)＝729＝7×104+1
・ まずフェルマーの小定理が成り立つこと自体が興味深いが、
数の持つどのような仕組みがフェルマーの小定理を成立させているのか、そこがさらに興味深い。
このページでは、群論の考え方をベースにして、未修者でも分かるように群論を用いずに証明を行なった。
興味を感じたら群論などを学ぶと良い。
【メモ2】
以下は、合同式に不慣れな場合の参考に。
・ 合同式1
合同式の演算について、ｎを自然数とすると、
ａ≡ｂ (mod ｎ) ⇒ ａｃ≡ｂｃ (mod ｎ)
である。
なぜなら、ｎでａ,ｂを割ると、
ａ＝ｑｎ＋ｒ, ｂ＝ｑ'ｎ＋ｒ
と同じ余りｒであり、ｃを掛けると、
ａｃ＝ｑｎｃ＋ｒｃ, ｂｃ＝ｑ'ｎｃ＋ｒｃ
ｑｎｃとｑ’ｎｃはｎで割り切れるので、
ａｃ,ｂｃのｎで割った余りは、共にｒｃをｎで割った余りとなり、等しい。
・ 合同式2
次に、ｎとｃが互いに素な場合には、、
ちなみに、互いに素とは、ｎとｃが同じ素因数を持たない場合のことである。
ａ≡ｂ (mod ｎ) ⇐ ａｃ≡ｂｃ (mod ｎ)
である。
なぜなら、ｎでａｃ,ｂｃを割ると、
ａｃ＝ｑｎ＋ｒ, ｂｃ＝ｑ'ｎ＋ｒ
と同じ余りｒであり、
ａｃ−ｂｃ＝ｑｎ−ｑ'ｎ
(ａ−ｂ)ｃ＝(ｑ−ｑ')ｎ
ｎとｃが互いに素なので、(ｑ−ｑ’)をｃは割り切れる。
したがって、
ａ−ｂ＝ｋｎ, ｋ＝(ｑ−ｑ')/ｃ
をみたすｋがあり、
ａ＝ｑｎ＋ｒならば、ｂ＋ｋｎ＝ｑｎ＋ｒであり、
ｂ＝(ｑ＋ｋ)ｎ＋ｒとなり、ａ≡ｂ (mod ｎ)となる。
【証明】
べき乗の巡回
ｐによる余りは1,2,〜,ｐ-2,ｐ-1のいずれかしかない。
ａにａを掛けて余りをとる操作Ｔを繰り返し行うと、
ｐ-1以下ですでに現われた余りが再び現れる。
そうでなければ、1,2,〜,ｐ-2,ｐ-1以外の余りがあることになり矛盾するからである。
操作Ｔの繰り返しによって作られる数列は初期値によって決まるので、
すでに現われた余りが再び現れると、それ以降は同じ数列の繰り返しとなる。
したがって、繰り返しの最も小さな周期ｔと、あるｉがあって、
ａˆ(i)≡ａˆ(i)・ａˆ(ｔ) (mod ｐ)
となる。
ａとｐは互いに素なので、ａˆ(i)とｐも互いに素で、
ａˆ(ｔ)≡1 (mod ｐ)
となる。
周期ｔはｐ-1の約数
次に、ｐによる余り1,2,〜,ｐ-2,ｐ-1をＰとし、
ａ,ａˆ(2),〜,ａˆ(t-1),ａˆ(t)のｐによる余りをＡとする。
Ａはｐによる余りの数なのでＰに含まれる。
Ａ以外にＰの数があれば、それをｂとし、Ａの各数にｂを掛けた数、
ａ・ｂ,ａˆ(2)・ｂ,〜,ａˆ(t-1)・ｂ,ａˆ(t)・ｂのｐによる余りをＢとする。
仮に、ＡとＢに共通の数があったとすると、
ａˆ(i)≡ａˆ(j)・ｂ (mod ｐ)
をみたすi,jがあり、ａˆ(i),ａˆ(j)はｐと互いに素なので、
j-i≥0のときは、k=j-iとし、j-i＜0のときは、k=t+j-iとすると、
ａˆ(k)≡ｂ (mod ｐ), 0≤ｋ≤ｔ-1
となり、ｂがＡに含まれるので矛盾する。
したがって、ＡとＢに共通の数はない。
さらに、仮に、ａ・ｂ,ａˆ(2)・ｂ,〜,ａˆ(t-1)・ｂ,ａˆ(t)・ｂに同じ数があったとすると、
ａˆ(i)・ｂ≡ａˆ(j)・ｂ (mod ｐ), ｉ≠ｊ, 1≤ｉ,ｊ≤ｔ
をみたすi,jがあり、ａˆ(i),ａˆ(j),ｂはｐと互いに素なので、
j-i>0のときは、k=j-iとし、j-i＜0のときは、k=t+j-iとすると、
ａˆ(k)≡1 (mod ｐ), 1≤ｋ≤ｔ-1
となり、ｋ<ｔなるｋもａの操作Ｔによる周期になってしまい、
ｔがａの操作Ｔの繰り返しにより1に戻る最も小さな数であることに矛盾する。
したがって、ａ・ｂ,ａˆ(2)・ｂ,〜,ａˆ(t-1)・ｂ,ａˆ(t)・ｂに同じ数はない。
そうすると、ＡとＢは同じ個数で、同じ数がないことが分かった。
つまり、Ａ以外にＰの数があると、このようなＢが取れる。
同様にして、Ａ,Ｂ以外にＰの数があれば、それをｃとし、Ａの各数にｃを掛けた数、
ａ・ｃ,ａˆ(2)・ｃ,〜,ａˆ(t-1)・ｃ,ａˆ(t)・ｃのｐによる余りをＣとすると、
ＣはＡと同じ個数で、同じ数がないことは分かっている。
仮に、ＣとＢに共通の数があったとすると、
ａˆ(i)・ｂ≡ａˆ(j)・ｃ (mod ｐ)
をみたすi,jがあり、ａˆ(i),ａˆ(j)はｐと互いに素なので、
j-i≥0のときは、k=j-iとし、j-i＜0のときは、k=t+j-iとすると、
ａˆ(k)・ｂ≡ｃ (mod ｐ), 0≤ｋ≤ｔ-1
となり、ｃがＢに含まれるので矛盾する。
したがって、ＣとＢに共通の数はない。
そうすると、ＡとＢとＣは同じ個数で、同じ数がないことが分かった。
つまり、ＡとＢ以外にＰの数があると、このようなＣが取れる。
同様にして、Ｐに残りの数がある限り、Ｄ,Ｅ,Ｆ,〜を取っていくと、
Ｐは有限個なので、この操作は有限回しかできない。
これらの数の集まりの個数はすべてＡと同じ個数なので、
ｐ-1個を同じ個数で分けることになり、Ａの個数ｔはｐ-1の約数であることが分かる。
結論
したがって、
ｐ-1＝ｋｔ, 1≤ｋ≤ｐ-1
をみたすｋがあり、
ａˆ(p-1)≡ａˆ(tk)≡(ａˆ(t))ˆ(k)≡(1)ˆ(k)≡1 (mod ｐ)
ａˆ(p-1)≡1 (mod ｐ)
となる。 □
公開日：2017/5/5
修正日：2017/8/9 【メモ1】「このページでは、群論の考え方をベースにして、未修者でも分かるように群論を用いずに証明を行なった。」を追加
最終修正日：2017/8/9