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

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

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

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

N_nc^{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 \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  = 2^2 \times 3 \times 7 \times 13 \times 67 \times 157 \times 181 \times 277 \times 1801 \times 3499 \times 32323 \times 64621 \times 17083093

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

はてなブックマーク - 素数が無限に存在することの証明 (2)
[`evernote` not found]

素数が無限に存在することの証明 (2)” への2件のコメント

  1. 俺は2006年のさらに二十年以上前には知っていた証明だから新証明のわけない。

コメントを残す

メールアドレスが公開されることはありません。