問題#A006 ★☆☆☆
素数が無数に存在することを示せ。
《ポイント》
超が付くほど有名な問題です。様々な証明が知られていますが、ここでは由緒正しい伝統的な証明と、21世紀に入ってから発表された恐ろしく簡潔な証明を示しておきます。
《解答例Ⅰ》～ユークリッドの方法による～
任意の素数の集合$p_1$、$p_2$、$\cdots$、$p_n$に対して、そのすべて要素の積に$1$を加えた数 $P=p_1 p_2\cdots p_n+1$ は$p_1$、$p_2$、$\cdots$、$p_n$のいずれでも割り切れないから、 $P$ は上記の集合に含まれない素因数を持たなければならない。これを繰り返すと無数の素数が得られるから、素数は無数に存在する。
《解答例Ⅱ》～サイダックの方法による～
$n$を$1$より大きい整数とする。$n$と$n+1$は互いに素なので$N_1=n(n+1)$は少なくとも$2$つの素因数を持つ。$N_1$と$N_1+1$は互いに素なので$N_2=N_1(N_1+1)$は少なくとも$3$つの素因数を持つ。同様の操作を繰り返していけば無数の相異なる素因数を持つ整数を構成できる。故に素数は無数に存在する。
《コメント》
解答例Ⅰに関して。勘違いなさる方の例として「$p_1 p_2\cdots p_n+1$が素数なんだ、ふ～ん」などと仰る方がいますが、そうではありません。$p_1 p_2\cdots p_n+1$が新しい素数を含むという主張がポイントなのです。書き方的には背理法っぽく書いた方が分かりやすいのですが、少なくとも、素数が無数に構成できるということを言わなければ証明にはなりません。