ユークリッドの証明から素数を作ってみる
素数が無限に存在することを、ユークリッドが証明しました。その証明方法を使って、素数表を作ってみるとどうなるのかを実験してみました。
Ⅰ ユークリッドの証明方法
Ⅱ 実験結果
Ⅰ ユークリッドの証明方法
「素数が無限にあることの証明」で解説した通り、ユークリッドは次の方法で証明を行いました。
素数が有限個しかないと仮定する。
このとき、すべての素数は \(~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~\)
この証明方法は、
・既存の素数すべての積に１を加えた数が、新たな素数となっている。
・既存の素数すべての積に１を加えた数が、新たな素数でわりきれる。
のどちらかになるということを利用し、素数が有限でないことを示しています。
そこでこの記事では、
素数は２だけである
という仮定から出発し、ユークリッドの証明方法により、素数がどう増えていくのかを観察していきたいと思います。
Ⅱ 実験結果
「素数判定プログラム」の対応ケタ数である16ケタを超えるまで、試行を繰り返してみたいと思います。
この時点で素数は
\begin{equation}
2
\end{equation}
だけなので、ここに \(~1~\) を加えると、
\begin{equation}
3（素数）
\end{equation}
である。
よって、新たな素数 \(~3~\) が見つかった。
順当ですね。１番目の素数から２番目の素数が導かれました。
この時点で素数は
\begin{equation}
2,3
\end{equation}
なので、これらの積に \(~1~\) を加えると、
\begin{equation}
2 \times 3+1=7（素数）
\end{equation}
である。
よって、新たな素数 \(~7~\) が見つかった。
\(~5~\) をとばして、 \(~7~\) が先に見つかってしまいました。
この時点で素数は
\begin{equation}
2,3,7
\end{equation}
なので、これらの積に \(~1~\) を加えると、
\begin{equation}
2 \times 3 \times 7+1=43（素数）
\end{equation}
である。
よって、新たな素数 \(~43~\) が見つかった。
このまま \(~5~\) や \(~11~\) は埋もれてしまうのでしょうか・・・。
この時点で素数は
\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~\) のみを採用します。
この時点で素数は
\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~\) も素数です。
この時点で素数は
\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~\) が見つかった。
これで１ケタ素数はコンプリート！ この調子で \(~11~\) も見つかるといいなぁ。
この時点で素数は
\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ではこれ以上の計算ができないので、手計算します。
この時点で素数は
\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~\) が見つかった。
またまたそれ自身が素数。これ以上は素数判定ができなくなってしまうので、ここで終了します。
思いつきで実験してみましたが、とりあえずは１ケタの素数は登場させられました。
素数は無限にあるので、この試行を繰り返していくうちに、２ケタの素数もコンプリートできるはず！！
あとはスパコンにお任せします！！
手計算で７ケタ×７ケタはなかなか辛いものがありました。