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

非常に大きな素数を一つ見つけても、その先に素数があることは保証できません。素数の無限性は、有限個で全部だと仮定したリストから、そのどれでも割り切れない整数を作ることで証明できます。

成立する条件

素数は $1$ より大きく、正の約数が $1$ と自分自身だけである整数です。$1$ は素数ではありません。

任意の整数 $N>1$ は少なくとも一つの素因数を持ちます。証明ではこの存在だけを使い、素因数分解の一意性までは使いません。

証明

1. まず補題を確認します。$N>1$ の $1$ より大きい正の約数の中で最小のものを $d$ とします。もし $d=uv$（$1<u<d$）と分解できれば、$u$ も $N$ の約数となって最小性に反します。したがって $d$ は素数です。
2. 素数が有限個しかなく、それをすべて $p_1,p_2,\ldots,p_k$ と並べられたと仮定します。$2$ は素数なので、$k\ge1$ です。
3. このリストを使って $$N=p_1p_2\cdots p_k+1$$ と置きます。$N>1$ なので、補題により少なくとも一つの素因数 $q$ を持ちます。
4. 各 $p_i$ で $N$ を割ると、積の部分は割り切れて余りが $1$ になります。したがって、どの $p_i$ も $N$ を割り切りません。特に素因数 $q$ はリストのどの素数とも異なります。
5. これは「リストがすべての素数を含む」という仮定に矛盾します。よって素数は有限個ではなく、無限に存在します。新しい素因数の具体的な大きさを決めなくても、存在は保証できます。

使ってみる

リストが $2,3,5$ なら、$2\cdot3\cdot5+1=31$ はどれでも割り切れません。この例では $31$ 自体が素数です。

一方、$2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509$ は合成数です。それでも素因数 $59,509$ は元のリストにないため、証明の考え方は変わりません。

注意点

「素数の積に $1$ を足すと必ず素数になる」は誤りです。必要なのは、その整数が元のリストにない素因数を持つことです。この証明だけから双子素数が無限にあるとは結論できません。

関連項目