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

プチ研究数論プチ研究

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


目次
  • 1. Ⅰ ユークリッドの証明方法
  • 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を加えた数が、新たな素数となっている。
・既存の素数すべての積に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 1807
\end{align}
である。
 
 よって、新たな素数 \(~13~\) が見つかった。

 なんと \(~13~\) を発掘!  \(~1807~\) も素数ではありますが、手続き上 \(~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ケタはなかなか辛いものがありました。


 
 


プチ研究数論プチ研究

Posted by Fuku