素数が無限にあることの4通りの証明

1より大きい整数で，約数が1とその数自身のみであるものを素数と言います。$2,3,5,7,11$ などが素数です。

素数一覧（４桁以下，番号つき）で紹介したように素数はたくさんありますが，実は，素数は無限にある（つまり，任意の整数 $N$ に対して，素数は $N$ 個以上ある）ことが知られています。

この記事では，素数が無限にあることの証明を4通り紹介します。

ユークリッドによる証明です。紀元前に発見されたものです。

※の補足：上記の証明では，

$p_1,p_2,\cdots,p_n$ が素数ならば $p=p_1p_2\cdots p_n+1$ も素数である

という主張をしているわけではありません。実際， この主張は正しくありません（例えば，$2$ と $7$ は素数ですが $2\times7+1=15$ は素数ではありません）。「素数が有限個しかない」という（偽である）仮定のもとで導かれる主張です。

試しに $N_1=2$ としてやってみると， $N_2=6=2\times 3$ となり新しい素数 $3$ を得ます。$N_3=42=2\times 3\times 7$ となり，新しい素数 $7$ を得ます。$N_4=1806=2\times 3\times 7\times 43$ となり新しい素数 $43$ を得ます。

ユークリッドの証明方法に勝るとも劣らない簡潔な証明です。この方法が21世紀になってから発見されたというのも驚きです。

$2^{2^n}+1$ という形の数をフェルマー数と言います。

• フェルマー数どうしは互いに素
• 当然ながら，全てのフェルマー数が素因数を最低1つは含んでいる

という事実から，素数が無限にあることが証明されます。

フェルマー数どうしが互いに素であることの証明はフェルマー数とその性質に記載しています。

$※$はオイラー積表示と呼ばれる，非常に美しい等式です。「全ての素数の組み合わせの積」と「全ての自然数」が一対一対応していることを表しています。オイラー積表示の左辺を具体的に書き下してみるとイメージが分かりやすいでしょう。

$(1+\dfrac{1}{2}+\dfrac{1}{2^2}+\cdots)$ $\times(1+\dfrac{1}{3}+\dfrac{1}{3^2}+\cdots)$ $\times(1+\dfrac{1}{5}+\dfrac{1}{5^2}\cdots)\cdots$

「素数が無限に存在する」よりも強い主張である「ディリクレの算術級数定理」というものがあります：

Tag:無限和，無限積の美しい公式まとめ

Tag:素数にまつわる覚えておくべき性質まとめ