高校数学

【素数】全ての素数の和とは?【素数を見つけるアルゴリズム】

ユキ
ユキ
どうも,ユキです。

素な人です(一人身という意味です)

ということで、素な数「素数」についての記事です。

理系が大好きなワードですね。

今回の記事を読むメリット

・素数がわかる

・素数を見つけるアルゴリズムがわかる

・すべての素数の和がわかる

素数とは

1と自分自身以外に約数を持たない(その数でしか割れない)自然数(正の整数)のことを言います。

いいかえると、約数を2つしかもたない自然数のことです。

素数の例:235

2の約数は123の約数は135の約数は15

 

素数ではない例:4915

4の約数は1249の約数は13915の約数は13515

などがあります。

ユキ
ユキ
素数は寂しいですね…

素因数分解とは

ある数を素数のかけ算で表すことをいいます。

素因数分解の例

4の素因数分解    

4=2×2

15の素因数分解

15=3×5

360の素因数分解

360=2×2×2×3×3×5

素数をどうやって見つける?

手計算や,目視で素数を見つけることはある程度までなら人の力で可能ですが,桁数が多くなると,人の力では困難です。

ですので,素数はC言語などをつかってコンピュータに命令を送って,コンピュータに見つけさせます。

素数を見つけるアルゴリズム

最も簡単な方法は,\(2,3,4,5\dots\)と順番に見ていくことです。

これは,C言語やJavaの教科書にもでてくるエラトステネスのふるいという方法です。

この方法は,一見簡単にプログラムできますが,無駄な計算が多いです。なので,エラトステネスのふるいを改良して使う必要があります。

具体的には,偶数は2以外は素数ではないので、奇数だけを見ていくアルゴリズムを使います。

例えば、\(2,3,4,5,6,7\dots\)と見ていく動作を\(2,3,5,7,9,11\dots\)としてあげることで,素数を見つける時間を半分に短縮できます。

素因数分解を使った暗号【RSA暗号】

RSA暗号とは,桁数が大きい素因数分解問題を解くことは難しい性質を利用して作られた公開鍵暗号です。

公開鍵は,「サマーウォーズ」でいうと,2056桁の暗号文です。

つまり,みんなが見ることが出来る鍵のことをいいます。

素数は無限に存在する?

まず,事実として知っておいて欲しい等式が3つあります。

$$\sum_{k=1}^{\infty}\frac{1}{n}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\dots+\frac{1}{n}+\dots=\infty$$

$$\sum_{p:prime}\frac{1}{p}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\dots=\infty$$

$$\sum_{k=1}^{\infty}\frac{1}{2^{n-1}}=\frac{1}{1}+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}\dots+\frac{1}{2^{n-1}}+\dots=2$$

 

ここで,nは自然数,pは素数を表しています

逆数和で和が無限大になる理由は,n(自然数)p(素数)無限個存在するからです。この命題は成り立っていますが,逆は成り立っていません。つまり,数字が無限個存在するから

といって,逆数和が無限大になるとは限らないです。3番目の式がそれを示しています。

 

この3つの等式から,上2つの式が無限になって,3番目の式が唯一2という実数に落ち着いています。

ここで,注目して欲しいのが数字の間隔です。一番上の式のn1ずつ間隔があいています。3番目の式は,n1,2,4,8と間隔がかなり広いです。

 

2番目の式のpは不規則な間隔だが,1番上の式よりは,間隔は広く,3番目の式よりは間隔が狭いのでしょう。

何が言いたいのかというと,数字の間隔が詰まっているものは,12番目の式のように無限大になり,逆に,数字の間隔が詰まっていない逆数和は3番目の式のように収束します。

双子素数は無限に存在する?

p,p+2が素数のとき,(p,p+2)双子素数といいます。(3,5)(5,7)(11,13)などが双子素数です。

実は,この問題は未解決です。では,双子素数の和はどうなっているのでしょう。もしも,無限大ならば,先ほどの命題どおり,双子素数は無限個存在するといえます。

