背理法

HOME＞ ピンポイント解説＞背理法＞素数が無限に存在することの証明

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

ここでは背理法を用いて、素数は無限に存在することを証明する。
証明の前に、素数の性質についてサラリと説明する。

素数とは

1と自分自身しか約数がない自然数を素数という。
20以下の数では、以下の8個が素数だ。
2, 3, 5, 7, 11, 13, 17, 19

上記の8個の数は、どれも1と自分自身でしか割り切ることができない。だから素数なのだ。

100を超えて最初に出現する素数は101、1000を超えて最初に出現する素数は1009だ。
この調子でいくらでも巨大な素数が存在する。

素数以外の数は、素数の積だけで表現できるが、素数は他の素数の積だけで表現することができないことも特徴だ。
(これは素数の定義から当然なのだが、この特徴はあとで出てくる)

背理法による、素数が無限であることの証明

証明したい命題は素数が無限に存在することである。
まず、これと正反対のことを仮定しよう。
「素数は有限個である」----これが仮定だ。

素数が有限個なら、数を数えることができるはずだ。
素数の個数を\(N\)とし、最大の素数\(P_{ N }\)とする。

\(N\)個の素数を順番に並べると、次のようになる。
\[ P_{ 1 }, P_{ 2 }, P_{ 3 }, P_{ 4 }\cdots P_{ N } \]

これらをすべてかけ合わせた数を\(Q\)とする。 \[ Q=P_{ 1 }\times P_{ 2 }\times P_{ 3 }\times P_{ 4 }\cdots P_{ N } \]

この\(Q\)は素数ではない。
\( P_{ 1 }, P_{ 2 }, P_{ 3 }, P_{ 2 }\cdots P_{ N } \)はすべて、\(Q\)の約数だからだ。
つまり\(Q\)は素数を使って割り切れるのである。

\(Q\)は次の式で表すこともできる。 \[ Q=(どれかの素数)\times (残りの素数の積) \]

例えば\(Q=210\) なら \[ 210=2\times (3\cdot5\cdot7) \]

でもいいし、 \[ 210=3\times (2\cdot5\cdot7) \] でもいい。

\[ 210=7\times (2\cdot3\cdot5) \] もある。

ここで\(Q\)に1を加えた数\(R\)を考える。 \[ R=Q+1 \]

\(Q\)は素数で割り切れたが、\(R\)は割り切れない。 \( P_{ 1 }, P_{ 2 }, P_{ 3 }, P_{ 2 }\cdots P_{ N } \)のどれで割っても、必ず1が余るからである。

この1が余る話は、割り算の検算で登場した以下の式に当てはめるとわかりやすい。 \[ R=(どれかの素数)\times (残りの素数の積)+1 \]

もし、\(R=211\)なら、次のようになる。

\[ 211=2\times (3\cdot5\cdot7)+1 \] でもいいし、

\[ 211=3\times (2\cdot5\cdot7)+1 \] でもいい。

\[ 211=7\times (2\cdot3\cdot5)+1 \]

つまり、\(R\)は、\(Q\)を作っているどの素数で割っても余りが生じるのである。
言い換えると、\(R\)は素数の積だけで表現できない数なのだ。

素数でない数は、素数で割り切ることができる。(素数の積だけで表現できる)
素数であれば、他の素数で割り切れない。(素数の積だけで表現できない)
素数は1と自分自身でしか割り切れないからだ。

\(R\)は素数で割り切れなかった。だから\(R\)は素数なのである。
ここで矛盾が出現する。

最初に\(P_{ N }\)を最大の素数と仮定した。
\(R\)は有限個(と仮定した)のすべての素数の積に1を加えた数だから、明らかに\(P_{ N }\)より大きい。
最大の素数だったはずの\(P_{ N }\)よりも、さらに大きな素数Rが現れたことは、明らかに前提と矛盾する。

この矛盾の原因がどこにあるのかと振り返ってみると、論の展開のどこもおかしくない。
ならば、前提とした「素数は有限個である」という仮定が誤りだったことになる。

「素数は有限個である」が誤りなので、「素数が無限に存在する」が正しいことになる。
こうして、「素数が無限に存在する」ことが証明されたのだ。

背理法のポイントは、「素数が無限に存在する」ことを積極的に証明していないことである。
「素数は有限個である」ことを前提として論を進めると矛盾が生じるので、前提の正反対が正しかったとして証明するのだ。

余談だが、まるで「相手チームのミスだけで勝った試合」のような証明だと感じてしまうのは、私だけかもしれない。

■最初のページ：ピンポイント解説：目次

このページのTOPへ