素数

素数とは、2}} 以上の自然数で、正の約数が 1}} と自分自身のみであるもののことである。正の約数の個数が 2}} である自然数と言い換えることもできる。1}} より大きい自然数で素数でないものは合成数と呼ばれる。

日本では、prime number}} の日本語への訳語は「素数」とすることが1881年に決まった。

一般には、素数は代数体の整数環の素元として定義される。このため、有理整数環 での素数は有理素数と呼ばれることもある。

最小の素数は 2}} である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,…}}素数が無数に存在することは、紀元前3世紀頃のエウクレイデスの著書『原論』で既に証明されていた。そこでの証明は、背理法により次のようになる：

『素数全体は有限個と仮定して、全ての素数の総乗に1を足した数をNとする。Nはどの素数で割っても余りが1となる。一方、Nはどの素数よりも大きいので、Nは素数ではない。すなわち、Nはある素数で割り切れる。これは、Nを整数で割った余りが一意であることに矛盾する。ゆえに、素数は無数にある。』自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。

分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2021年4月現在で知られている最大の素数は、2018年12月7日に発見された、それまでに分かっている中で51番目のメルセンヌ素数 2sup であり、十進法で表記したときの桁数は2486万2048桁に及ぶ。

1. 定義と例
-------

素数とは、自明な正の因数以外に因数を持たない自然数であり、1}} でない数のことである。つまり、正の因数の個数が 2 である自然数である。

例えば、2}} は、正の因数が 1, 2}} のみなので素数である。

素数でない 2}} 以上の自然数を合成数と呼ぶ。

合成数であることの判定法として、たとえば下記の4条件がある：

4以上の偶数。
10以上で末尾が5か0の数。
6以上で、数字根が3, 6, 9となる数。
一の位から見て奇数番目の位の数の和と、偶数番目の位の数の和との差が11の倍数であれば、11の倍数である。逆に、この4条件を、全て満たさない数でも素数とは限らない。例えば、91}} は、正の因数が 1, 7, 13, 91}} なので素数ではない。

また、2, 3}} 以外の素数は、最も近い6の倍数との差が 1}} か −1}} である。

2}} でない素数は奇数であり、奇素数と呼ぶ。

100以下の素数は25個存在し、小さい順に次の通りである。

さらに、1000以下の素数は100以下のものを含め168個存在する。101以上で1000以下の素数は小さい順に次の通りである。

2. 素因数分解の可能性・一意性
----------------

「2}} 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する。素因数分解の可能性から、素数全体の成す集合は、2以上の自然数全体の成す集合とその乗法からなる半群の最小どの素数も他の自然数の積では表せないためこれ以上小さい生成系は存在しない。}}の生成系である。言い換えれば、これは「素数は自然数の構成要素である」などとなる。

素数の定義である「1}} と自分自身でしか割り切れない」という条件は、抽象代数学において、環の既約元の概念に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えばネーター環では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。

2.1. 1 は素数か
-----------

現代の定義では 1}} は素数ではない。歴史を通しても 1}} を素数に含めない数学者が多数派であったが、20世紀初頭の環論の成熟まで定義は統一されていなかった。プラトンやアリストテレスを含むほとんどの古代ギリシアの哲学者は 1}} を数とさえ見なさず、素数性の考察の対象としなかった。スペウシッポスは 1}} を数と見なし素数としたが、当時としては異端であった。この時代には素数を奇数の一部分と考え、2}} を素数に含めない数学者もいた。アラビアではおおむね古代ギリシアに倣って 1}} は数でないとされた。中世からルネサンスにかけて、1}} が数として扱われるようになり、1}} を最初の素数とする数学者も現れた。18世紀半ば、ゴールドバッハはオイラーに宛てた書簡で 1}} を素数に挙げている。19世紀にも少数派だが 1}} を素数に含める数学者はかなりいた。ハーディの『A Course of Pure Mathematics』では、1933年に出版された第6版までは 1}} を素数に含めているが、1938年の第7版から 2}} を最小の素数とするよう改訂されている。デリック・ノーマン・レーマーの 1}} を含む素数表は1956年まで出版された。ルベーグは 1}} を素数だと考えた最後の専門的な数学者だと言われている。

1}} も素数と定義すると、素数に関する多くの定理で、もとの「素数」を「1}} 以外の素数」と呼び替える記述の修正が必要になる。例えば 6}} の素因数分解は、

と無数に与えられることになり、一意性は「1}} を含む素数」については成り立たない。エラトステネスの篩においては、1}} も素数とすると、1}} の倍数を消去し、残った唯一の数 1}} を出力するので機能しない。さらに、1}} 以外の素数で成り立つ様々な性質がある。20世紀初頭までに 1}} は素数ではなく「単数」という特別な分類に属するという見方が一般的になった。

3. 歴史
-----

