素数が無限に存在することを、ユークリッドが証明しました。その証明方法を使って、素数表を作ってみるとどうなるのかを実験してみました。
Ⅰ ユークリッドの証明方法
Ⅱ 実験結果
Ⅰ ユークリッドの証明方法
「素数が無限にあることの証明」で解説した通り、ユークリッドは次の方法で証明を行いました。
素数が有限個しかないと仮定する。
このとき、すべての素数は $~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 139
\end{align}
である。
よって、新たな素数 $~13~$ が見つかった。
なんと $~13~$ を発掘！ $~139~$ も素数ではありますが、手続き上 $~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~$ が見つかった。
またまたそれ自身が素数。これ以上は素数判定ができなくなってしまうので、ここで終了します。
思いつきで実験してみましたが、とりあえずは１ケタの素数は登場させられました。
素数は無限にあるので、この試行を繰り返していくうちに、２ケタの素数もコンプリートできるはず！！
あとはスパコンにお任せします！！
手計算で７ケタ×７ケタはなかなか辛いものがありました。
コメント
コメント一覧 （4件）
面白かったです！
>1807=13×1807
>1807 も素数ではありますが
1807＝13×139
139 は素数
ですよね？
コメントありがとうございます！！
その通りです。修正いたしました。
ご指摘いただき、助かります(^.^)
内容もとてもおもしろいものなのですが！
７桁×７桁を手計算するなんて…まずそこに拍手です！
小学校などで習う（というか覚える？）素数は割と限られているので、
このように自身で素数を発見できるというのは驚きです。
体調に気を付けて、これからも更新頑張ってください！
コメントありがとうございます。
素数が無限に存在することの証明を利用した企画でした。
コメント大変励みになります！！ 更新頑張ります！！