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

【命題】

pを素数、aをpで割り切れない整数とする。
このとき、
aˆ(p-1)≡1 (mod 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/5/5

素数が無限にあることの証明

【証明】
すべての素数をXとする。Xの個数は有限又は無限である。
仮に有限しかないとすると、それらすべてを掛け合わせることができ、
掛け合わせた数をxとすると、xも有限である。
x+1は少なくとも一つの素数で割られる(後で証明する)ので、その素数をpとする。
Xのどの素数もx+1を割ることはできないので、pはXにはない。
これはXがすべての素数であることに反する。
したがって、素数は無数にある。 □

自然数nは少なくとも一つの素数で割られることの証明

nが素数の場合には、nで割ればよい。
以下、nは素数でないとする。

【メモ】
ちなみに、自然数とは1以上の整数である。
素数とは自然数nでnと1以外には割られない数である。
aがbで割られること、a=bcであること、bがaの約数であることは同値である。

【証明1】
自然数nは一意に素因数分解されるので、少なくとも一つの素数で割られる。 □

【メモ】
自然数nが一意に素因数分解されることは、算術の基本定理と呼ばれる。
素因数分解とは、自然数nと等しい素数の積を見つけることである。
一意というのは、そのような素数の組が一つに定まるということである。
よく考えると、【証明】では一意であることや素因数分解されることは使っていない。
したがって、次の証明が考えられる。

【証明2】
自然数nが一意に素因数分解されることを用いない。
自然数nにnと1以外の約数があれば、その約数xを一つ取り、同様の操作Tを繰り返す。
操作Tの対象となる約数は、前操作の約数よりも小さくなる。
自然数は下に有限なため、一連の操作はxと1以外に約数のない数を取って終了する。
そのようなxは素数であり、pとする。

次に、自然数nの約数をm、mの約数をlとすると、
n=km、m=k’lより、n=(kk’)lとなり、
lはnの約数となる。
つまり、自然数nの約数の約数は、nの約数でもある。

操作Tは、自然数nの約数を取る操作であったので、
操作Tの繰り返しで取られた素数pもnの約数である。
したがって、自然数nは少なくとも一つの素数pで割られる。 □

【証明】の論理構造の考察

【証明】の論理構造を考察すると、その骨格は、
命題A「すべての素数は有限である」という仮定の下で、
命題B「すべての素数をXとする」⇒命題¬B「Xはすべての素数でない」という矛盾を導き出している。
つまり、A⇒(B⇒¬B)である。
そして、すべての素数は有限でないから無限であると結論する。
では、すべての素数が無限であれば、有限の場合と同じ操作を行っても矛盾は生じないのだろうか?
もしも、矛盾があったとしたらどうなるのか?

まず、命題C「すべての素数は有限又は無限である」について考える。
無限を「大きすぎて考えられない数」と捉えれば、有限は「大きくなくて考えられる数」であり、
つまり、すべての素数は「考えられる個数」又は「考えられない個数」かであると主張している。
では、「考えられる」とは何か、それは「全体をXと対象化したり」「全体Xから一部を取り出したり」「すべてを掛け合わせたり」「+1などの四則演算をする」ことなどである。

無限はどの操作ができてどの操作ができないのか。少なくとも無限とは「命題がその数を含むと、命題が真偽不明になる、つまり命題でなくなる場合のある数」と言える。そこで大切なのは、無限を含むどのような命題が真偽不明になるのかを明確にすることである。さらに言えば、命題を伴わない有限・無限という枠組みを一度捨てて、そのような各命題によって相対的に有限・無限を定義したり、分類したりすることもできるだろう。

今回で言えば、命題D「すべての素数は無限個である」は真としているが、命題E「無限個の素数をすべて掛け合わせた数がある」や命題F「無限個の素数をすべて掛け合わせた数+1という数がある」は命題として扱っていない。
では仮に、命題として扱い矛盾が生じたらどうなるか。命題Cは有限又は無限のどちらでも矛盾するので、命題C自身が矛盾することになり、すべての素数が有限又は無限でない何かであることを示すか、さもなければ「すべての素数を対象化すること」が矛盾を抱えるので、すべての素数をまとめて扱う議論は大きな制約を受ける。
そこで、命題EFを真偽不明として、命題としては扱わずに切り捨てれば矛盾も生じず、命題Cを前提として命題Dが真となる主張が保たれ、素数をまとめて扱う議論が可能となる。つまり、「全体をXと対象化したり」「全体Xから一部を取り出したり」するのを可とし、「すべてを掛け合わせたり」「+1などの四則演算をする」のは不可とするのである。

ただ、命題EFを切り捨てると不完全になる。
そこで、直観的な観点から、
「無限個の1以上の数を足したり、掛け合わせれば無限になる」
「無限の四則演算を「∞=∞+n,∞=∞×n(1≤n)」とする」
これらの命題を前提とすれば、
x=∞、x+1=∞で、
「x+1は少なくとも一つの素数で割られる」は、x+1=∞=∞×pで真であり、
「Xのどの素数もx+1を割ることができる」ことになり、
pがすべての素数Xに入っていても矛盾を生じない。
つまり、すべての素数が無限であれば、有限の場合と同じ操作を行っても矛盾を生じなくなる。

ちなみに、「すべての素数」を対象化することなく、数学的帰納法によって素数が無限にあることを証明できる。
参照:背理法被害者の会「素数の無限性」
この場合は、「すべての素数は有限又は無限である。」という仮定も必要ない。
数学的帰納法から上記の仮定を証明(数学的帰納法は途中で終わるか終わらないかのどちらか)することができるし、おそらく、数学的帰納法を認めることと、加算無限集合の対象化とは同値なのだと思う。

公開日:2017/4/19
修正日:2017/5/5、【メモ】4行目「素因数分解されること」を追加
修正日:2017/5/15、【証明】「すると、すべての素数をXとして、それらを」⇒「すると、すべての素数をXとできる。それらを」
【証明】「どの素数についてもx+1は割られないので」⇒「どの素数もx+1を割ることはできないので」
【証明2】「素数pはnの約数」⇒「素数pもnの約数」
修正日:2017/5/19、最後尾に「【証明】の論理構造の考察」を追加
【証明】を有限だと矛盾を生み、無限だと矛盾が回避される論理構造が明確になるように修正
修正日:2017/5/20、「【証明】の論理構造の考察」の1段落目後半に「では、すべての素数が無限であれば、同じ操作を行っても矛盾は生じないのだろうか?もしも、矛盾があったとしたらどうなるのか?」を追加
2段落目を「ことなどである。(改行)無限はどの操作ができてどの操作ができないのか。」で段落分け
3段落目「は真偽不明であり、命題として扱っていない。」⇒「は命題として扱っていない。」
3段落目「そこで、命題EFを命題として扱わずに切り捨てれば矛盾も生じず、」⇒「命題EFを真偽不明として、命題としては扱わずに切り捨てれば矛盾も生じず、」
修正日:2017/5/30、最後尾に数学的帰納法による証明のリンクを追加
最終修正日:2017/5/30