素数の無限性

おもちゃ箱に入っているレゴブロックを思い浮かべてみてください。いくつものブロックを組み立てて大きなお城や車を作れますが、ブロックのパーツそのものは、それ以上分けられません。

数学でこの基本ブロックの役目をする数が、まさに素数（1と自分自身だけを約数にもつ数）です。2、3、5、7といった数ですね。6は2と3をかけて作れますし、12は2、2、3をかけて作れます。1より大きい自然数はすべて、素数の積に分解できます。

では、数が1億、1兆を超えてどこまでも大きくなっていくとき、この基本ブロックも新しく現れ続けるのでしょうか。数が大きくなるほど、ほかの数で割り切れる確率が高くなるので、いつか素数が完全に消えてしまいそうに見えます。けれども素数は、宇宙の果てまで行っても決して尽きません。

約2300年前、古代ギリシャの数学者ユークリッドは、この問いに対してとてもエレガントな答えを出しました。彼のもとの証明は、「素数がいくつ与えられても、その外にまた別の素数がある」ことを示す方法でした。今日では、これを「素数は有限だ」と仮定して矛盾を導く背理法（偽だと仮定して矛盾を示す証明法）の形に整えて紹介することが多いです。

世の中に素数が2、3、5の3つしかないと仮定してみましょう。ここで、これらをすべてかけてから1を足します。（2 × 3 × 5）+ 1は31になります。

この新しい数31を2で割ると、余りは1です。3で割っても余りは1、5で割っても余りは1。つまり、私たちが知っているどの素数でも割り切れません。結局、31そのものが新しい素数であるか、私たちが知らなかった別の素数で割り切れるはずです。どちらにしても、もとのリストになかった新しい素数が必ず存在するという結論にたどり着きます。

既知の素数をすべてかけて1を足した数が、いつもそれ自体で素数になるわけではありません。もう少し正確に言うと、その計算結果が合成数（素数ではない数）だったとしても、必ず新しい素数の約数をもつ、という意味です。

たとえば、最初の6つの素数をかけて1を足した（2 × 3 × 5 × 7 × 11 × 13）+ 1は30031です。この数は素数ではなく、59と509という新しい2つの素数の積に分解できます。大切なのは、結果が素数であってもなくても、もとのリストの外にある新しい素数が必ず必要になる、という事実です。

素数は、数が大きくなるほど少しずつ現れにくくなりますが、完全には消えません。ネットバンキングなどで使われているRSAのような現代の暗号方式は、とても大きな素数が十分たくさんあることと、大きな素数2つをかけた数を再び素因数分解するのがきわめて難しいことを利用しています。