素数が無限にあることの証明（中学生向け）

　周りで見かける証明が、中学生にも分かるように書いてないので、書いてみました。（最近、一人称視点の小説を読んだので、解説も一人称視点で書いてみました。）

証明

前書き

　例えば偶数2, 4, 6, 8, …は$${n}$$番目の偶数が$${2n}$$と計算できると分かっている。素数はどうだろうか、つまり

（$${n}$$番目の素数）＝（$${n}$$の何かしらの式）

の「何かしら」が分かったりしていないだろうか。分かっていれば$${n}$$にポンポン数を入れていけば、いくらでも素数が生み出せるから、素数が無限にあることはすぐに分かるのだが……

　しかし調べてみると、どうやら「何かしら」を見つけることは、数学上の超難問とされているらしい。

　ならば、諦めて別の道を探すのが賢明だろう。

　何も、$${n}$$番目の素数を具体的に知りたいわけではないのだ。ただ、素数の個数に限りがあるのか、無いのかを知りたいだけなのだ。

　であれば、もっと間接的なアプローチがあるはずだ。

　まっすぐ攻めるだけが道じゃない。

証明スタート

　そもそも「素数が無限になかったらどうなるか」を考えてみる。考えてみるだけなので、何も問題ない。思考実験というやつだ。思考の中なら、世界が100人の村だったらどうなるか、と考えるのも自由だ。

　素数が無限にはないってことは、つまり、素数には限りがあるってことになる。だから、1番目の素数は2、2番めの素数は3……といった具合に素数のリストを作ったら、この作業はどこかで終わる。

　ただまあ、具体的にどこで終わるのかは分からない。だから最後の番号は適当に$${n}$$とでもしておこう。（$${a}$$とか$${b}$$を使うより、番号が英語でnumberだから、その頭文字を取って$${n}$$とした方が分かりやすいはずだ。）

　同じく、最後の素数である$${n}$$番目の素数も何か分からない。だから適当に$${p_n}$$としておく。（右下に小さく$${n}$$と添えることで、$${n}$$番目であることがひと目で分かる。あと、素数が英語でprime numberなので頭文字のpを取って使っている。）

　素数を小さい順番に並べてリストを書き出してみると、こんな感じになる。

 　　　　　　　　　　　　（素数のリスト）
　　　　　　　　　　　　　番号　　素数
　　　　　　　　　　　　　　1　　　2
　　　　　　　　　　　　　　2　　　3
　　　　　　　　　　　　　　3　　　5
　　　　　　　　　　　　　　4　　　7
　　　　　　　　　　　　　　︙　　︙
　　　　　　　　　　　　　1157　　9343
　　　　　　　　　　　　　1158　　9349
　　　　　　　　　　　　　　︙　　︙
　　　　　　　　　　　　　　$${n}$$　　$${p_n}$$
　　　　　　　　　　　　　 （おわり）

　うむ、悪くない。この世界のあらゆる素数はこのリストに載っていることになる。このリスト、売ったら儲かるだろうか。

　ありがたいことに、1158番目の素数が9349だと既に誰かが確かめてくれているので、$${n}$$は少なくとも1158以上だとは分かる。

　だから本当にこのリストをちゃんと書こうとしたら、かなり長いリストになる。書かないけど。

ターニングポイント

　何やら作為的な匂いがするが、この世界に存在する全ての素数をかけあわせてみる。

$$
N = 2 \times 3 \times 5 \times 7 \times \cdots \times 9343 \times 9349 \times \cdots \times p_n
$$

$${N}$$はよく分からんが、とんでもなく大きな数だ。それでも、とにかくある数だ。素数が無限にアレばこうはいかない。
　あと、$${N}$$は全ての素数で割り切れるのは、作り方から明らかか。

　こいつに、ちょっとしたいたずらをしてみよう。具体的に言えばこれに1を足してみる。

$$
M = N + 1
$$

　これだけなのに、効果は劇的だ。$${M}$$は全ての素数で割り切れなくなる。理由を次で説明しよう。

全ての素数で割り切れない理由

　$${M}$$が、たまたま何かある素数$${p}$$で割り切れたらどうなるだろうか。

上の式で$${N}$$を移項してみる。

$$
M - N = 1
$$

　さっき確認済みだが、$${N}$$はあらゆる素数で割り切れる。だから、素数$${p}$$で割り切れるのは当然だ。

　つまり、$${M}$$と$${N}$$は素数$${p}$$で割り切れている。

　すると、$${M - N}$$も$${p}$$で割り切れることになる。（理由は「補足1」で説明しておく。）

　これで左辺が$${p}$$で割り切れることが分かる。となれば、イコールでつながっている右辺も$${p}$$で割り切れないといけない。

　右辺とか言ったが、要するに1のことだ。1が素数$${p}$$で割り切れないといけない。しかし1だ。1を割り切るのは1だけだ。素数$${p}$$は絶対に2以上だから、1を割り切れるはずがない。

　だから$${M}$$が、たまたま何かある素数$${p}$$で割り切れるなんてことは起こらない。起こってはいけない。ということになる。

結論へ

　$${M}$$がどんな素数でも割り切れないことが分かった。
　あれ、$${M}$$ってなんだっけ？
　ちょっと書いてみよう。

$$
M = 2 \times 3 \times 5 \times 7 \times \cdots \times 9343 \times 9349 \times \cdots \times p_n + 1
$$

　そうそう、こんなやつだった。存在する全ての素数をかけ合わせて、1を足すんだ。こいつは、どんな素数でも割り切れないわけだ。