紀元前1600年頃のエジプト第2中間期において、素数の初等的な性質が部分的に知られていたことが、リンド数学パピルスなどの資料によって示唆されている。例えば分数をエジプト式分数で表す場合、素数と合成数の場合で異なる計算をしなければならないからである。しかし、記録に残っている限りにおいて、明確に素数を研究対象としたのは古代ギリシア人が最初である。紀元前約300年頃に書かれたユークリッドの『原論』には素数が無数に存在することや、その他の素数の性質が証明されている。また、ユークリッドはメルセンヌ素数から完全数を構成する方法を示している。ギリシアの数学者、エラトステネスに因んで名付けられたエラトステネスの篩は、素数を列挙するための計算方法である。

古代ギリシア時代の後、17世紀になるまで素数の研究にはそれほどの進展が無かった。1640年に、ピエール・ド・フェルマーはフェルマーの小定理を述べた。この定理は後にライプニッツとオイラーによって証明された。 素数が無数に存在することは既に古代ギリシア時代から知られていて、ユークリッドが彼の著作『原論』の中で証明している。

3.1. ユークリッドによる証明
----------------

『原論』第9巻 命題20素数の個数はいかなる定められた素数の個数よりも多い。定められた個数の素数を //p//sub とせよ。//p//sub より多い個数の素数があると主張する。『原論』による証明定められた素数の個数が n}} 個であるとき、n}} 個の素数を小さい順番に並べて i}} 番目の素数を psub とする。このとき、n}} 個の素数をすべて掛け合わせた数に 1}} を加えた数を q}} とすると、//q// =}} //p//sub.q}} は有限個の自然数の積に 1}} を加えた数なので 1}} より大きい自然数である。ゆえに、q}} は素数または合成数のどちらかである。q}} が素数のとき、q}} は最大の素数 psub より大きい素数になるので、定められた個数の素数よりも多くの素数が存在する。q}} が合成数のとき、q}} を割り切る素数が存在する。一方、q}} の定義より、すべての psub で割った余りは 1}} になるので、q}} はすべての psub で割り切れない。したがって、すべての psub 以外に素数が存在する。すなわち、定められた個数の素数よりも多くの素数が存在する。例自然数の有限集合 A}} の全ての要素を掛け合わせた自然数を //f//}} とする。定められた個数の素数から成る集合を //A//sub とするとき、1=//f//(//A//sub は素数なので、新しい素数 31}} が得られる。したがって、定められた個数より多くの素数が存在する。定められた個数の素数から成る集合を //A//sub とするとき、1=//f//(//A//sub なので、新しい素数 7}} と 19}} が得られる。したがって、定められた個数より多くの素数が存在する。

3.2. 他の証明
---------

上記のユークリッドによる証明以外にも、素数が無数に存在することの証明方法が存在する。

素数の逆数の和が発散することを利用した証明group=注釈
2つの異なるフェルマー数が互いに素であることを利用した証明
整数の集合に、等差数列の族を開基とする位相を入れる証明
//n// ≥ 2}} に対して、//n//}} は少なくとも相異なる2個の素因数を持つことを利用した証明group=注釈。おそらく最も短い証明。

4. 素数判定と素因数分解
-------------

与えられた自然数 n}} が素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。最も素朴な方法は、2}} から sqrt 以下の素数まで順番に割っていく、試し割り法と呼ばれる方法である。n}} が sqrt 以下の全ての素数で割り切れなければ n}} は素数である。試し割り法は、n}} が大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割り法よりも高速なアルゴリズムが考案されている。また、特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。

上記の通り2を除く偶数、2桁以上で末尾が5の数、数字和が3の倍数となる数は合成数と分かるのでそれを省き、7以上の素数を順番に割る方法がある。

5. 分布
-----

ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。 これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。

x}} 以下の素数の個数を π}}}}とすると、

が成り立つ。この定理は、1792年に15歳のカール・フリードリヒ・ガウスによって予想されていた。この定理の証明は、ゼータ関数と複素関数論を用いる高度なものであったが、1949年にアトル・セルバーグとポール・エルデシュは独立に初等的な証明を与えた。この評価式はリーマン予想を仮定すると大幅に精度をよくすることができる。

次のような定理もある。

「任意の自然数 n}} に対して、//n// < //p// ≤ 2//n//}} を満たす素数 p}} が存在する」この主張は「任意の素数 p}} の次の素数は 2//p//}} 未満」とも言い換えられる。したがって、2017年5月現在知られている最大の素数 2sup の次の素数は 2sup 未満である。

一方で、例えば //n//sup と sup の間に素数が存在するかという問題は未解決である。

