偉大な数学者ユークリッドによる、シンプルで美しい数学的証明。
数学にあまりなじみが深くない人にもわかりやすく紹介します。
素数とは、「１と自分自身でしか割り切れない自然数」のことをいう。
（たとえば ２、３、５、７、11、… など。）
逆に素数以外の２以上の自然数は「合成数」というが、実はすべての合成数は素数同士の掛け算によってできている。
24 ＝ 2×2×2×3
365 = 5×73
1000 ＝ 2×2×2×5×5×5
といった具合。
いわゆる「素因数分解」というやつだ。
まさに「素（もと）の数」というだけあって、素数はあらゆる自然数の構成材料になるスペシャルな数字なのである。
そしてこの素数、実は無限に存在することが分かっている。
ユークリッドによる美しい証明
「素数は無限に存在する」
と言われて、すぐに納得できるでしょうか。
直感的に、
「数字が無限に大きくなるんだから、素数も探せば無限に見つかるでしょ」
とは思うかもしれない。
ただそれを論理的に証明してくれと言われたら困ってしまう。
なにしろ「無限」という壮大なテーマを相手にしなければならない。
この証明を最初に成し遂げた男こそ、古代エジプトの数学者ユークリッドであった。
なんと今から約2300年も昔、紀元前３世紀ごろの功績である。
〈出典:wikipedia〉
彼の残した証明はおおむね次のとおり。
素数の個数は有限だと仮定する。
すべての素数を並べて、\(p{\tiny 1} , p{\tiny 2} , p{\tiny 3} , … , p{\tiny n}\) とおいたとき、
\(N=(p{\tiny 1} × p{\tiny 2} × p{\tiny 3} × … × p{\tiny n}) + 1\) となるような自然数\(N\)を考える。
\(N\)は \(p{\tiny 1} , p{\tiny 2} , p{\tiny 3} , … , p{\tiny n}\) のいずれでも割り切れないため、素数といえるはずだが、そうすると当初すべての素数として並べた以外の新たな素数が得られたことになるので、矛盾である。
よって仮定は誤っており、素数は無限に存在する。
数学の証明というと、なにやら難解な数式を書きつらねるようなイメージがあるが、ユークリッドが残したこの証明は非常にシンプルで美しい。
そして2300年の時を超えて現代の私たちが見ても、ちゃんと理解することができる。
「数学というのは時代にとらわれない普遍的な学問なんだなあ」
としみじみ感じてしまうのである。
しかし、上記の証明を一度パッと見ただけでは、いまひとつピンとこない人も少なくないと思う。
少なくとも文系出身の筆者はそうだった。
以下では、ユークリッドの証明をもう少し詳しく、できるだけやさしく解説していきます。
「背理法」という考え方
ユークリッドの証明は、「背理法」と呼ばれる論法を用いている。
① 命題を否定するような仮説を立てる
② 仮説が正しいとすると矛盾が生じることを指摘する
③ 仮説は誤りなので、間接的にもとの命題が正しいことが証明できる
といった手順をふむ証明の方法のことである。
背理法の考え方は、よく事件捜査におけるアリバイの調査に例えられる。
今、事件の容疑者となった友人A君の無実を証明したいとしよう。
一生懸命 A君の純粋さ・誠実さを語ったところで、それはなかなか無実の証明にはならない。
ここで思い切って、
① まずA君を犯人だと仮定する
② 犯行時刻にA君は別の場所にいたなど、アリバイ（＝矛盾点）を指摘する
③ 仮定は誤っており、A君は無実であると証明できる
という段取りで考えれば、スッキリ明快に証明ができてしまう。
背理法は時として大変便利な論法なのである。
ユークリッドの証明を追ってみよう
背理法をふまえて、あらためてユークリッドの証明を考えてみる。
素数の個数は有限だと仮定する。
すべての素数を並べて、\(p{\tiny 1} , p{\tiny 2} , p{\tiny 3} , … , p{\tiny n}\) とおいたとき、
\(N=(p{\tiny 1} × p{\tiny 2} × p{\tiny 3} × … × p{\tiny n}) + 1\) となるような自然数\(N\)を考える。
\(N\)は \(p{\tiny 1} , p{\tiny 2} , p{\tiny 3} , … , p{\tiny n}\) のいずれでも割り切れないため、素数といえるはずだが、そうすると当初すべての素数として並べた以外の新たな素数が得られたことになるので、矛盾である。
よって仮定は誤っており、素数は無限に存在する。
ここでも、まず冒頭で「素数の個数は有限」として、証明したいこととは反対の仮説を立てている。
あとはこの仮説について矛盾を指摘することで、「素数は無限にある」と証明できる。
ユークリッドの証明で「矛盾である」と言っているのは、いったいどんなことだろうか。
分かりやすくするために単純化してみる
たとえば、この世に素数が
２、３、５、７、11
の５つしかないとしてみよう。
証明の手順にしたがって、
\(N=(2×3×5×7×11)+1=2311\)という数を考える。
ここで、\(N\) を ２、３、５、７、11 いずれの素数で割ろうとしても、カッコの中は割り切れるものの、＋１の部分が必ず余りとして残ってしまうことがわかる。
この世のすべての素数で割り切れないということは、素数の掛け算でできている合成数によっても当然割り切れない。
しかし一方で、\(N\) は「１および\(N\)（=2311）それ自身でなら割り切れる」ことも明らかである。ということは、定義からして\(N\) は素数だといえる。
素数は２、３、５、７、11 の５つしかないはずの世界に、なんと2311という新しい素数が登場しまった。
素数がいくつあっても同じこと
たとえば素数がちょうど100個ある世界を考えても、構造は同様である。
\(N=(p{\tiny 1} × p{\tiny 2} × p{\tiny 3} × … × p{\tiny 100}) + 1\) を100通りのどの素数によっても割り切れない（１余る）ので、やはり\(N\) 自身が101番目の新たな素数となってしまう。結局素数をいくつに設定しようが、素数が有限個だと想定している限り、つまり \(N=(p{\tiny 1} × p{\tiny 2} × p{\tiny 3} × … × p{\tiny n}) + 1\) と表せる限りは、必ず最初のリストにない新しい素数を生み出してしまうことになるのだ。
仮説では素数が有限個であるはずなのに「すべての素数」を定められない。
ユークリッドはこのことを「矛盾である」と指摘しているのである。
よってめでたく「素数の個数は有限である」との仮説は棄却され、「素数は無限に存在する」ことが証明された。
実際のところ、自然数Nは素数とは限らない
筆者がユークリッドの証明に初めて触れたときは、
「なるほど、じゃあ素数を適当にいくつか順にかけていって１を足したら必ず素数になるってこと？」
などと思ってしまったのだが、実はそうではない。
実際に、たとえば \((2×3×5×7×11×13)+1=30031\) は素数ではなく合成数だ。「２、３、５、７、11、13 のどれでも割り切れないんだから素数じゃないの？」
と思うかもしれないが、いやいや現実世界では、素数はこの６つだけではない。
\(30031=59×509\) と表せるとおり、59という素数、509という素数によってバッチリ割り切れてしまう。 ユークリッドの証明において \(N=(p{\tiny 1} × p{\tiny 2} × p{\tiny 3} × … × p{\tiny n}) + 1\) が素数になるといえるのは、「\(p{\tiny 1}\)～\(p{\tiny n}\) が素数のすべてだ」という、事実と異なる前提があるからこそなのである。そう聞いてもなんとなく不思議な感じがしてしまうのは、論理のトリックともいうべきだろうか。
そうした不思議な感覚も含めて、数学の面白さを感じられるところだと思う。
□古代の数学者ユークリッドは、素数が無限に存在することを記録上初めて証明した。
・背理法を用いた、シンプルで美しい証明
コメント