読者です 読者をやめる 読者になる 読者になる

tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

漏れた素数:ユークリッドの証明

数学 自由研究 素数

《定理》
素数は無限に存在する

上の定理は、数学を詳しくない人にも良く知られた事実です。


証明をしたのは「ユークリッド」という古代アレクサンドリアの数学者です*1。こちらは、数学をかじった人には比較的よく知られていることです。


f:id:tsujimotter:20140725151521j:plain:w160
オックスフォード大学自然史博物館にあるユークリッドの像 (Wikipediaより引用)


ユークリッドの証明には背理法を用います。この証明は、非常に簡潔であることで有名です。

《ユークリッドの証明?》(この証明には一か所誤りがあります)
背理法を用いて証明する。すなわち、素数が有限個であると仮定する。

素数は有限個であるから、もっとも大きな素数が存在する。これを  P としよう。

 P より小さい自然数のすべてに対して積をとり、1を加えてこれを  P' とする。

 P' = 1\cdot 2\cdot 3\cdots P + 1

さてこの数  P' は、 1 から  P までのすべての自然数に対して割り切れない。したがって、 P' P より大きい素数である。これは  P がもっとも大きな素数であるという仮定に反する。

よって、背理法により「素数が有限個ではない」が証明された。

「素数は有限個ではない」ということは、当たり前ですが「素数は無限個存在する」ということです。


さて、《ユークリッドの証明?》を考えてみると1つの考えが浮かんできます。

素数を無限に生成する方法があるのではないか


素数を無限に生成する方法は知られていません*2から、これが見つかれば 大発見 です!


tsujimotter の考えた「すばらしい発明」は、つまりはこういうことです。


今知っている素数は  2 だけであると仮定します。

まず、 2 以下のすべての自然数に対して積をとって  1 を加えた数を、新たな素数とします。すなわち、

 1\cdot 2+1 = 3

より  3 が素数として得られます。

次に、新たに生成した素数(この場合は  3) 以下のすべての自然数に対して積をとって  1 を加えた数を、新たな素数とします。すなわち、

 1\cdot 2\cdot3 + 1 = 7
より、 7 が素数として得られます。


これを次々繰り返すことで、素数を無限に生成することができるはずです。
何せ《ユークリッドの証明?》にあるように、すべての素数の積をとって1を加えれば「新たな素数が生成される」のですから。


いやー、素晴らしい方法ですね。
「tsujimotter の素数生成術」とでも名付けましょうか。


このまま続けていくと、次のように無限に多くの素数列が生成されます。

 2, 3, 7, 5041, ...


ん?

ちょっとまてよ!

 5041 ってなんだ!?

 5041 = 71\cdot 71

となって、明らかに素数じゃないじゃないか!!!

なんてこったい!!!


でもおかしいですね。

「素数以下のすべての自然数の積に  1 を加えると、新たな素数が生成される」はずなのに。。。


何か間違っているのでしょうか。

(わからない人は、少し止まって考えてみましょう。)
 
 
 
 
 
 
 

種明かし

さて、茶番は終わりです。

何が間違っていたか、それは至ってシンプルです。


それは《ユークリッドの証明?》が間違っていたのです!


ばばーん!


世紀の大発見!ユークリッドの証明が間違っていた!!!


なんていうつもりはありません。笑


第一、ユークリッドの証明が間違っていたら「世紀の」大発見どころの騒ぎじゃないですからね。
ユークリッドは紀元前の人なわけですから…



…ここ、笑うところですよ?


さて、どこが間違いかというと、もちろん私の書いた《ユークリッドの証明?》が間違っているのです。


具体的には、この部分。

さてこの数  P' は、 1 から  P までのすべての自然数に対して割り切れない。したがって、 P' P より大きい素数である


正しくは、こうなります。

さてこの数  P' は、 1 から  P までのすべての自然数に対して割り切れない。したがって、 P' P より大きい素数であるか、 P より大きい素数  P'' が存在し  P'' で割り切れる


正しい《ユークリッドの証明》を書き下すとこうなります。

《ユークリッドの証明》
背理法を用いて証明する。すなわち、素数が有限個であると仮定する。

素数は有限個であるから、もっとも大きな素数が存在する。これを  P としよう。

 P より小さい自然数のすべてに対して積をとり、1を加えてこれを  P' とする。

 P' = 1\cdot 2\cdot 3\cdots P + 1

さてこの数  P' は、 1 から  P までのすべての自然数に対して割り切れない。したがって、 P' P より大きい素数であるか、 P より大きい素数  P'' が存在し  P'' で割り切れる。これは  P がもっとも大きな素数であるという仮定に反する。

よって、背理法により「素数が有限個ではない」が証明された。


具体的に数値で考えましょう。

 P = 7 とします。

 P より小さい自然数のすべてに対して積をとり、1を加えてこれを  P' を考えます。

 P' = 1\cdot 2\cdot 3 \cdots P + 1

この数  P' は、 1 から  P までのすべての自然数に対して割り切れません。

したがって、 P より大きい素数であるか、 P より大きい素数  P'' が存在し  P'' で割り切れます

 P' = 5041 = 71\cdot 71
より、たしかに  P' = 5041 は素数ではありません。
 P = 7 より大きく、 P' = 5041 より小さな素数  P'' = 71 で割り切れるからです。



 P より大きく、 P' より小さな素数  P''

この存在を忘れていました。


この  P'' こそ、 漏れた素数 だったわけです。


ここでわかったことは、《ユークリッドの証明》は背理法により「素数が無限にあること」を示しているが、具体的に素数を構成する「アルゴリズム」を示したものではない、という事実です。


いやはや、勘違いから始まった自由研究でしたが、非常に勉強になりました。

「tsujimotter の素数生成術」なんて名前つけなくて、ほんとによかった。笑
 
 

参考文献

1. 「オイラーによる素数生成多項式」についてまともに書かれた、私が知る限り唯一の本です。素数生成多項式に限らず、数論の幅広い分野を網羅しており、かつ、文章は魅力的に綴られています。かなり難しい本ですが、読む価値は十分すぎるほどあります。

我が数、我が友よ―数論への招待

我が数、我が友よ―数論への招待

2. 基本的には「数論」の本なのですが、この本は「暗号理論」や「楕円曲線」などの応用によった本です。脚注に書いたミラー・ラビン法も詳しく載っています。分厚い本ですが、なかなか丁寧に書いてくれているので、分野外でも比較的読みやすい本かと思います。「はじめての」といいつつ、内容は非常に濃いのでしっかり勉強したい人向けです。

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

 

《関連記事》
素数が無数にあることのオイラー積を使った証明 - tsujimotterのノートブック

 

*1:お恥ずかしながら、tsujimotterはアレクサンドリアのことをギリシャの都市だと思っておりました。場所的には現在のエジプトにあたるのですね。

*2:有限個の素数列を生成するオイラーの多項式(参考文献1)や確率的に素数を判定するミラー・ラビン法などは知られています。(参考文献2)