素数が全く無い区間は、いくらでも長いものがあることが知られている。//n// ≥ 2}} に対して、連続する //n// − 1}} 個の自然数 //n//[[階乗 はそれぞれ、それらより小さい 2, …, //n//}} で割り切れるので、どれも素数でない。n}} は任意にとれるから、素数が全く無いいくらでも長い区間があると言える。これは一例にすぎず、実際にはもっと小さい所で、素数が全く無い長い区間が生じるようである。例えば、114}} から 126}} まで13}}個連続で合成数である。

5.1. 素数計数
---------

2015年に、ゴールドバッハの予想検証プロジェクトは 4 × 10sup 以下の全ての素数を計算したと報告したが、結果は保存されていない。しかしながら、素数計数関数を計算するには、実際に素数を数えるより高速な公式が存在する。この公式を使って、10sup 以下に 19垓2532京391兆6068億396万8923個の素数があると計算された。

また、別の計算によると、リーマン予想が真であると仮定した場合、10sup 以下に 184垓3559京9767兆3492億00}}86万7866個の素数が存在する。

5.2. 分布の視覚化
-----------

エラトステネスの篩
ウラムの螺旋
プリヒタの素数円

6. 素数に関連する主な性質
--------------

6.1. 素数の逆数和
-----------

素数の逆数の和は発散する。この命題は『素数は無数に存在する』という命題を含んでいるが、それだけではなく素数の分布に関してより多くの情報を提供している。

この結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。以下の証明はポール・エルデシュによる、より直接的で、また簡潔な証明であるgroup=注釈。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。

エルデシュによる証明素数の逆数和は収束すると仮定する。i}} 番目の素数を psub で表すと、

を満たす N}} が存在する。

n}} 以下の自然数のうち最大素因数が psub 以下のものからなる集合を Asub とする。任意の //k// ∈ //Asub に対して、//

//k// =}} //u//supと表示すると、v}} は高々 2sup 通り、//u//sup より

//Asub …//Asub の元は、//p//sub 以上の素因数を少なくとも1つ持つから、 より

//Asub より//sfrac …,  より sfrac, ∴ //n// < 2sup。これは n}} の任意性に矛盾。

双子素数に限ると、逆数和は //B//sub に収束することが証明されている。

6.2. その他の性質
-----------

 =}} 1}} のとき、等差数列：//a//, //a// + //m//, //a// + 2//m//, …}} には素数の項が無数に含まれている。ここで //m// =}} 10}} とすると、十進表記において一の位が 1, 3, 7, 9}} である素数はどれも無数にあることが分かる。
素数 p}} に対して、 =}} 1 ⇒ //a//sup
p}} が素数 ⇔ ! ≡ −1 }}
素数の2乗差は 5}} の倍数, 3}} の倍数, 8}} の倍数のいずれかである。
約数の和が素数になる自然数は、2}} と素数かその累乗数の平方数である。しかし、素数やその累乗数の自乗であっても約数の和が素数になるとは限らない。約数の和が素数になる数が無限にあるかどうかの証明はされていない。
七進表記において、5以上の素数の数字根は、必ず1か5となる。

7. 素数生成式
--------

n}}番目の素数を求める素数生成式は存在しないと主張されることがあるが、これは誤りである。しかしながら、そのような式で実効的に計算可能なものは知られていない。

以下は1964年に Willans C.P. が報告したウィルソンの定理に基づく公式で、n}}番目の素数 psub を求めることができる：

7.1. 1変数多項式
-----------

オイラーの発見した式：

は、自然数 n}} が //n// < 41}} で全て素数となる。これは、虚二次体 の類数が 1}} であることと関係している。一般に、0 ≤ //n// < //p//}} で多項式 //f// =}} //n//sup が素数の値を取るとき、素数 p}} の値を「オイラーの幸運数」という。オイラーの幸運数は //p// =}} 2, 3, 5, 11, 17, 41}} の6つのみであり、これらはすべてヘーグナー数と対応する。

ルビーの多項式：

は //n// =}} 0, …, 44}} で全て素数となる。 同様に

103//n//sup 
47//n//sup は //n// =}} 0, …, 42}} で全て素数となる。

36//n//sup は //n// =}} 0, …, 44}} で絶対値は全て素数となる。

高い次数での多項式はあまり知られていないが

//n//sup 
2//n//sup は //n// =}} 0, …, 25}} で絶対値は全て素数となる。 ただし //n//sup の //n// =}} 9, 12, 13}} で −107}} を取るなど、同じ素数が何度も出現する場合がある。

7.2. 多変数多項式
-----------

多変数の多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、//k// + 2}} が素数となる必要十分条件は、次のディオファントス方程式が自然数解を持つことである：

//z// + //pl// + //t//(2//ap// − //p//sup

8. 特殊な形をした素数
------------

メルセンヌ素数：2sup
フェルマー素数：
オイラー素数：
階乗素数
//n//! + 1}}型
//n//! − 1}}型
素数階乗素数：//p//# ± 1}}
レピュニット //R//sub
双子素数
いとこ素数
セクシー素数
三つ子素数