素数は無限に存在する(ユークリッドの背理法)

方針

解答

⓪ 発想 — どう考え始めるか。 「無限にある」は、「有限個しかない」と仮定する背理法に翻訳するのが古典的な道だ。

素数が $p_1,\dots ,p_n$ で全部だと仮定して、全部の積に1を足した数 $N=p_1{p}_2\cdots p_n+1$ を作る。

$N$ をどの $p_i$ で割っても余り $1$ — つまり $N$ の素因数はリストのどれとも違う。だが $2$ 以上の整数は必ず素因数をもつ。「リスト外の素数」の存在が、仮定を壊す。

① 有限と仮定。 素数が $p_1,p_2,\dots ,p_n$ の有限個しかないとする。

② $N$ を作る。 $N=p_1{p}_2\cdots p_n+1$ とおく($N\ge 2$)。どの $p_i$ で割っても、$p_1\cdots p_n$ は割り切れるので余りは $1$。よって $N$ はどの $p_i$ でも割り切れない。

③ 矛盾。 $N\ge 2$ は素因数を(少なくとも $1$ つ)もつが、それは $p_1,\dots ,p_n$ のどれでもない=リストにない素数。これは「素数は $p_1,\dots ,p_n$ で全部」という仮定に矛盾する。よって素数は無限に存在する。

まとめ 素数が有限個なら、全部の積に $1$ を足した $N$ がどの素数でも割れず、新しい素因数をもって矛盾。素数は無限。命題(背理法)と整数の融合(ユークリッドの証明)。

発展 — 一歩先へ。 $N=p_1\cdots p_n+1$ 型の数(ユークリッド数)は素数とは限らない: $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\times 509$。「$N$ が素数だから矛盾」と書くのは有名な誤りで、正しくは「$N$ の素因数がリスト外」。素数の無限性には、オイラーによる $\sum \frac{1}{p}$ の発散を使う証明など、まったく別の道もあり、証明の多様さ自体がこの定理の豊かさになっている。

別解

背理法を使わない直接版($n!+1$ の素因数)。 「どんな数よりも大きい素数がある」を直接構成で示すこともできる。

任意の自然数 $n$ に対して、$N=n!+1$ を考える。$N\ge 2$ だから素因数 $q$ をもつ。

もし $q\le n$ なら、$q$ は $n!$ を割り切る($n!$ は $q$ を因数に含む)。すると $q$ は $N-n!=1$ も割り切ることになり不可能。よって $q>n$。

つまり「どんな $n$ に対しても、$n$ より大きい素数が存在する」— 素数はいくらでも大きく、無限にある。仮定を置いて壊す(本解)か、大きい素数を実際に作って見せるか。同じ「積$+1$」の仕掛けの、2つの語り口だ。