漏れた素数：ユークリッドの証明 - 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$ がもっとも大きな素数であるという仮定に反する。
よって、背理法により「素数が有限個ではない」が証明された。

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

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

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

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

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

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

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

$1\cdot 2+1 = 3$

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

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

$1\cdot 2\cdot3 + 1 = 7$

より、 $7$ が素数として得られます。

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

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

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

作者: パウロリーベンボイム,Paulo Ribenboim,吾郷孝視
出版社/メーカー: 共立出版
発売日: 2003/08
メディア: 単行本
クリック: 1回
この商品を含むブログ (1件) を見る

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