　しかし、算術の基本定理によれば、どんな数でも何かしらの素数で割り切れないといけない。（補足3）おっと、1は例外か。ただ$${M}$$は明らかに1より大きいから気にしなくていい。

　つまり、本当は、$${M}$$は何かしらの素数で割り切れないといけない。

　それが世界の決まりだ。

　素数が有限個しかないとすると、世界の決まりに反した数を作り出せてしまう。だから、素数は無限個ないといけない。

　証明終了だ。

補足1（差が割り切れる証明）

　$${M}$$と$${N}$$が素数$${p}$$で割り切れるなら、$${M - N}$$が$${p}$$で割り切れることを証明しよう。一見当たり前だろうか？　ただ、改めて証明しろと言われると、ちょっと戸惑う感じだ。

　こういう時は定義に戻って考えるのが近道だ。

　調べてみると、「$${M}$$は$${p}$$で割り切れる」の定義は、こうだ：

$${M = kp}$$となる数$${k}$$がある。

　まあ、当たり前と言えば当たり前だな。ただ、その当たり前を途方もなく積み重ねることで、当たり前でない結論にたどり着くのが数学だ。ここは謙虚に受け止めよう。

　重要なのは$${k}$$という数の存在が保証されている、ということだ。

　同じように、$${N}$$は$${p}$$で割り切れるから、$${N = lp}$$となる数$${l}$$があるはずだ。

　とすれば、

$$
M - N = kp - lp = (k - l) p
$$

と書ける。これで$${M - N}$$が$${p}$$で割り切れると言える。少し分かりにくいだろうか。

　分かりやすくするために、$${k - l}$$を改めて$${m}$$とでもしよう。そうすれば、

$$
M - N = mp
$$

となる。これは$${M - N}$$が$${p}$$で割り切れる定義に一致する。

　証明終了！

補足2（矛盾の張本人）

　証明の核は、$${M}$$という数だ。$${M}$$が世界の理から外れた張本人だった。素数が無限にあることが分かった今、こいつの立ち位置はどうなっているのか、少し気になる。

　素数は無限にあるから、当然$${n}$$番目で終わりということはない。どんな大きな素数を連れてきても、「僕はそれより大きい素数です」というヤツが出てくる。

　ただ、$${n}$$を適当に決めて、

$$
M = 2 \times 3 \times 5 \times 7 \times \cdots \times 9343 \times 9349 \times \cdots \times p_n + 1
$$

という数を考えること自体は許される。何の問題もない。
　上でした証明と同じ流れで、$${M}$$は

$$
2, 3, 5, 7, \cdots , 9343, 9349, \cdots ,p_n
$$

の全てで割り切れないことが分かる。

　しかし、それだけだ。

　証明の時は、

$$
2, 3, 5, 7, \cdots , 9343, 9349, \cdots ,p_n
$$

がこの世界の全ての素数であるという前提があった。だから$${M}$$は全ての素数で割り切れない、と言えた。

　でも、今はそうはならない。$${p_n}$$の後にも素数は続いてゆく。

　$${M}$$は$${n}$$番目よりもっと先の素数で割り切れるだけだ。

　$${M}$$から矛盾が引き出されたのは、$${p_n}$$が最後の素数という前提があったからだ。今はそんなものはない。

　$${M}$$はただ「$${n}$$番目までの素数で割り切れない」という性質を持った数に過ぎない。

　ちなみに、ある$${n}$$について、たまたま$${M}$$が素数になることはある。しかしどんな$${n}$$についても$${M}$$が素数になるわけじゃない。

　本当かって？

　そこまで言うなら、試してみようじゃないか。俺もちょっと興味がある。

　$${n=1}$$の時、$${M=3}$$で、素数。
　$${n=2}$$の時、$${M=7}$$で、素数。
　$${n=3}$$の時、$${M=31}$$で、素数。

　ほう。頑張るじゃないか。

　$${n=4}$$の時、$${M=211}$$で、素数。
　$${n=5}$$の時、$${M=2311}$$で、素数。

　おいおい。まじか。

　$${n=6}$$の時、$${M=30031}$$で、素数ではない。

　ふむ。まあ、こんなものだ。ちなみに、

$$
30031 = 59 \times 509
$$

と素因数分解される。ちなみに、59は17番目、509は97番目の素数だ。

補足3（算術の基本定理）

　1を除いたどんな数$${n}$$でも、必ず素数で割り切れることを証明しよう。

　と、思ったが、面倒なので証明のアイデアだけ書くことにする。数学的に問題のない形で清書する作業は、読者に任せる。

　で、アイデアだ。

　もし$${n}$$が素数なら、$${n}$$は自分自身という素数で割り切れるからOKだ。

　だから問題は$${n}$$が素数ではない場合。つまり合成数の場合だ。

　合成数は$${n=ab}$$と分解できる。

　分解先の$${a}$$または$${b}$$が素数であれば、話は終わりだ。なのでどちらも合成数と仮定することになる。だから、さらに分解可能だ。

　それでまた素数なら終わりだから、合成数と仮定して分解する。

　こうして分解を続けていって、どこかで素数が現れたら終わりだ。

　最後の可能性として、どこまで分解しても素数が現れない場合が残される。この場合、分解は無限に行われることになるのだが、これはありえないと分かる。

　なぜなら、分解をすると数は小さくなるからだ。各分解のステップ毎に、現れる数は小さくなってゆく。

　そして自然数には最小の数1がある。

　だからどこかで分解は終わる。つまり、あるステップで、分解後の数が合成数ではない瞬間が来る。

　それは素数が現れたということである。

　そこで、終わりだ。

　全ての場合について、$${n}$$は何らかの素数で割り切れることが言えた。

　証明終了！