$$\sum_{p}\frac{1}{p}+\frac{1}{p+2}=(\frac{1}{3}+\frac{1}{5})+(\frac{1}{5}+\frac{1}{7})+(\frac{1}{11}+\frac{1}{13})+\dots=??$$

実は,双子素数の和は有理数か無理数かはわかりませんが,収束することが知られています。

だいたい1.9くらい(ブルン定数)になるそうです。(もしも無理数であれば,双子素数は無限個存在するとわかります。)

現状では,双子素数は有限個か無限個かわからないと言う話をしましたが,\(p_{n+1}-p_{n}<=246\)となる素数は,無限個存在するということがわかっています。

これを\(p_{n+1}-p_{n}=2\)まで,縮めることが今後の数学者の課題となっています。

双子素数以外の数もこちらの記事で紹介しています。

 https://cupuasu.club/math-perfect-number/

全ての素数の積が偶数でも奇数でもないって本当?

全ての素数の積は,

$$\prod_{p:prime}p=2\times3\times5\times7\times\dots=4\pi^2$$

となります。(最初に2をかけてるから偶数っぽさそうですけどね)

これは、ある条件下では正しいです。$$4\pi^2$$の証明は、この記事がわかりやすかったので掲載しておきます。

http://solidstatephysics.blog.fc2.com/blog-entry-25.html

でも、その条件を無視すると、この等式は大きな矛盾点をはらんでいます。

$$2\times3\times5\times7>4\pi^2$$

その矛盾点は、素数を7まで掛けた時点で右辺を上回ってしまう点です。

実は,数字というのは,無限大になるとおかしくなるのです。(これが偶数ではない理由だよ)

おかしくなる原因は,解析接続というチート技があるのですが、別の記事で取り上げます。

ゼータ関数と素数

ζ(ゼータ)関数は,

$$\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s}=1+\frac{1}{2^s}+\frac{1}{3^s}+\dots $$

で表される\(\zeta\)のことを言います。また,\(\zeta\)関数と素数には密接な関係があります。

$$\zeta(s)=\prod_{p:prime}\frac{1}{1-p^{-s}}=\frac{1}{1-2^{-s}}\frac{1}{1-3^{-s}}\frac{1}{1-5^{-s}}\dots$$

これをオイラー積といいます。でも,オイラー積とゼータ関数が結びつかないとおもうので,

オイラー積を式変形します。\(\frac{1}{1-p^{-s}}\)について,等比級数の公式を使うと,

 

$$\frac{1}{1-p^{-s}}=\sum_{0}^{\infty}=1+p^{-s}+p^{-2s}+p^{-3s}+\dots$$

よって,\(\zeta(s)\)は,

$$\zeta(s)=\prod_{p:prime}1+p^{-s}+p^{-2s}+p^{-3s}+\dots $$

となるので,大きい項から順に書き下すと,

$$\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^s}$$

$$=1+2^{-s}+3^{-s}+\dots$$

$$=\sum_{n=1}^{\infty} \frac{1}{n^s}$$

となり,ゼータ関数とオイラー積は同一の式であることがわかります。

素数のまとめ

素数のまとめ

・素数とは、1と自分自身以外に約数を持たない(その数でしか割れない)自然数(正の整数)のこと

・素数を見つけるためのアルゴリズムは「エラトステネスのふるい」

・素数を全て足すと、偶数でも奇数でもない無理数になる

・ゼータ関数とオイラー積は同一の式である

最後に

お気づきでしたでしょうか?

今回扱っている画像の数字は全て素数でした!

茶番はさておき、素数が無限にあるということで、覚えてもきりがありません。

また、素数判定のアルゴリズムはエラトステネスだけで無く、確率的に判定するものもあってやっかいです。

さらには、shorのアルゴリズムという行列式やフーリエ変換を用いたやっかいなアルゴリズムもあります。

ABOUT ME
ユキ
数学担当です。お金大好き大学生やってます。 講義がないときは、だいたい図書館にいるので図書館の門番とも呼ばれています。 L・O・V・E ラブリー マネー!