数学コラム
素数が無限にあることの証明
素数が無限に存在することは，ユークリッドによる次の証明が有名です。
素数が有限個しか存在しなかったとして，全ての素数を $p_1,~p_2,~\cdots,~p_n$ とする。ここで，$p=p_1 p_2 \cdots p_n+1$ とすると，$p$ は $p_1,~p_2,~\cdots,~p_n$ のどの素数でも割り切れないので新たな素数となるが，これは $p_1,~p_2,~\cdots,~p_n$ を全ての素数とした仮定に矛盾する。よって，素数は無限に存在する。
紀元前3世紀ごろに『原論』に記されたものですが，今でも背理法の例として教わるので知っている人も多いと思います。素数が無限にあることの証明は様々ありますが，簡潔さで言えばこのユークリッドの証明が一番でしょう。
ところが，最近になってユークリッドに匹敵する簡潔な証明が示されました。2006年に発表されたフィリップ・サイダックによる証明です。
$N$ を2以上の整数とする。$N$ と $N+1$ は互いに素なので，$N_2=N(N+1)$ は少なくとも2つの異なる素因数を持つ。同様に，$N_2$ と $N_2+1$ は互いに素なので，$N_3=N_2(N_2+1)$ は少なくとも3つの異なる素因数を持つ。この操作は無限に続けることができる。
極めてシンプルで美しい証明です。背理法さえも使われていません。
実際にやってみる
$N=2$ でやってみましょう。
| $N$ |
$N(N+1)$ の素因数分解 |
| 2 |
2∙3 |
| 6 |
2∙3∙7 |
| 42 |
2∙3∙7∙43 |
| 1806 |
2∙3∙7∙13∙43∙139 |
| 3263442 |
2∙3∙7∙13∙43∙139∙3263443 |
| 10650056950806 |
2∙3∙7∙13∙43∙139∙547∙607∙1033∙31051∙3263443 |
確かに1つ進むたびに素因数が1個以上増えています。
参考リンク
(2014/05/12)