なぜ素数は無限に存在するのか？ ユークリッドが遺した美しい背理法
出典: 素数とは、「1とその数自身でしか割り切れない、1より大きい整数」のことだ。 2, 3, 5, 7, 11, 13, 17… と続くこの不思議な数は、すべての整数を形作る「数字の元素」のような存在である。
数は無限にあるのだから、素数も無限にあるように思える。しかし、数が大きくなるにつれて、例えば1億や1兆といった巨大な領域では、他の数で割り切れる「合成数」ばかりになり、素数はどんどん見つかりにくくなっていく（実際、素数の出現頻度は対数的に減少する）。
では、いつか素数は「枯渇」して、最大最後の素数で行き止まりになってしまうのだろうか？
この疑問に対し、今から2300年以上前、古代ギリシャの数学者ユークリッドは、自著『原論』において「素数は無限に存在する」ことを、極めてエレガントな方法で証明した。その証明で使われたのが、現代でも数学の強力な武器である「背理法」だ。
ユークリッドの美しい証明（背理法）
背理法とは、「証明したい命題の『逆』を仮定し、そこから矛盾を導き出すことで、元の命題が正しいことを証明する」という推理手法である。
ユークリッドは以下のように論理を展開した。
ステップ1：素数は「有限個しかない」と仮定する
まず、素数が有限個（例えば全部で $n$ 個）しか存在しないと仮定しよう。
それらの有限個の素数をすべてリストアップし、小さい順に $p_1, p_2, p_3, \dots, p_n$ と名付ける。
（仮定の上では、これ以外の素数は宇宙に存在しない）
ステップ2：すべての素数を掛け合わせた数に「1」を足す
ここで、リストアップしたすべての素数を掛け合わせ、最後に「1」を加えた新しい巨大な数 $P$ を作成する。
$$P = (p_1 \times p_2 \times p_3 \times \dots \times p_n) + 1$$
ステップ3：数 $P$ の性質を考える
この新しく作った数 $P$ は、一体どんな数だろうか。
この数 $P$ を、私たちが最初に作った「すべての素数のリスト」のどれか（例えば $p_1$ や $p_2$）で割ってみる。
すると、前半の積の部分 $(p_1 \times p_2 \times \dots \times p_n)$ はきれいに割り切れるが、最後に足した「1」が余ってしまう。
つまり、$P$ はリストにあるどの素数で割っても、必ず「1」余る。
ステップ4：矛盾の発生
算術の基本定理により、「1より大きいすべての整数は、素数の積で表せる（または自身が素数である）」という絶対のルールがある。
しかし、数 $P$ はリストにある既存のどの素数でも割り切れない。ということは、次の2つの可能性しか残されていない。
- $P$ 自身が、リストに載っていない「新しい素数」である。
- $P$ はリストに載っていない「別の新しい素数」で割り切れる。
いずれにしても、「リストの $n$ 個で素数はすべてである」という最初の仮定が崩れ、リストの外側に新たな素数が存在しなければならないことになる。
この矛盾は、最初の「素数は有限である」という仮定が間違っていたために生じたものだ。したがって、「素数は無限に存在する」という命題が正しいことが証明された。
2300年間色褪せないロジック
この証明の何よりの美しさは、**「具体的な新しい素数を計算して見つける必要がない」**という点にある。ただ論理の力だけで、まだ見ぬ無限の彼方にある素数の存在を保証して見せたのだ。
哲学者ベルトラント・ラッセルは「数学には、最も純粋な芸術に匹敵する最高の美が存在する」と語ったが、ユークリッドのこの証明は、まさにその「冷厳で美しい芸術」の完璧な一例である。今夜、夜空を見上げるとき、その暗闇の深さと同じように、数学の世界にも無限の星（素数）が瞬いていることに思いを馳せてみてはいかがだろうか。
お役立ち情報
- Wikipedia - 素数の無限性
- ユークリッドの証明のほか、オイラーによるゼータ関数を用いた証明や、トポロジーを用いた現代的な証明など、様々なアプローチの日本語まとめ。
- 数学カフェ - 数学の美しさに触れるシリーズ
- 一般の数学愛好家向けに、背理法の基本的な使い方から数学史上の有名な証明までを平易に解説した日本語コミュニティサイト。
- The Prime Pages
- テネシー大学が運営する、素数に関するあらゆる情報（現在見つかっている最大の素数、素数判定アルゴリズムなど）が集約された世界的な専門サイト（英語）。