素数
素数(そすう、primeあるいはprime number)とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。
prime number の日本語への訳語を「素数」とすることは1881年(明治14年)に決まった。
一般には、素数は代数体の整数環の素元として定義される(そこでは反数などの同伴なものも素数に含まれる)。このため、有理整数環 \mathbb Z での素数は有理素数(ゆうりそすう、rational prime)と呼ばれることもある。1 は素数に含めない。
最小の素数は 2 である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。
素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。素数が無限に存在することは、次のように背理法で証明できる。
『いま、素数がn個しかなかったとして、それらの全ての素数を全部かけた積に1を足した数をmとする。ここで、mはどの素数で割っても余りが1となる。一方、mはどの素数よりも大きいので、mは素数ではない。すなわち、mはある素数で割り切れる。これは、mがどの素数で割っても余りが1となることに矛盾する。したがって、素数は無限にある。』
自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。
分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2021年4月現在で知られている最大の素数は、2018年12月7日に発見された、それまでに分かっている中で51番目のメルセンヌ素数 282589933 − 1 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ。
素数とは、自明な正の因数(1 と自分自身)以外に因数を持たない自然数であり、1 でない数のことである。つまり、正の因数の個数が 2 である自然数である。
例えば、2 は、正の因数が 1, 2 のみなので素数である。
素数でない 2 以上の自然数を合成数と呼ぶ。
下記の4条件どれかを満たす数は全て合成数である。
4以上の偶数。(2で割り切れる)
10以上で末尾が5か0の数。(5で割り切れる)
6以上で、数字根が3、6、9となる数(3で割り切れる)(21, 27, 33, 39, 51, 57, 63, 69, 81, 87, 93, 99, …)。
一の位から見て奇数番目の位の数の和と、偶数番目の位の数の和との差が11の倍数であれば、11の倍数である。(11で割り切れる)(100以上では、110,121,132,143,154,165,176,187,198,209, …)
逆に、この4条件を、全て満たさない数でも素数とは限らない。例えば、91 は、正の因数が 1, 7, 13, 91 なので素数ではない。
また、2, 3 以外の素数は、最も近い6の倍数との差が 1 か −1 である。
2 でない素数は奇数であり、奇素数と呼ぶ。
100以下の素数は25個存在し、小さい順に次の通りである。
さらに、1000以下の素数は100以下のものを含め168個存在する(100以下を除けば143個)。101以上で1000以下の素数は小さい順に次の通りである。
「2 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する(算術の基本定理)。素因数分解の可能性から、素数全体の成す集合は、2以上の自然数全体の成す集合とその乗法からなる半群の最小どの素数も他の自然数の積では表せないためこれ以上小さい生成系は存在しない。の生成系である。
素数の定義である「1 と自分自身でしか割り切れない」という条件(既約性)は、抽象代数学において、環の既約元の概念(一部の環では素元の概念と一致する)に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えばネーター環では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。
現代の定義では 1 は素数ではない。歴史を通しても 1 を素数に含めない数学者が多数派であったが、20世紀初頭の環論の成熟まで定義は統一されていなかった。プラトンやアリストテレスを含むほとんどの古代ギリシアの哲学者は 1 を数とさえ見なさず、素数性の考察の対象としなかった。スペウシッポスは 1 を数と見なし素数としたが、当時としては異端であった。この時代には素数を奇数の一部分と考え、 2 を素数に含めない数学者もいた(ただしユークリッドをはじめとする多数派は 2 を素数に含めている)。アラビアではおおむね古代ギリシアに倣って 1 は数でないとされた。中世からルネサンスにかけて、1 が数として扱われるようになり、1 を最初の素数とする数学者も現れた。18世紀半ば、ゴールドバッハはオイラーに宛てた書簡で 1 を素数に挙げている(ただしオイラー自身は 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 は素数ではなく「単数」という特別な分類に属するという見方が一般的になった。
紀元前1600年頃のエジプト第2中間期において、素数の初等的な性質が部分的に知られていたことが、リンド数学パピルスなどの資料によって示唆されている。例えば分数をエジプト式分数で表す場合、素数と合成数の場合で異なる計算をしなければならないからである。しかし、記録に残っている限りにおいて、明確に素数を研究対象としたのは古代ギリシア人が最初である。紀元前約300年頃に書かれたユークリッドの『原論』には素数が無数に存在することや、その他の素数の性質が証明されている。また、ユークリッドはメルセンヌ素数から完全数を構成する方法を示している。ギリシアの数学者、エラトステネスに因んで名付けられたエラトステネスの篩は、素数を列挙するための計算方法である。
古代ギリシア時代の後、17世紀になるまで素数の研究にはそれほどの進展が無かった。1640年に、ピエール・ド・フェルマーはフェルマーの小定理を(未証明ではあるが)述べた。この定理は後にライプニッツとオイラーによって証明された。
素数が無数に存在することは既に古代ギリシア時代から知られていて、ユークリッドが彼の著作『原論』の中で証明している。
『原論』第9巻 命題20
素数の個数はいかなる定められた素数の個数よりも多い。
定められた個数の素数を p1, p2, …, pn とせよ。p1, p2, …, pn より多い個数の素数があると主張する。
『原論』による証明
定められた素数の個数が n 個であるとき、n 個の素数を小さい順番に並べて i 番目の素数を pi とする。
このとき、n 個の素数をすべて掛け合わせた数に 1 を加えた数を q とすると、
q  p1 × p2 × … × pn + 1.
q は有限個の自然数の積に 1 を加えた数なので 1 より大きい自然数である。ゆえに、q は素数または合成数のどちらかである。
q が素数のとき、q は最大の素数 pn より大きい素数になるので、定められた個数の素数よりも多くの素数が存在する。
q が合成数のとき、q を割り切る素数が存在する。いっぽう、q の定義より、すべての pi で割った余りは 1 になるので、q はすべての pi で割り切れない。したがって、すべての pi 以外に素数が存在する。すなわち、定められた個数の素数よりも多くの素数が存在する。(証明終)
自然数の有限集合 A の全ての要素を掛け合わせた自然数を f(A) とする。
定められた個数の素数から成る集合を A3  {2, 3, 5}  とするとき、f(A3) = 2 × 3 × 5 + 1 = 31 は素数なので、新しい素数 31 が得られる。したがって、定められた個数より多くの素数が存在する。
定められた個数の素数から成る集合を A4  {2, 3, 5, 31}  とするとき、f(A4) = 2 × 3 × 5 × 31 + 1 = 931  7 × 7 × 19 なので、新しい素数 7 と 19 が得られる。したがって、定められた個数より多くの素数が存在する。
上記のユークリッドによる証明以外にも、素数が無数に存在することの証明方法が存在する。
素数の逆数の和が発散することを利用した証明(#素数の逆数和を参照)
整数の集合に、等差数列の族を開基とする位相を入れる証明
n ≥ 2 に対して、n(n + 1) は少なくとも相異なる2個の素因数を持つことを利用した証明。おそらく最も短い証明。
与えられた自然数 n が素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。最も素朴な方法は、2 から n 以下の素数まで順番に割っていく、試し割り法と呼ばれる方法である。n が n 以下の全ての素数で割り切れなければ n は素数である。試し割り法は、n が大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割り法よりも高速なアルゴリズムが考案されている。また、特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。
上記の通り2を除く偶数、2桁以上で末尾が5の数、数字和が3の倍数となる数は合成数と分かるのでそれを省き、7以上の素数を順番に割る方法がある。
ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。
これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。
x 以下の素数の個数を π(x)(素数計数関数)とすると、
\pi (x)\sim \int_2^x \frac{dt}{\log t} \sim \frac{x}{\log x}\quad (x\to \infty)
が成り立つ。この定理は、1792年に15歳のカール・フリードリヒ・ガウスによって予想されていた(ガウスが最初に予想したのかどうかは不明)。この定理の証明は、ゼータ関数と複素関数論を用いる高度なものであったが、1949年にアトル・セルバーグとポール・エルデシュは独立に初等的な証明を与えた。この評価式はリーマン予想を仮定すると大幅に精度をよくすることができる。
次のような定理もある。
「任意の自然数 n に対して、n < p ≤ 2n を満たす素数 p が存在する」(ベルトランの仮説、チェビシェフの定理)
この主張は「任意の素数 p の次の素数は 2p 未満」とも言い換えられる。したがって、2017年5月現在知られている最大の素数 282589933 − 1 の次の素数は 282589934 − 2 未満である。
一方で、例えば n2 と (n + 1)2 の間に素数が存在するかという問題は未解決である(ルジャンドル予想)。
素数が全く無い区間は、いくらでも長いものがあることが知られている。n ≥ 2 に対して、連続する n − 1 個の自然数 n! + 2, …, n! + n はそれぞれ、それらより小さい 2, …, n で割り切れるので、どれも素数でない。n は任意にとれるから、素数が全く無いいくらでも長い区間があると言える。これは一例にすぎず、実際にはもっと小さい所で、素数が全く無い長い区間が生じるようである。例えば、114 から 126 まで13個連続で合成数である。
2015年に、ゴールドバッハの予想検証プロジェクトは 4 × 1018 以下の全ての素数(9京5676兆2609億0388万7607個、約 1017個)を計算したと報告したが、結果は保存されていない。しかしながら、素数計数関数を計算するには、実際に素数を数えるより高速な公式が存在する。この公式を使って、1023 以下に 19垓2532京0391兆6068億0396万8923個(約 221個)の素数があると計算された。
また、別の計算によると、リーマン予想が真であると仮定した場合、1024 以下に 184垓3559京9767兆3492億0086万7866個(約 222個)の素数が存在する。
素数の逆数の和は(無限大に)発散する。この命題は『素数は無数に存在する』という命題を含んでいる(有限個ならば収束、すなわち発散しないはずである)が、それだけではなく素数の分布に関してより多くの情報を提供している。
この結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。以下の証明はポール・エルデシュによる、より直接的で、また簡潔な証明である。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。
素数の逆数和は収束すると仮定する。i 番目の素数を pi で表すと、
\sum_{i=N+1}^\infty \frac{1}{p_i} <\frac{1}{2} \cdots (1)
を満たす N が存在する。
n 以下の自然数のうち最大素因数が pN 以下のものからなる集合を An とする。任意の k ∈ An に対して、
k  u2v(v の各素因数の指数は全て 1)
と表示すると、v は高々 2N 通り、u2 ≤ k ≤ n より
#An ≤ 2Nn …(2)
Anc の元は、pN+1 以上の素因数を少なくとも1つ持つから、(1) より
\# {A_n}^c \le \sum_{i=N+1}^\infty \left[ \frac{n}{p_i} \right] \le n\sum_{i=N+1}^\infty \frac{1}{p_i} <\frac{n}{2}
#Anc  n − #An より
n < #An …(3)
(2), (3) より n < 2N n, ∴ n < 22N+2。これは n の任意性に矛盾。(証明終)
双子素数に限ると、逆数和は B2  1.902… に収束することが証明されている(ブルン定数)。
(a, m)  1 のとき、等差数列:a, a + m, a + 2m, … には素数の項が無数に含まれている。(ディリクレの算術級数定理)
ここで m  10 とすると、十進表記において一の位が 1, 3, 7, 9 である素数はどれも無数にあることが分かる。
素数 p に対して、(a, p)  1 ⇒ ap−1 ≡ 1 (mod p)(フェルマーの小定理)
p が素数 ⇔ (p − 1)! ≡ −1 (mod p)(ウィルソンの定理)
素数の2乗差は 5 の倍数, 3 の倍数, 8 の倍数のいずれかである。
約数の和が素数になる自然数は、2 と素数かその累乗数の平方数である。しかし、素数やその累乗数の自乗であっても約数の和が素数になるとは限らない。約数の和が素数になる数が無限にあるかどうかの証明はされていない(後述)。
七進表記において、5以上の素数の数字根は、必ず1か5となる。
n 番目の素数を求める素数生成式は存在しないと主張されることがあるが、これは誤りである(ウィルソンの定理やミルズの定理を用いたものが存在する)。しかしながら、そのような式で実効的に計算可能なものは知られていない。
オイラーの発見した式:
は、自然数 n が n < 41 で全て素数となる。これは、虚二次体 \mathbb{Q}(\sqrt{-163}) の類数が 1 であることと関係している。一般に、0 ≤ n < p で多項式 f(n)  n2 − n + p が素数の値を取るとき、素数 p の値を「オイラーの幸運数」という。オイラーの幸運数は p  2, 3, 5, 11, 17, 41 の6つのみであり、これらはすべてヘーグナー数と対応する。
ルビーの多項式:
は n  0, …, 44 で全て素数となる。
103n2 − 3945n + 34891 (Ruby)
47n2 − 1701n + 10181 (Fung)
は n  0, …, 42 で全て素数となる。
36n2 − 2358n + 36809 (Willium)
は n  0, …, 44 で絶対値は全て素数となる。
n3 − 34n2 + 381n − 1511 (Goetgheluck)
2n3 − 45n2 + 331n − 3191 (Goetgheluck)
は n  0, …, 25 で絶対値は全て素数となる。
ただし n3 − 34n2 + 381n − 1511 の n  9, 12, 13 で −107 を取るなど、同じ素数が何度も出現する場合がある。
多変数の多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、k + 2 が素数となる必要十分条件は、次のディオファントス方程式が自然数解を持つことである:
メルセンヌ素数:2n − 1(n は素数が必要、n  2, 3, 5, 7, 13, …)
フェルマー素数:22n + 1
オイラー素数:n2 + n + 41
素数階乗素数:p# ± 1(p は素数、p# は p の素数階乗)
レピュニット R2, R19, R23, …(Rn は 1 が n 個続く数、通常は基数を 10 にとる)
双子素数(差が 2 である2つの素数)
いとこ素数(差が 4 である2つの素数)
セクシー素数(差が 6 である2つの素数)
三つ子素数(3つの素数の組 (p, p + 2, p + 6) または (p, p + 4, p + 6)((p, p + 2, p + 4)型は (3, 5, 7) のみ。)
四つ子素数(p, p + 2, p + 6, p + 8 が全て素数)
ソフィー・ジェルマン素数(p と 2p + 1 がともに素数である時の p のこと)
安全素数(p と 2p + 1 がともに素数である時の 2p + 1 のこと)
スーパー素数(素数列における素数番目の素数)
切り捨て可能素数(与えられた基数において 0 を含まず、左右から数を取っていった数がすべて素数である素数)
陳素数(p + 2 が半素数またはともに素数)
正則素数(円の p 分体の類数を割り切らない奇素数)
非正則素数(円の p 分体の類数を割り切る奇素数)
フィボナッチ素数(フィボナッチ数の数列に含まれる素数)
ヴィーヘリッヒ素数 (2p-1 ≡ 1 (mod p2) を満たす素数 p)
ある数の約数の和になる素数:3, 7, 13, 31, 127, 307, 1093, …
双子素数の予想:双子素数は無数に存在する、という予想。
ゴールドバッハの予想:6 以上の全ての偶数は 2 つの奇素数の和で表すことができる、という予想。
弱いゴールドバッハ予想:7 以上の全ての奇数は 3 つの素数の和で表すことができる、という予想。ただしハラルド・ヘルフゴットによる証明が2013年に発表されている。
ルジャンドル予想:全ての n に対し、n2 と (n + 1)2 の間に素数が存在するかという予想。
既知のフェルマー素数以外に、フェルマー数にフェルマー素数は存在するか?
メルセンヌ素数は無数に存在するか?
ソフィー・ジェルマン素数、安全素数は無数に存在するか?
フィボナッチ数列には、素数である項が無数に現れるか?(フィボナッチ素数)
幸運数でも素数でもあるような数は無数に存在するか?
ハッピー素数は無数に存在するか?
n2 + 1 の形の素数は無数に存在するか?(ブニャコフスキー予想)
約数の和の列になる素数は無数に存在するか?
長い間、数論、その中でもとりわけ素数に関する研究は、その分野以外での応用の全くない純粋数学の見本と見なされていた。特に、イギリスの数論研究者であるハーディは、自身の研究が軍事的に何の重要性も持たないことを誇っていた。しかし、この見方は1970年代には覆されてしまった。素数が公開鍵暗号のアルゴリズムに使用できると広く知られるようになったためである。現在では素数はハッシュテーブルや擬似乱数生成にも用いられ、工学的応用上重要度の高いものとなっている。
公開鍵暗号のアルゴリズムとして、RSA暗号やディフィー・ヘルマン鍵共有といった、大きな数の素因数分解は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの(大きな)素数の掛け算は比較的簡単に(効率的に)行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。
自然界に現れる素数の一例として、素数ゼミと呼ばれるセミの一種がいる。アメリカ合衆国に分布するこのセミの成虫は、ある周期ごとに、13年ないしは17年間の周期で大量発生する。成虫になった後は、数週間だけを地上で成虫として過ごし交配と産卵を行う。このセミが素数周期で発生する理由として、寄生虫や捕食者に対抗するための進化であるという説や近縁種との交雑を避けるためであるという説がある。つまり、もしこのセミが12年の発生周期を持っていた場合、12の約数である2, 3, 4, 6年の寿命を持つ捕食者と同時に発生してしまうことになり、捕食対象にされやすくなる。また、地理的に近い場所で12年周期と15年周期のセミが存在した場合、60年ごとに2種は同時に発生し、交雑してしまう可能性がある。すると、雑種は発生周期がずれてしまい、同種のセミとの交尾の機会が失われる。素数の周期を持つものは交雑が起こりにくく、淘汰されにくいと考えられる。
また、ゼータ関数上の零点の分布の数式が、原子核のエネルギー間隔を表す式と一致することを示し、素数と核物理現象との関連性が示唆されている。
自然数で素数でないものが連続している区間を「素数砂漠」という。例えば{24, 25, 26, 27, 28) は「長さ 5 の素数砂漠」である。素数砂漠を挟む2個の素数は 3 以上であるため、共に奇数である。このことから、素数砂漠の長さは必ず奇数である。いくらでも長い素数砂漠が構成できる(#分布を参照)。
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, …
1、2桁の素数の暗記方法として、次のような語呂合わせが考え出されている。
素数の一般項で、よく知られているものは、
p(n)=1+ \textstyle\sum\limits_{m=1}^{2^n} \left\lfloor \left( \dfrac{n}{\sum\limits_{k=1}^m \lfloor \cos ^{2}\frac{\left( n-1 \right)! +1}{k} n \rfloor }\right)^\frac{1}{n} \right\rfloor