ユークリッドの証明から素数を作ってみる

 素数が無限に存在することを、ユークリッドが証明しました。その証明方法を使って、素数表を作ってみるとどうなるのかを実験してみました。
Ⅰ ユークリッドの証明方法
Ⅱ 実験結果


目次

Ⅰ ユークリッドの証明方法

 「素数が無限にあることの証明」で解説した通り、ユークリッドは次の方法で証明を行いました。

証明

 素数が有限個しかないと仮定する。
 
 このとき、すべての素数は $~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を加えた数が、新たな素数となっている。
・既存の素数すべての積に1を加えた数が、新たな素数でわりきれる。

のどちらかになるということを利用し、素数が有限でないことを示しています。
 
 そこでこの記事では、

素数は2だけである

という仮定から出発し、ユークリッドの証明方法により、素数がどう増えていくのかを観察していきたいと思います。


Ⅱ 実験結果

 「素数判定プログラム」の対応ケタ数である16ケタを超えるまで、試行を繰り返してみたいと思います。

1回目

 この時点で素数は
\begin{equation}
2
\end{equation}
だけなので、ここに $~1~$ を加えると、
\begin{equation}
3(素数)
\end{equation}
である。
 
 よって、新たな素数 $~3~$ が見つかった。

 順当ですね。1番目の素数から2番目の素数が導かれました。

2回目

 この時点で素数は
\begin{equation}
2,3
\end{equation}
なので、これらの積に $~1~$ を加えると、
\begin{equation}
2 \times 3+1=7(素数)
\end{equation}
である。
 
 よって、新たな素数 $~7~$ が見つかった。

  $~5~$ をとばして、 $~7~$ が先に見つかってしまいました。

3回目

 この時点で素数は
\begin{equation}
2,3,7
\end{equation}
なので、これらの積に $~1~$ を加えると、
\begin{equation}
2 \times 3 \times 7+1=43(素数)
\end{equation}
である。
 
 よって、新たな素数 $~43~$ が見つかった。

 このまま $~5~$ や $~11~$ は埋もれてしまうのでしょうか・・・。

4回目

 この時点で素数は
\begin{equation}
2,3,7,43
\end{equation}
なので、これらの積に $~1~$ を加えると、
\begin{align}
&2 \times 3 \times 7 \times 43+1 \\
&=1807 \\
&=13 \times 139
\end{align}
である。
 
 よって、新たな素数 $~13~$ が見つかった。

 なんと $~13~$ を発掘!  $~139~$ も素数ではありますが、手続き上 $~13~$ のみを採用します。

5回目

 この時点で素数は
\begin{equation}
2,3,7,13,43
\end{equation}
なので、これらの積に $~1~$ を加えると、
\begin{align}
&2 \times 3 \times 7 \times 13 \times 43+1 \\
&=23479 \\
&=53 \times 443
\end{align}
である。
 
 よって、新たな素数 $~53~$ が見つかった。

 これまた合成数で、 $~53~$ を見つけました。ちなみに $~443~$ も素数です。

6回目

 この時点で素数は
\begin{equation}
2,3,7,13,43,53
\end{equation}
なので、これらの積に $~1~$ を加えると、
\begin{align}
&2 \times 3 \times 7 \times 13 \times 43 \times 53+1 \\
&=1244335 \\
&=5 \times 248867
\end{align}
である。
 
 よって、新たな素数 $~5~$ が見つかった。

 これで1ケタ素数はコンプリート! この調子で $~11~$ も見つかるといいなぁ。

7回目

 この時点で素数は
\begin{equation}
2,3,5,7,13,43,53
\end{equation}
なので、これらの積に $~1~$ を加えると、
\begin{align}
&2 \times 3 \times 5 \times 7 \times 13 \times 43 \times 53+1 \\
&=6221671 (素数)\\
\end{align}
である。
 
 よって、新たな素数 $~6221671~$ が見つかった。

 まさかのそれ自身が素数。Excelではこれ以上の計算ができないので、手計算します。

8回目

 この時点で素数は
\begin{equation}
2,3,5,7,13,43,53,6221671
\end{equation}
なので、これらの積に $~1~$ を加えると、

\begin{align}
&2 \times 3 \times 5 \times 7 \times 13 \times 43 \times 53 \times 6221671+1 \\
&=38709183810571 (素数)\\
\end{align}


\begin{align}
&2 \times 3 \times 5 \times 7 \times 13 \times 43 \times 53 \\
&\times 6221671+1 \\
\\
&=38709183810571 (素数)\\
\end{align}

である。
 
 よって、新たな素数 $~38709183810571~$ が見つかった。

 またまたそれ自身が素数。これ以上は素数判定ができなくなってしまうので、ここで終了します。
 
 
 思いつきで実験してみましたが、とりあえずは1ケタの素数は登場させられました。
 素数は無限にあるので、この試行を繰り返していくうちに、2ケタの素数もコンプリートできるはず!!
 あとはスパコンにお任せします!!


 手計算で7ケタ×7ケタはなかなか辛いものがありました。


 
 


よかったらシェアしてね!

コメント

コメント一覧 (4件)

  • 面白かったです!

    >1807=13×1807
    >1807 も素数ではありますが

    1807=13×139
    139 は素数

    ですよね?

    • コメントありがとうございます!!
      その通りです。修正いたしました。
      ご指摘いただき、助かります(^.^)

  • 内容もとてもおもしろいものなのですが!
    7桁×7桁を手計算するなんて…まずそこに拍手です!
    小学校などで習う(というか覚える?)素数は割と限られているので、
    このように自身で素数を発見できるというのは驚きです。
    体調に気を付けて、これからも更新頑張ってください!

    •  コメントありがとうございます。

       素数が無限に存在することの証明を利用した企画でした。
       コメント大変励みになります!! 更新頑張ります!! 

コメントする

CAPTCHA


目次
閉じる