素数は無限にあることは周知の事実であり、その証明も数多くある。

私が青二才の時のこの証明は証明とはいえないものだった。

その証明とは・・・

「数が無限にあるから素数も無限にある」(略証:数が無限にあるから、いくらでも素数の候補があって、時間はかかるかもしれないが探し続ければそのうち素数にぶちあたる。その操作が永遠に続けられるから)

なんとプアーな証明なことだろう。

冗談です。プアーじゃなく、これは証明になっていません。

しかし、いまさらとはいえ、新しい証明方法を考えることで、なにか新しいことがわかるかもしれません。

そこで、素数が無限にあることの新証明に挑戦しようではありませんか。

きっかけは、2006年のサイダックさんの証明(Filip Saidak’s Proof)です。簡潔で初等的な新証明です。

それが簡潔であるがゆえに、一念発起して、私も素数無限の新証明に挑戦したくなったのです。

 

いろいろな証明

素数が無限に存在することはとっくの昔に証明されています。

有名な、ユークリッドさんの原論(紀元前3世紀頃らしい)にかかれている証明ですが、その後からも次々に証明が発表されています。

ウィキペディア
素数が無数に存在することの証明

すばらしいページですね。私が追記することなどありません。

例のサイダックさんの証明(Filip Saidak’s Proof)も解説されています

下記は個人的に気に入ってる証明。背理法を使わないで証明しているところが素敵!

素数の無限性
http://www.ma.kagu.tus.ac.jp/~abe/sub2-2.html

自分で新証明を考えだす前に、過去に公表されている証明方法を研究して新証明に望むことにします。

 

2019.8.10追記:「素数の無限性」ページについて

素数の無限性
http://www.ma.kagu.tus.ac.jp/~abe/sub2-2.html

は、東京理科大学理学部第一部数学科の安部直人教授のページでしたが、閉鎖されたようです。

http://abel.a.la9.jp/sub4.html
が新しく作成されたページのようですが、素数の無限性の記事は掲載されていませんでしたので、下記にそこでかかれていた内容を紹介しておきます。

定理 素数は無限に存在する。

 証明(背理法) 
  定理が成立しないとすると,素数は有限個である。[背理法の仮定]
 それらの素数を p1,p2,・・・, pn とする。
 このとき,q = (p1p2・・・pn)+1 を考えると,
 q は p1,p2,・・・, pn のどれでも割り切れない。
 したがって,q を素数の積として表したとき,
 この積に現れる素数は p1,p2,・・・, pn のいずれとも異なる。
 これは矛盾である。
 したがって定理が証明された。

 直接証明1
  p_1, p_2, ・・・, p_n を相異なる n 個の素数とする。
 q = (p_1p_2・・・p_n)+1 とおく。
 p_1, p_2, ・・・, p_n は q の素因数ではない。
 q は 2 以上の自然数なので、素因数 p を持つ。
 p, p_1, p_2, ・・・, p_n は n+1 個の相異なる素数である。 
 故に、素数は無限に存在する。

 直接証明2
  任意の素数 P につき、P 以下の素数の積を M とする。
 q=M+1 とおく。
 P 以下の素数は q の素因数ではない。
 q は 2 以上の自然数なので、素因数 p を持つ。
 p は P より大きい素数である。
 故に、素数は無限に存在する。

 直接証明3
  任意の自然数 m につき、m(m+1) をとれば、
 「 m の素因数の集合(種類)は、
 m(m+1) の素因数の集合(種類)の真部分集合である」
 これは任意の回数繰り返すことが可能である。
 故に、素数は無限に存在する。

上記の背理法による証明と直接照明1は同じ内容の証明に見えますが、論理的には全然違った構造です。背理法は便利な論理手段だと考えますが、「矛盾」という高度な論理思考を使っています。背理法は、使わなくてすむのなら使わないにこしたことありません。

 

 

自分でも新証明を考える

素数無限についていろいろな証明をみていると、ある共通点に気が付きます。

それは、「既存の素数をつかって、新たな素数をみつける、この操作が繰り返しできる。

このやり方が素数無限の初等的な証明でかなり有効に使われています。

たとえば、ユークリッドさん(その改定版)も、既存(既知)の素数\(p_1,p_2,p_3,…,p_n\)から、それらを全て掛け合わせて1を足した(引いた)数から、新しい素数を見つけています。つまり、

\[a_n=\prod_{i=1}^{n}p_i+1\]という数列から新しい(既存でない)素数を見つけています。

