全脳科学帳

これを好む者はこれを楽しむ者に如かず

素数が無限に存在することの証明 (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

プログラムを使ってもこのあたりが限界のようだが、楽しい。