素数が無限に存在することの証明 (2)

2つ目に紹介する証明は、2006年にフィリップ・サイダックが発表したもの。とても簡潔で、私はこの証明が最も好きである。

証明
$N_1$ を1より大きい整数とする。 $N_1$ と $N_1 + 1$ は互いに素なので、 $N_2 = N_1 (N_1 + 1)$ は少なくとも2つの異なる素因数を持つ。同様に、 $N_2$ と $N_2 + 1$ は互いに素なので、 $N_3 = N_2 (N_2 + 1)$ は少なくとも3つの異なる素因数を持つ。この操作は無限に続けることができるので、いくらでも大きな個数の素数を得ることができる。したがって素数は無限に存在する。(証明終) (→ 英語版)

こんな簡潔な証明が21世紀になってから発見されたというのは驚きである。しかも背理法を使わず、直接的に「無限」を扱っているのがいい。

$N_n$ は $c^{2^n}$ ぐらいのオーダーで増えるので、急速に大きくなる。 $N_1 = 2$ として計算してみると、

$\displaystyle N_1 = 2$

$\displaystyle N_2 = 6 = 2 \times 3$

$\displaystyle N_3 = 42 = 2 \times 3 \times 7$

$\displaystyle N_4 = 1806 = 2 \times 3 \times 7 \times 43$

$\displaystyle N_5 = 3263442 = 2 \times 3 \times 7 \times 13 \times 43 \times 139$

$\displaystyle N_6 = 10650056950806 = 2 \times 3 \times 7 \times 13 \times 43 \times 139 \times 3263443$

$\displaystyle N_7 = 113423713055421844361000442$ $\displaystyle = 2 \times 3 \times 7 \times 13 \times 43 \times 139 \times 547\times 607 \times 1033 \times 31051 \times 3263443$

$\displaystyle N_8 = 12864938683278671740537145998360961546653259485195806$ $\displaystyle = 2 \times 3 \times 7 \times 13 \times 43 \times 139 \times 547 \times 607 \times 1033 \times 29881 \times 31051 \times 67003$ $\displaystyle \times 3263443 \times 9119521 \times 6212157481$

(大きな数の計算と素因数分解には、大矢建正さんの数学のプログラムと、カシオの高精度計算サイトを使った)
というふうに素因数の数が増えていく。

$N_1 = 3$ もやってみよう。

$\displaystyle N_1 = 3$

$\displaystyle N_2 = 12 = 2^2 \times 3$

$\displaystyle N_3 = 156 = 2^2 \times 3 \times 13$

$\displaystyle N_4 = 24492= 2^2 \times 3 \times 13 \times 157$

$\displaystyle N_5 = 599882556 = 2^2 \times 3 \times 7 \times 13 \times 157 \times 3499$

$\displaystyle N_6 = 359859081592975692 = 2^2 \times 3 \times 7 \times 13 \times 67 \times 157 \times 277 \times 3499 \times 32323$

$\displaystyle N_7 = 129498558604939936868397356895854556$ $\displaystyle = 2^2 \times 3 \times 7 \times 13 \times 67 \times 157 \times 181 \times 277 \times 1801 \times 3499 \times 32323 \times 64621$ $\displaystyle \times 17083093$