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