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

この記事では、高校数学で理解できる、
「素数が無限に存在することの証明」

について、紹介したいと思います。

素数について

まずは「素数」について、
正確な定義からおさらいしていきましょう。

「素数」とは、
正の約数が1とその数自身のみである自然数。

簡単に言えば、
正の約数を2つしか持たない自然数です。

具体的には、以下の通り。

「1」約数：1　→　素数ではない
「2」約数：1, 2　→　素数
「3」約数：1, 3　→　素数
「4」約数：1, 2, 4　→　素数ではない
「5」約数：1, 5　→　素数
「6」約数：1, 2, 3, 6　→　素数ではない
「7」約数：1, 7　→　素数
「8」約数：1, 2, 4, 8　→　素数ではない
…

「1」は約数が1つしかないため、
素数ではありません。

また、「4, 6, 8」は約数が3つ以上あるため、
素数ではありません。

背理法について

では次に、数学の証明方法の一つである、
「背理法」について紹介します。

「背理法」とは、ある命題が、
正しくないと仮定して矛盾を導くことで、
もとの命題が正しいことを証明する方法。

例えば、「猫が犬でないこと」
を背理法で証明すると…

①「猫が犬である」と仮定する。
②犬は「わんわん」と鳴くが、
　猫は「わんわん」と鳴かない。
③よって「猫が犬である」
　という仮定に矛盾が生じる。
④よって「猫は犬ではない」。

このような方法を「背理法」といいます。

【証明】素数は無限に存在する

それでは本題の、
＜素数が無限に存在することの証明＞
を紹介したいと思います。

—（証明）—

背理法を用いるので、
＜素数が無限に存在しない＞

つまり、
＜素数が有限個(ｎ個)しか存在しない＞

と仮定して矛盾を導いていきます。

このｎ個の素数を、
　P1、P2、P3、…、Pn
と名付けておきます。

いま、この世界には、
「P1～Pn のｎ個の素数しかない」
と仮定したので、

「P1～Pn 以外の素数が存在すること」
を見つけてあげれば、

仮定が間違っていたことになり、
素数が無限に存在することを証明できます。

ここで、
P1～Pn までをかけ合わせた数に1を足した数
を「Q（※）」とします。

※ Q ＝ ( P1 × P2 × P3 × … × Pn ) ＋ 1

すると「Q」は、
P1～Pn のどの数でも割り切ることができません。

P1～Pn までをかけ合わせた数

（ P1 × P2 × P3 × … × Pn ）

は、P1～Pn の倍数なので、
P1～Pn のどの数でも割り切ることができます。

ただ、「Q」はそこに1を足しているので、
P1～Pn のどの数でも割り切ることができない、
ということになります。

よって、この「Q」という数は、
1とQでしか割り切れない数。

つまり、「Q」は P1～Pn 以外の素数
ということになります。

ゆえに、仮定が間違っていたことになるので、
素数は無限に存在することが証明されました。

おわりに

いかがでしたでしょうか？
非常にシンプルで個人的に好きな証明のひとつです。

※この記事の内容は、動画でも解説しています。
▼YouTube「好きになる数学」ch

ちなみにこの背理法による証明は、
紀元前にユークリッドにより発見されたといわれています。

素数が無限に存在することの「証明」は、
この方法以外にもいくつかありますので、
興味がある方はぜひ調べてみてください！