L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~

フェルマーの小定理の証明

【命題】

pを素数、aをpで割り切れない整数とする。
このとき、
$$a^{p-1}\,\equiv\,1\quad(mod\;p)$$

が成り立つ。

【メモ1】

・ 以下、ˆはべき乗(冪乗)記号とし、例えばaˆ(p-1)はaを(p-1)回掛けることを表わす。
・  ≡ (mod p)は合同式といい、左辺と右辺をpで割った余りが等しいことを表わす。
・ 上記の式は、つまり、aを(p-1)回掛けた数をpで割ると余りが1になることを示す。
例えば、p=7,a=3とすると、
3ˆ(7-1)=3ˆ(6)=729=7×104+1
・ まずフェルマーの小定理が成り立つこと自体が興味深いが、
数の持つどのような仕組みがフェルマーの小定理を成立させているのか、そこがさらに興味深い。
このページでは、群論の考え方をベースにして、未修者でも分かるように群論を用いずに証明を行なった。
興味を感じたら群論などを学ぶと良い。

【メモ2】

以下は、合同式に不慣れな場合の参考に。
・ 合同式1
合同式の演算について、nを自然数とすると、
a≡b (mod n) ⇒ ac≡bc  (mod n)
である。
なぜなら、nでa,bを割ると、
a=qn+r, b=q'n+r
と同じ余りrであり、cを掛けると、
ac=qnc+rc, bc=q'nc+rc
qncとq’ncはnで割り切れるので、
ac,bcのnで割った余りは、共にrcをnで割った余りとなり、等しい。
・ 合同式2
次に、nとcが互いに素な場合には、、
ちなみに、互いに素とは、nとcが同じ素因数を持たない場合のことである。
a≡b (mod n) ⇐ ac≡bc  (mod n)
である。
なぜなら、nでac,bcを割ると、
ac=qn+r, bc=q'n+r
と同じ余りrであり、
ac−bc=qn−q'n
(a−b)c=(q−q')n

nとcが互いに素なので、(q−q’)をcは割り切れる。
したがって、
a−b=kn, k=(q−q')/c
をみたすkがあり、
a=qn+rならば、b+kn=qn+rであり、
b=(q+k)n+rとなり、a≡b (mod n)となる。

【証明】

べき乗の巡回

pによる余りは1,2,〜,p-2,p-1のいずれかしかない。
aにaを掛けて余りをとる操作Tを繰り返し行うと、
p-1以下ですでに現われた余りが再び現れる。
そうでなければ、1,2,〜,p-2,p-1以外の余りがあることになり矛盾するからである。
操作Tの繰り返しによって作られる数列は初期値によって決まるので、
すでに現われた余りが再び現れると、それ以降は同じ数列の繰り返しとなる。
したがって、繰り返しの最も小さな周期tと、あるiがあって、
aˆ(i)≡aˆ(i)・aˆ(t) (mod p)
となる。
aとpは互いに素なので、aˆ(i)とpも互いに素で、
aˆ(t)≡1 (mod p)
となる。

周期tはp-1の約数

次に、pによる余り1,2,〜,p-2,p-1をPとし、
a,aˆ(2),〜,aˆ(t-1),aˆ(t)のpによる余りをAとする。
Aはpによる余りの数なのでPに含まれる。
A以外にPの数があれば、それをbとし、Aの各数にbを掛けた数、
a・b,aˆ(2)・b,〜,aˆ(t-1)・b,aˆ(t)・bのpによる余りをBとする。
仮に、AとBに共通の数があったとすると、
aˆ(i)≡aˆ(j)・b (mod p)
をみたすi,jがあり、aˆ(i),aˆ(j)はpと互いに素なので、
j-i≥0のときは、k=j-iとし、j-i<0のときは、k=t+j-iとすると、
aˆ(k)≡b (mod p), 0≤k≤t-1
となり、bがAに含まれるので矛盾する。
したがって、AとBに共通の数はない。
さらに、仮に、a・b,aˆ(2)・b,〜,aˆ(t-1)・b,aˆ(t)・bに同じ数があったとすると、
aˆ(i)・b≡aˆ(j)・b (mod p), i≠j, 1≤i,j≤t
をみたすi,jがあり、aˆ(i),aˆ(j),bはpと互いに素なので、
j-i>0のときは、k=j-iとし、j-i<0のときは、k=t+j-iとすると、
aˆ(k)≡1 (mod p), 1≤k≤t-1
となり、k<tなるkもaの操作Tによる周期になってしまい、
tがaの操作Tの繰り返しにより1に戻る最も小さな数であることに矛盾する。
したがって、a・b,aˆ(2)・b,〜,aˆ(t-1)・b,aˆ(t)・bに同じ数はない。
そうすると、AとBは同じ個数で、同じ数がないことが分かった。
つまり、A以外にPの数があると、このようなBが取れる。

同様にして、A,B以外にPの数があれば、それをcとし、Aの各数にcを掛けた数、
a・c,aˆ(2)・c,〜,aˆ(t-1)・c,aˆ(t)・cのpによる余りをCとすると、
CはAと同じ個数で、同じ数がないことは分かっている。
仮に、CとBに共通の数があったとすると、
aˆ(i)・b≡aˆ(j)・c (mod p)
をみたすi,jがあり、aˆ(i),aˆ(j)はpと互いに素なので、
j-i≥0のときは、k=j-iとし、j-i<0のときは、k=t+j-iとすると、
aˆ(k)・b≡c (mod p), 0≤k≤t-1
となり、cがBに含まれるので矛盾する。
したがって、CとBに共通の数はない。
そうすると、AとBとCは同じ個数で、同じ数がないことが分かった。
つまり、AとB以外にPの数があると、このようなCが取れる。
同様にして、Pに残りの数がある限り、D,E,F,〜を取っていくと、
Pは有限個なので、この操作は有限回しかできない。
これらの数の集まりの個数はすべてAと同じ個数なので、
p-1個を同じ個数で分けることになり、Aの個数tはp-1の約数であることが分かる。

結論

したがって、
p-1=kt, 1≤k≤p-1
をみたすkがあり、
aˆ(p-1)≡aˆ(tk)≡(aˆ(t))ˆ(k)≡(1)ˆ(k)≡1 (mod p)
aˆ(p-1)≡1 (mod p)
となる。 □

公開日:2017/5/5
修正日:2017/8/9 【メモ1】「このページでは、群論の考え方をベースにして、未修者でも分かるように群論を用いずに証明を行なった。」を追加
最終修正日:2017/8/9