素数は無限にある：ユークリッドの証明

紀元前300年頃、ユークリッドはひとつの段落に収まる論法を書き留めました。それは改善されることがありませんでした。改善できないからです。主張は素数が永遠に続くというもので、証明は構成です：有限の素数リストを持ってきてください、そこに載っていない素数をお返しします。

2000年後の今もなお、この論法には良いマジックトリックの質があります。すべての手順がはっきり見えます。どう終わるかも分かっています。それでも決まります。

素数とは何か、そしてなぜこの問いが重要か

素数とは1より大きい整数で、約数が1とそれ自身だけのものです。最初のいくつかは 2、3、5、7、11、13 です。整数の中に原子のように存在し、他のすべての整数は素数を掛け合わせて作られます。たとえば30は 2 × 3 × 5 に分解され、その因数分解の仕方は本質的にひとつです。

素数がすべての整数の構成要素である以上、自然な問いが生まれます：素数は尽きるのでしょうか？最大の素数があって、それを超えると枯れてしまうのでしょうか？ユークリッドの答えはノーであり、その道筋は一度座って読み通せるほど優雅です。

設定：リストが完全だと仮定する

この論法は背理法による証明です。反対側に一切を与えることから始めます。

さて、すべての素数をリストに集めたところで、それらから新しい数を構成します。

リストを破る数を構成する

これが核心の操作であり、何をしているのかをじっくり見る価値があります。リストのすべての素数を掛け合わせると、リスト上のどの素数も割り切れる数が得られます。1を加えることで、それらすべてを一度に乱します。

NをP1で割ると、余りは1です。なぜなら積（p1 × p2 × … × pk）はp1で割り切れ、1を加えることで余りが1になるからです。p2も、p3も、リスト上のすべての素数について同じ論理が成り立ちます。それらのどれもNを割り切れません。

矛盾

証明を誠実にする反例

ここで多くの通俗的なユークリッドの証明の解説が道を踏み外します。N自身が常に素数だと主張するのです。そうではありません、そしてその区別は重要です。

リスト {2、3、5、7、11、13} を取りましょう。積は 2×3×5×7×11×13 で、それは30030です。1を加えると N = 30031 です。

30031は素数でしょうか？いいえ。

30031 = 59 × 509 です。

59と509はともに素数であり、どちらもリスト {2、3、5、7、11、13} に現れません。これはまさに証明が予測していることです：Nが素数であることではなく、Nの素因数がリストに存在しないこと。この場合、素因数は59と509という、有限リストに載り損ねたふたつの素数です。論法は正しく、その正しさは因数から来ており、N自身からではありません。

証明が実際に言っていること

この論法の形は珍しいほどにクリーンなので、少し立ち止まる価値があります。

漏れた素数を明示的に構成しているわけではありません。それを探しているのでもありません。そうでないと仮定すると論理的な袋小路に至ることを示すことで、それが存在しなければならないことを証明しています。Nの因数に潜む素数qは、見つけやすいかもしれません（59と509は、30031のいくつかの小さな約数を試せば見つかります）。あるいは巨大かもしれません。証明は気にしません。その力は必然性から来ています：どんなリストを渡しても、構成はギャップを見つけます。

これは自然に、「反対を仮定し、崩れるのを見る」という同じ精神で進む他の証明につながります。カントールの対角線論法は、より大きなスケールで同じ構造を使います：実数の完全なリストが存在すると仮定し、そこにないことが証明可能な実数を構成します。ユークリッドの残響は聞き違えようがありません。

素数が完全に消えることがない理由

証明が教えてくれないことのひとつは、素数がどれくらい離れていられるか、あるいはある素数の次の素数がどれほど大きいかです。ユークリッドの論法が保証するのは存在だけです：どんな有限の集まりの先にも、別の素数が住んでいる。数直線上の素数の分布ははるかに難しい問いであり、今日でも数学の最も深い未解決の領域のひとつであり続けています。

証明が教えてくれることは構造的なことです。素数は有限の手段では尽くせません。素数をリストアップすることに一生を捧げても、常に無限の余りへとリストアップし続けることになるでしょう。見つけたすべての素数は本物でしたが、あなたの前にある素数も同じくらい本物で、同じくらい多く、有限のリストでは同じくらい届かないのです。

掛け算と指数で数を構成したときにどれだけ速く増大するかの感覚のために、指数を直感的に理解する記事が自然な伴侶です：p1 × p2 × … × pk の積は思ったよりずっと速く増え、それがNがこんなに素早く大きくなる理由のひとつです。

その禅的な本質

ユークリッドの証明は2000年以上前のものであり、数学者たちはそれ以降、同じ結果の数百もの証明を発見しました。しかしそのどれも、この証明を時代遅れにしていません。この証明がその位置を保っているのは、最も巧妙だからでも最も一般的だからでもなく、最も透明だからです。

一度読むだけで論法全体が見えます。構成は自然です。矛盾は鮮明です。複雑な機械が主張する通りに動いていると信じ込まなければならないステップはひとつもありません。

証明があなたに心に留めてほしいことはひとつのアイデアです：どんな有限の素数リストもすでに不完全である。リストの選び方が悪いからではなく、素数とはどんな有限の数でも収め切れないようなものだからです。素数は整数が無限に属するように、分数が無限に属するように、直線上の点が無限に属するように、無限に属しています。証明は次の素数がどこにあるかを教えてくれません。次の素数は必ずそこにある、と教えてくれます。

それで十分です。それはいつでも十分でした。

この必然性の精神を共有する他の結果については、グッドスタインの定理が、「別の可能性が不可能なのだから何かが起きなければならない」という同じ論理を使い、どんなに書き表せないほど増大しても必ずゼロに戻る数列を示しています。この論法の家族を知ることには価値があります。それぞれが同じ根本的な事実への異なる角度です：数学には逃げ道がありません。構造は保たれます。