サイダックさんの証明は、\(a_1=2,a_{n+1}=a_n(a_n+1)\)という数列を考えると、\(a_n\)は素因数分解すると少なくともn個の素因数をもっている(\(a_nと(a_n+1\))は互いに素だから)。nはいくらでも増やせるから素因数は無限にあるということです。数列\(a_1=2,a_{n+1}=a_n(a_n+1)\)から新しい素数をみつけています。新しくみつかった素数がどういったものか具体的にはわかりませんが。

つまり、なんらかの式(数列)を考えて、その式から次々と新しい素数の存在を示すことができれば、素数が無限にあることが証明できるというわけです。

既存の素数から、それ以外の素数をみつける式、それが見つかれば、素数無限の証明が完成します。

さて、自分でも考えるぞ・・・意気込んだのはいいですが、そう簡単い見つかるわけ無いですね。

ユークリッドさんのパクリとして、\(a_n=p_{n-1}!-1\) こんなの考えました。新しくもなんともないですね、Wikipediaに類似が乗っていますし。悪しからず。

いろいろひねり出してみたのですが、気の利いたものは発見できずギブアップ!

 

苦肉の策でひねり出したのが下記の数列です。

\(a_1=2\)
\(a_2=3\)
\(a_3=5\)
これらは初期値として、また既知の素数の集合の列として
\(P_1=\{2\}\)
\(P_2=\{2,3\}\)
\(P_3=\{2,3,5\}\)
を考えます。

さらに、4以上のnに対しては、既知の素数の集合\(P_{n-1}\)の要素を小さい順に並べて
\(p_1<p_2<p_3<…<p_{n-1}\)とします。
\[a_n=\sum_{i=1}^n (-1)^{i+1}\frac{\prod_{j=1}^{n} {p_j}} {p_i}\]とし、
\(a_n\)の素因数のなかで\(P_{n-1}\)に含まれていない最小の素数が少なくとも1つは見つかるはずなのでそれをpとし、、
\[P_n=P_{n-1}\cup\{p\} \]として既知の素数の集合に追加します。

\( p_i \)を増加関数にしているのは、交代級数\(a_n\)の値が負にならないように調整するためです。

 

ユークリッドさんやサイダックさんの考えていた数列は、爆発的に大きくなっていくのですが、交代級数にすることで数列の増加を少し押さられたのではないかと思います。
※ここでの「爆発してる」という表現はあいまいな用語ですが指数的に大きくなるといった意味です。

 

数列をいろいろいじってすっきり感がないですが、下記の数列によって新しい素数が次々に見つかります。
これを私が考えた素数無限の新証明として勘弁してください。

\(a_1=2,P_1=\{2\}\)
\(a_2=3,P_2=\{2,3\}\)
\(a_3=5,P_3=\{2,3,5\}\)
\(a_4=11,P_4=\{2,3,5,11\}\)
\(a_5=91=7*13,P_5=\{2,3,5,7,11\}\)
\(a_6=727,P_6=\{2,3,5,7,11,727\}\)
\(a_7=526219=79*6661,P_7=\{2,3,5,7,11,79,727\}\)
\(a_8=40256911,P_7=\{2,3,5,7,11,79,727,40256911\}\)

こんな感じで新しい素数が次々と見つかっていきます。

素数を生成する式(関数)があれば、素数が無限にあることの証明ができます。

 

ところで、自然数nが与えられた時に、n番目の素数を表す式があるのでしょうか?

もし、そのような式があれば、その式を使った数列は無限に続くはずで、素数無限の証明に使えるはずです。

 

素数を生成する式(関数)

実は素数だけを生成する式はあります。それも、n番目の素数を表す式であります。

素数を表す式があることは、ウワサに聞いていましたが、しかし、実際に調べると、簡単にはみつかりませんでした。

下記は難しすぎてわかりませんが、なんだか将来性がありそうなのでリンク!
http://www.geocities.jp/ikuro_kotaro/koramu/481_f1.htm

そして、調べ続けいているうちについに発見!

発見といっても他の人が発見した素数式を発見したということです。

素数に関して超詳しいサイト(日本語です)があったので、紹介、つかリンク。
素数が無限の超詳しいサイト
素数を式だけであらわす

なんか、このサイトは凄すぎて足元にも及びません。素数に関しては、ここにおまかせしましょう。

このサイトの説明によると、素数が無限にあることの証明は170通り以上あるそうです。数え方にもよるでしょうが、歴史がある命題の事だけはあって証明も豊富ですね。