2.1.6 素数の無限性

最後に、素数が無限に存在することを証明します。この証明は、古代ギリシャ時代から知られたことです。古代ギリシア人は素数が無限にあると知っていました。その証明は、いかにも数学的です。

定理 2.1.32
素数は無限に存在する。

証明

背理法で証明します。素数が有限個しかないと仮定しましょう。その有限個の素数を $p_1,p_2,\cdots,p_n$とします。そして、この全ての素数をかけた数に1を足したものを$x$としましょう。つまり $x=p_1p_2\cdots p_n+1$です。すると、$x$は、どんな素数より大きいことが分かります。また、$p_1$で割ると1余りますので、$p_1$で割り切れません。$p_2$で割っても1余りますので、$p_2$でも割り切れません。同様に、任意の素数で割ると1余りますので、任意の素数で割りきれないことが分かります。つまり、$x$は、すべての素数を約数として持ちませんので、$x$は素数です。ところが、$x$は、任意の素数より大きい素数となってしまい、矛盾です。 これは、素数が有限個しかないと仮定したことが誤っていたのです。したがって、素数は無限にあることがわかります。

何か不思議な証明ですね。狐につままれたような気がしますがその感覚はとても大切です。不思議と思った人は、何度も何度もこの証明を反芻してください。