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

素数は無限に存在するのでしょうか？今回は素数が無限に存在することの証明についてお勉強していきましょう。

素数とは

素数（Prime Number）とは

数（Prime Number）とは１と自分自身でしか割り切れない１より大きい整数

のことです。
小さいほうから５０個の素数を並べると以下のようになります。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229

素数は無限に存在するの？

素数は無限に存在するのでしょうか？次の定理が知られています。

素数は無限に存在する

証明方法1（ユークリッド）

素数が無限個存在することの証明で一番有名なものはユークリッドの証明です。
実際の証明方法を見てみましょう。

証明

背理法で証明する。
素数がn個しかないとして、その有限個の素数を p₁,p₂,‥,p_nとする。
p = p₁p₂‥p_n + 1はp_i (1≦i≦n)で割り切れないので素数となるが、
p > p_i (1≦i≦n)なので最初に仮定した「素数がn個しかない」ことに矛盾する。
したがって、素数は無限個存在する。

証明方法2（サイダック）

2006年に発表されたフィリップ・サイダックの証明は簡潔でわかりやすい証明になっています。

参考：F. Saidak, “A new proof of Euclid’s theorem,” Amer. Math. Monthly, 113:10 (2006) 937-938.(http://dx.doi.org/10.2307/27642094) MR 2271540

実際の証明方法を見てみましょう。

証明

n>1を正の整数とする。
nとn+1 は連続した整数であるので互いに素である。
したがって
N₂ = n(n+1)
は少なくとも2つの異なる素因子を持つ。
同様に、N₂とN₂+1 は互いに素なので、
N₃ = N₂(N₂ + 1)
は少なくとも3つの異なる素因子を持つ。
この操作は無限に続けることができるので、任意に異なる素因子を持つ数を構成することができる。
よって素数は無数に存在する。

まとめ

今回は素数についてお勉強しました。