素数は、示されたどんな個数の素数よりも多い。

— ユークリッド『原論』命題 IX.20

素数 とは、1 と自分自身でしか割りきれない、1 より大きい整数です。2、3、5、7、11、13、……。ほかの数は、$12=2\cdot2\cdot3$ のように、すべて素数の積です。素数は算数の原子なのです。

先へ進むほど、素数はまれになります。1 から 100 までには 25 個ありますが、1 000 001 から 1 000 100 までには 6 個しかありません。どこかで尽きてしまうのでしょうか。ユークリッドは、尽きないことを四行の議論で示しました。イギリスの数学者 G. H. ハーディは、それを数学全体で最も美しい議論のひとつとみなしていました。

証明

だれかが有限個の素数のリスト $p_1,p_2,\ldots,p_n$ をくれたとします。ユークリッドは、そのリストの 外に 少なくともひとつ素数があることを示します。すべてをかけて 1 を足しましょう。

$$N=p_1\cdot p_2\cdots p_n+1.$$

$N$ をリストのどの素数で割っても、積 $p_1p_2\cdots p_n$ はその素数で割りきれるので、余りは 1 です。リストのどの素数も $N$ を割りきりません。

ところが $N$ は 1 より大きいので、少なくともひとつ素因数 $q$ をもちます。なぜでしょう。$N$ の 1 より大きい約数のうち最小のものをとります。それが素数でなければ、もっと小さい約数をもち、それも $N$ を割りきるので、最小だという選び方に反します。だから最小の約数は素数です。

この素数 $q$ は $N$ を割りきり、リストのどの素数も $N$ を割りきりません。よって $q$ はリストにありません。どんな有限のリストもすべての素数を含むことはできないのです。

$$\boxed{\text{素数は無限にある。}}$$

ユークリッドは「無限」という言葉を使いません。ギリシャ人が避けた言葉です。彼は、どんな 個数の素数が与えられても、もっとある、と言います。同じことを、注意深く言ったのです。

つくった数はいつも素数とはかぎらない

$N$ はいつも素数だと思うのは、よくあるまちがいです。見てみましょう。

リスト $N$ $N$ は素数か
2 3 はい
2, 3 7 はい
2, 3, 5 31 はい
2, 3, 5, 7 211 はい
2, 3, 5, 7, 11 2 311 はい
2, 3, 5, 7, 11, 13 30 031 いいえ：$30\,031=59\cdot509$

六行目では $N$ は合成数です。けれどもその因数 59 と 509 は、リストにない素数です。証明は $N$ が素数だとは一度も言っていません。言ったのは、何か 新しい素数が $N$ を割りきる、ということだけです。表のようなリストが無限に多くの素数を生むのかどうかは、今もわかっていません。

平方についての似た証明

何かを仮定して矛盾にいたるという同じスタイルの議論で、$\sqrt2$ が分数ではないことも証明できます。『原論』第十巻が論じているもうひとつの結果です。$\sqrt2=\frac pq$ で分数が既約だとすると、$p^2=2q^2$。$p^2$ は偶数なので $p$ も偶数、$p=2k$。すると $4k^2=2q^2$、$q^2=2k^2$ で、$q$ も偶数になります。ところが分数は既約だったはずです。矛盾です。

練習問題：リスト 3、5 から始めると、どんな数ができ、どんな新しい素数が現れるか？

$N=3\cdot5+1=16=2^4$。この数は合成数で、ただひとつの素因数 $2$ はリストにありません。証明は、2 から始まらないリストでも成り立ちます。

練習問題：素数をひとつも含まない、連続する 5 つの数があることを示せ。

$6!=720$ をとります。$720+2$、$720+3$、$720+4$、$720+5$、$720+6$ はそれぞれ 2、3、4、5、6 で割りきれるので、どれも素数ではありません。$(n+1)!$ を使えば、同じようにして連続する $n$ 個の合成数が得られます。素数は尽きませんが、そのあいだはいくらでも広くなりうるのです。

出典： 『原論』命題 IX.20、D. E. Joyce 版 · G. H. ハーディ『ある数学者の生涯と弁明』· GIMPS、Great Internet Mersenne Prime Search。

ユークリッドの全トピック · ← ユークリッドの互除法：最大公約数 · 第五公準とほかの幾何学 →

画像クレジット.