【ユークリッドの定理】素数が無限に存在することのシンプルで美しい証明とは

---

数学の世界では、素数は無数に存在するということがわかっています。

このことが最初に証明されたのは、なんと紀元前３世紀ごろ。
古代エジプトの数学者：ユークリッド（エウクレイデス）が著書『原論』の中で明らかにしました。

彼によるシンプルで美しい証明は、2,300年以上の時を超えて今なお人類を魅了しています。

この記事では、

についてまとめています。

基本的な用語のおさらい

今回ご紹介するユークリッドによる証明（俗にいう「ユークリッドの定理」）は、

背理法の論法を使って「素数の個数が無限であること」を示す

というものです。

これを理解するための前提として、そもそも素数とか背理法がどんなものかをわかってる必要があるので、まずは簡単にそのあたりからおさらいしていきましょう。

素数の定義とは

素数とは、１と自分自身でしか割り切れないような正の整数のことをいいます。

正の整数（自然数）である時点で、すべての数は当然１で割り切ることができますよね。

・3 ÷ 1 ＝ 3
・82 ÷ 1 ＝ 82
・578 ÷ 1 = 578

そして当然、自分自身で割り切ることもできます。

・8 ÷ 8 ＝ 1
・67 ÷ 67 ＝ 1
・771 ÷ 771 = 1

ここまではどの数も同じ。

素数というのは、これら以外に割り切れるような自然数が存在しない数ということです。

逆に割り切れる自然数がほかにある場合、それは素数ではなく「合成数」といいます。

さらに合成数を構成するパーツそれぞれについて「何で割り切れるか」をチェックしていくと、結局すべての自然数は素数同士の掛け算によってできていることもわかります。

・24 ＝ 2 × 2 × 2 × 3　
・365 = 5 × 73
・1000 ＝ 2 × 2 × 2 × 5 × 5 × 5

これが中学校で習う、いわゆる「素因数分解」というやつですね。

背理法ってどんなもの？

背理法というのは、一旦証明したいこととは反対の仮説を立てて、その矛盾を指摘することで当初の命題を証明するような論法のことです。

これではちょっと抽象的なので、犯罪捜査のアリバイを例にして考えてみましょう。

事件の被疑者であるAくんの潔白を証明したいとします。

Aのくんが「僕はやってない！」と訴えても、それ自体の証明は難しいので、ここで「アリバイ」という背理法のテクニックが登場するわけです。

1. ひとまずAくんを犯人だと仮定する
2. 犯行当時Aくんは事件現場から遠く離れた場所にいたことを指摘する
3. 仮定に矛盾が生じ、「Aくんが犯人だ」という説は誤りだとわかる
4. 「Aくんは犯人ではない」と証明できる

こんな感じで、「XだとしたらおかしいからXじゃない」「YじゃないとしたらおかしいからYだ」みたいなのが背理法です。

背理法の論法は数学の証明問題においてもよく登場します。

ユークリッドによる証明

それでは本題です。

素数は無数に存在するという命題について、ユークリッドによる証明は次のとおりでした。

「無限」という大きなテーマを相手にしながら、難解な数式などは一切登場せず、シンプルな論理で端的に証明しきっています。

これが紀元前の記録だというのですから、数学という学問の歴史の深さには感服するしかないですね。

さて、この証明がどういう過程で証明たりえているか、もう少し詳しく読み解いていきましょう。

単純化して考えてみる

まずは問題を単純化して考えてみます。

たとえば仮に、この世に素数が

２、３、５、７、11

の５つしか存在しないとしてみましょう。

証明の手順にしたがって、

\(N=(2×3×5×7×11)+1=2311\)

という数を考えます。

ここで\(N\) は、 2、3、5、7、11 いずれの素数でも割り切ることができません。
カッコの中身（=2310）は割り切れますが、結局「+1」の部分が必ず余りとして残ってしまいますからね。

つまり\(N\)=2311を割り切れる自然数は、1と2311以外には存在しないということです。
ということは、定義からして「\(N\) は素数である」ことが確定します。

これは明らかに矛盾です。
だってこの世に素数は２、３、５、７、11 の５つしか存在しないはずなんですから。

\(N\)=2311という新しい素数が生まれることで当初の前提が崩壊し、そもそも「素数は5つだけ」なんて仮定は誤りだったことが証明できました。

素数がいくつあっても同じこと

さっきのような理屈で考えると、この世に存在する素数が100個だろうが1万個だろうが、有限の数を仮定する限りは同じように矛盾が指摘できることがわかります。

素数が100個しかない世界を、少し抽象度を上げて考えてみましょう。

\(N=(p{\tiny 1} × p{\tiny 2} × p{\tiny 3} × … × p{\tiny 100}) + 1\)

この場合も、100通りのどの素数でも割り切れずに1余るので、やはり\(N\) 自身が101番目の新たな素数となってしまいます。

「すべての素数から成る \(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}) + 1\)

この数式のように「連続する素数をすべて掛け算していって最後に1を足した数（N）は必ず素数になる」というのが常に成り立つ法則だと考えてしまいがちなのですが、これは間違いです。

反例を挙げると、たとえば次のような場合。

\((2×3×5×7×11×13)+1=30031\)

「２、３、５、７、11、13 のどれでも割り切れないんだから素数じゃないの？」
と思うかもしれませんが、現実の素数はこれらの6種類だけではないという点を見落としています。

実際は、30031は59でも509でも割り切れるので、素数ではなく合成数です。

ユークリッドの証明において \(N=(p{\tiny 1} × p{\tiny 2} × p{\tiny 3} × … × p{\tiny n}) + 1\) が素数になるといえるのは、「\(p{\tiny 1}\)～\(p{\tiny n}\) が素数のすべてだ」という前提があるからこそなんですね。
そしてこの前提は現実には起こり得ないわけです。

数の世界って面白い

というわけで今回は、

素数は無限に存在する

という命題について、ユークリッドの定理による証明を見てきました。

はるか紀元前に生み出された内容を現代人が読んでも何の違和感もなく理解し納得できるというのは、ほかの学問分野においてはそうそうないことでしょう。
時代が違えば当然文化が違い、常識が違いますからね。

数と論理がもつ普遍性のおかげで、2,300年もの時を超えて、ユークリッドが味わったのと同じ数の美しさを私たちも味わえる。

そのダイナミックな感覚は、数学ならでは大きな魅力のひとつと言えそうです。