素数が無限にあることの証明

数学雑学数論数学雑学

 素数が無限に存在することの証明は、紀元前にユークリッドによって行われました。その証明方法をわかりやすく解説していきます。
Ⅰ 本当に素数は無限にあるのか
Ⅱ ユークリッドの証明
Ⅲ 証明の解説


目次
  • 1. Ⅰ 本当に素数は無限にあるのか
  • 2. Ⅱ ユークリッドの証明
  • 3. Ⅲ 証明の解説

Ⅰ 本当に素数は無限にあるのか

  \(~2,3,5,7,\cdots~\) と「素数」は続いていきます。
 その素数がこのまま無限に続いていくのか、それとも有限で最大の素数なるものが存在するのかは、ユークリッド以前は難しい疑問でした。
 
 実際、同じ100個の自然数を調べてみても、数が大きければ大きいほど素数の個数は減っていきます。↓↓

自然数の範囲 その範囲の素数の個数
\(~1~\) から \(~100~\) まで 25個
\(~1001~\) から \(~1100~\) まで 16個
\(~10001~\) から \(~10100~\) まで 11個
\(~100001~\) から \(~100100~\) まで 6個

 上の表を見ていると、最終的には素数が無くなってくるのでないかと感じる人も多いかと思います。
 
 しかし、ユークリッドは主著『原論』の9巻命題20で、この疑問を解決しています。


Ⅱ ユークリッドの証明

 ユークリッドが使った方法は、数学Ⅰで出てくる「背理法」です。
 ユークリッドは「√2が無理数であることの証明」もこの方法で行っています。
 
 ユークリッドの巧みな証明方法を見てみましょう↓↓

証明

 素数が有限個しかないと仮定する。
 
 このとき、すべての素数は \(~p_1,p_2,p_3,\cdots,p_n~\) で表すことができる。
 ここで、
\begin{equation}
P=p_1 \times p_2 \times p_3 \times \cdots \times p_n+1
\end{equation}
という自然数 \(~P~\) を考える。
 
 この \(~P~\) は、 \(~p_1,p_2,p_3,\cdots,p_n~\) のどの素数で割ったとしても、 \(~1~\) 余るため割りきれない。
 
 そのため、 \(~P~\) は新たな素数であるか、 \(~P~\) は \(~p_1,p_2,p_3,\cdots,p_n~\) 以外の素数でしか割れない合成数ということになる。
 
 どちらにせよ、すべての素数が \(~p_1,p_2,p_3,\cdots,p_n~\) であることに矛盾するため、素数が無限にあることが示された。 \(~\blacksquare~\)

 さて、この証明を読み理解できたでしょうか。
 
 文字や添え字に抵抗ある人にとっては、意味が掴みにくいかと思います。次章で証明の意味を紐解いていきます。


Ⅲ 証明の解説

 先ほどの証明を、具体的な素数をあてはめて考えていこうと思います。

例1

素数が \(~2,3~\) のみの場合
 素数が \(~p_1=2,p_2=3~\) しかないと仮定する。このとき、自然数 \(~P~\) は
\begin{equation}
P=2 \times 3+1=7
\end{equation}
となる。
 
 この \(~P~\) は、 \(~1~\) と \(~7~\) (その数自身)でしか割れないため、新たな素数である。
 
 そのため、すべての素数が \(~2,3~\) しかないことに矛盾。

 証明中の「 \(~P~\) は新たな素数」というのは、この例1のように、すべての素数の積に \(~1~\) を足すことで、今までにない素数を作り出せてしまうことを表しているのですね。
 

例2

素数が \(~2,3,5,7,11,13~\) のみの場合
 素数が \(~p_1=2,~\)\(~p_2=3,~\)\(~p_3=5,~\)\(~p_4=7,~\)\(~p_5=11,~\)\(~p_6=13~\) しかないと仮定する。このとき、自然数 \(~P~\) は
\begin{equation}
P=2 \times 3 \times 5 \times 7 \times 11 \times 13+1=30031
\end{equation}
となる。
 
 この \(~P~\) は \(~59~\) で割れるが、その \(~59~\) は \(~1~\) と \(~59~\) (その数自身)でしか割れないため、新たな素数である。
 
 そのため、すべての素数が \(~2,3,5,7,11,13~\) しかないことに矛盾。

 証明中の「 \(~P~\) は \(~p_1,p_2,p_3,\cdots,p_n~\) 以外の素数でしか割れない合成数」というのは、この例2のように、すべての素数の積に \(~1~\) を足した数 \(~P~\) が合成数のときのことです。
 
 しかし、その合成数 \(~P~\) は既存の素数では割れないことは証明済みのため、割る数として出てきた数は新たな素数ということになります。
 
 念を押して言いたいのが、

\(~P=p_1 \times p_2 \times p_3 \times \cdots \times p_n+1~\) は必ずしも素数になるとは限らない!

ということ。
 
 実際に \(~30~\) までの素数について、「各素数までの積+1」が素数かどうかを調べてみると、

最大の素数 最大の素数までの積+1( \(~P~\) ) 素数判定
\(~2~\) \(~3~\) 素数
\(~3~\) \(~7~\) 素数
\(~5~\) \(~31~\) 素数
\(~7~\) \(~211~\) 素数
\(~11~\) \(~2311~\) 素数
\(~13~\) \(~30031~\) \(~59~\) でわれる
\(~17~\) \(~510511~\) \(~19~\) でわれる
\(~19~\) \(~9699691~\) \(~347~\) でわれる
\(~23~\) \(~223092871~\) \(~317~\) でわれる
\(~29~\) \(~6469693231~\) \(~331~\) でわれる

 ということで、ほとんどの場合で \(~P~\) 自体が素数ではなく、新たな素数でわれる合成数ということがわかりました。


 この方法で素数表を作ってみたら面白そうです・・・。


 
 


◇参考文献等
・ヴィクターJ.カッツ(2009)『カッツ 数学の歴史』,p.103,上野健爾監訳,三浦伸夫監訳,中根美知代訳,高橋秀裕訳,林知宏訳,大谷卓史訳,佐藤賢一訳,東慎一郎訳,中沢聡訳, 共立出版.
・「素数に恋する女」製作委員会(2017)『素数姫の素数入門』,pp.48-53,洋泉社.
・真実のみを記述する会(2017)『素数表150000個』,暗黒通信団.

数学雑学数論数学雑学

Posted by Fuku