素数

素数（そすう、英: prime あるいは prime number）とは、2 以上の自然数で、正の約数が 1 とその整数自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。

日本では、英: prime number の日本語への訳語は「素数」とすることが1881年（明治14年）に決まった^[1][2]。和算では素数のことを単数と呼んでいた^[3]。

一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環 ${\displaystyle \mathbb {Z} }$ での素数は有理素数（ゆうりそすう、英: rational prime）と呼ばれることもある。

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

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を素数で割った余りが1であることに矛盾する。ゆえに、素数は無数にある。』

自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。

分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。現在知られている最大の素数は、2024年10月12日に発見された、それまでに分かっている中で52番目のメルセンヌ素数 2^136279841 − 1 であり、十進法で表記したときの桁数は4102万4320桁に及ぶ^[5][6]。

定義と例

100 以下の素数一覧
	02	3	00	05	00	7	00		00
11		13				17		19
		23						29
31						37
41		43				47
		53						59
61						67
71		73						79
		83						89
						97

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

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

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

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

• 4以上の偶数。（2で割り切れる）
• 10以上で末尾が5か0の数。（5で割り切れる）
• 6以上で、数字根が3, 6, 9となる数（3で割り切れる）。（20以上では、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, …）^[7]

逆に、この4条件を、全て満たさない数でも素数とは限らない。例えば、91 は、正の因数が 1, 7, 13, 91 なので素数ではない。

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

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

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

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

→詳細は「素数の一覧」を参照

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

→詳細は「算術の基本定理」を参照

「2 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する（算術の基本定理）。素因数分解の可能性から、素数全体の成す集合は、2以上の自然数全体の成す集合とその乗法からなる半群の最小^{[注釈 1]}の生成系である。言い換えれば、これは「素数は自然数の構成要素である」などとなる^[8]。

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

1 は素数か

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

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

6 = 2 × 3 = 1 × 2 × 3 = 1² × 2 × 3 = 1³ × 2 × 3 = …

と無数に与えられることになり、自然数の素因数分解の一意性は「1 を素数に含めると」成り立たなくなる^[9]。エラトステネスの篩においては、1 も素数とすると、1 の倍数（すなわち他のすべての数）を消去し、残った唯一の数 1 を出力するので機能しない^[17]。さらに、1 以外の素数で成り立つ様々な性質がある（例えば、自然数とそれに対応するオイラーのφ関数や約数関数の値との関係など）^[18][19][20]。20世紀初頭までに 1 は素数ではなく「単数」という特別な分類に属するという見方が一般的になった^[9]。

歴史

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

古代ギリシア時代の後、17世紀頃までの長い間、素数の研究にはあまり進展が見られなかった。1640年に、ピエール・ド・フェルマーは「フェルマーの小定理」を述べた（未証明）。この定理は後にライプニッツとオイラーによって証明された。

自然数を渦巻状に並べていき、素数だけを黒く塗ったもの（ウラムの螺旋）。
素数が高密度に集まった対角線、水平線、垂線が見て取れる。素数の分布が極めて難解であるために、この素数のパターンが示す事実については未だに明らかにされていない。

素数が無数に存在することは既に古代ギリシア時代から知られていて、ユークリッドが彼の著作『原論』^[21]の中で証明している。

ユークリッドによる証明

『原論』第9巻 命題20^[21]

素数の個数はいかなる定められた素数の個数よりも多い。

定められた個数の素数を p₁, p₂, …, p_n とせよ。p₁, p₂, …, p_n より多い個数の素数があると主張する。

『原論』による証明^{[注釈 2]}

定められた素数の個数が n 個であるとき、n 個の素数を小さい順番に並べて i 番目の素数を p_i とする。

1 < p₁ < p₂ < … < p_n.

このとき、n 個の素数をすべて掛け合わせた数に 1 を加えた数を q とすると、

q = p₁ × p₂ × … × p_n + 1.

q は有限個の自然数の積に 1 を加えた数なので 1 より大きい自然数である。ゆえに、q は素数または合成数のどちらかである。

q が素数のとき、q は最大の素数 p_n より大きい素数になるので、定められた個数の素数よりも多くの素数が存在する。

q が合成数のとき、q を割り切る素数が存在する。一方、q の定義より、すべての p_i で割った余りは 1 になるので、q はすべての p_i で割り切れない。したがって、すべての p_i 以外に素数が存在する。すなわち、定められた個数の素数よりも多くの素数が存在する。（証明終）

1878年、クンマーは q = p₁ × p₂ × … × p_n + 1 の代わりに q = p₁ × p₂ × … × p_n − 1 を考えても同様に証明できることを示した。

例

自然数の有限集合 A の全ての要素を掛け合わせた自然数を f(A) とする。

定められた個数の素数からなる集合を A₃ = {2, 3, 5} とするとき、f(A₃) = 2 × 3 × 5 + 1 = 31 は素数なので、新しい素数 31 が得られる。したがって、定められた個数より多くの素数が存在する。

定められた個数の素数からなる集合を A₄ = {2, 3, 5, 31} とするとき、f(A₄) = 2 × 3 × 5 × 31 + 1 = 931 = 7 × 7 × 19 なので、新しい素数 7 と 19 が得られる。したがって、定められた個数より多くの素数が存在する。

他の証明

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

• 素数の逆数の和が発散することを利用した証明^{[注釈 3]}（#素数の逆数和を参照）
• 2つの異なるフェルマー数が互いに素であることを利用した証明^{[注釈 4]}
• 整数の集合に、等差数列の族を開基とする位相を入れる証明^{[注釈 5]}
• n ≥ 2 に対して、n(n + 1) は少なくとも相異なる2個の素因数を持つことを利用した証明^{[注釈 6]}（サイダックによる）

素数判定と素因数分解

→詳細は「素数判定」および「素因数分解」を参照

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

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

分布

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

x 以下の素数の個数を π(x)（素数計数関数）とすると、

${\displaystyle \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月現在知られている最大の素数 2^82589933 − 1 の次の素数は 2^82589934 − 2 未満である。

一方で、例えば n² と (n + 1)² の間に素数が存在するかという問題は未解決である（ルジャンドル予想）。

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

素数計数

2015年に、ゴールドバッハの予想検証プロジェクトは 4 × 10¹⁸ 以下の全ての素数（9京5676兆2609億0388万7607個、約 10¹⁷個）を計算したと報告した^[26]が、結果は保存されていない。しかしながら、素数計数関数を計算するには、実際に素数を数えるより高速な公式が存在する。この公式を使って、10²³ 以下に 19垓2532京0391兆6068億0396万8923個（約 2×10²¹個）の素数があると計算された。

また、別の計算によると、リーマン予想が真であると仮定した場合、10²⁴ 以下に 184垓3559京9767兆3492億0086万7866個（約 2×10²²個）の素数が存在する^[27]。

分布の視覚化

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

素数に関連する主な性質

素数の逆数和

素数の逆数の和は（無限大に）発散する。この命題は『素数は無数に存在する』という命題を含んでいる（有限個ならば収束、すなわち発散しないはずである）が、それだけではなく素数の分布に関してより多くの情報を提供している。

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

エルデシュによる証明

素数の逆数和は収束すると仮定する。i 番目の素数を p_i で表すと、

${\displaystyle \sum _{i=N+1}^{\infty }{\frac {1}{p_{i}}}<{\frac {1}{2}}\cdots (1)}$

を満たす N が存在する。

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

k = u²v（v の各素因数の指数は全て 1）

と表示すると、v は高々 2^N 通り、u² ≤ k ≤ n より

#A_n ≤ 2^N√n …(2)

A_n^c の元は、p_N+1 以上の素因数を少なくとも1つ持つから、(1) より

${\displaystyle \#{A_{n}}^{c}\leq \sum _{i=N+1}^{\infty }\left[{\frac {n}{p_{i}}}\right]\leq n\sum _{i=N+1}^{\infty }{\frac {1}{p_{i}}}<{\frac {n}{2}}}$

#A_n^c = n − #A_n より

n/2 < #A_n …(3)

(2), (3) より n/2 < 2^N √n, ∴ n < 2^2N+2。これは n の任意性に矛盾。（証明終）

双子素数に限ると、逆数和は B₂ = 1.902… に収束することが証明されている（ブルン定数）。

その他の性質

• (a, m) = 1 のとき、等差数列：a, a + m, a + 2m, … には素数の項が無数に含まれている。（ディリクレの算術級数定理）

ここで m = 10 とすると、十進表記において一の位が 1, 3, 7, 9 である素数はどれも無数にあることが分かる。

• 素数 p に対して、(a, p) = 1 ⇒ a^p−1 ≡ 1 (mod p)（フェルマーの小定理）
• p が素数 ⇔ (p − 1)! ≡ −1 (mod p)（ウィルソンの定理）
• 素数の2乗差は 5 の倍数, 3 の倍数, 8 の倍数のいずれかである。

5 ( = 3² − 2²), 16 ( = 5² − 3²), 21 ( = 5² − 2²), 24 ( = 7² − 5²), 40 ( = 7² − 3²), …

• 約数の和が素数になる自然数は、2 と素数かその累乗数の平方数である。しかし、素数やその累乗数の自乗であっても約数の和が素数になるとは限らない。約数の和が素数になる数が無限にあるかどうかの証明はされていない（後述）。
• 七進表記において、5以上の素数の数字根は、必ず1か5となる。

素数生成式

→詳細は「en:Formula for primes」を参照

n番目の素数を求める素数生成式は存在しないと主張されることがあるが、これは誤りである（ウィルソンの定理やミルズの定数を用いたものが存在する）^[28]。しかしながら、そのような式で実効的に計算可能（英語版）なものは知られていない。

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

${\displaystyle p(n)=1+\textstyle \sum \limits _{m=1}^{2^{n}}\left\lfloor {\sqrt[{n}]{\dfrac {n}{\sum \limits _{k=1}^{m}\left\lfloor \cos ^{2}{\frac {\left(k-1\right)!+1}{k}}\pi \right\rfloor }}}\right\rfloor }$^[29]

1変数多項式

オイラーの発見した式：

• f(n) = n² − n + 41

は、自然数 n が n < 41 で全て素数となる。これは、虚二次体 ${\displaystyle \mathbb {Q} ({\sqrt {-163}})}$ の類数が 1 であることと関係している^[30][31]。一般に、0 ≤ n < p で多項式 f(n) = n² − n + p が素数の値を取るとき、素数 p の値を「オイラーの幸運数」^[32]という。オイラーの幸運数は p = 2, 3, 5, 11, 17, 41 の6つのみであり、これらはすべてヘーグナー数と対応する。

ルビーの多項式：

• f(n) = 36n² − 810n + 2753

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

• 103n² − 3945n + 34891 (Ruby)
• 47n² − 1701n + 10181 (Fung)

は n = 0, …, 42 で全て素数となる。

• 36n² − 2358n + 36809 (Willium)

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

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

• n³ − 34n² + 381n − 1511 (Goetgheluck)
• 2n³ − 45n² + 331n − 3191 (Goetgheluck)

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

多変数多項式

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

wz + h + j − q = 0

(gk + 2g + k + 1)(h + j) + h − z = 0

16(k + 1)³(k + 2)(n + 1)² + 1 − f² = 0

2n + p + q + z − e = 0

e³(e + 2)(a + 1)² + 1 − o² = 0

(a² − 1)y² + 1 − x² = 0

16r²y⁴(a² − 1) + 1 − u² = 0

n + l + v − y = 0

(a² − 1)l² + 1 − m² = 0

ai + k + 1 − l − i = 0

[{a + u²(u² − a)}² − 1](n + 4dy)² + 1 − (x + cu)² = 0

p + l(a − n − 1) + b(2an + 2a − n² − 2n − 2) − m = 0

q + y(a − p − 1) + s(2ap + 2a − p² − 2p − 2) − x = 0

z + pl(a − p) + t(2ap − p² − 1) − pm = 0

特殊な形をした素数

• メルセンヌ素数：2ⁿ − 1（n は素数、n = 2, 3, 5, 7, 13, …）
• フェルマー素数：2²ⁿ + 1
• オイラー素数：n² + n + 41
• 階乗素数
  • n! + 1型 (n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, …)
  • n! − 1型 (n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, …)
• 素数階乗素数：p# ± 1（p は素数、p# は p の素数階乗）
• レピュニット R₂, R₁₉, R₂₃, …（R_n は 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 分体の類数を割り切る奇素数）
• フィボナッチ素数（フィボナッチ数の数列に含まれる素数）
• ヴィーヘリッヒ素数 (2^p−1 ≡ 1 (mod p²) を満たす素数 p)
• グロタンディーク素数（57のことでグロタンディークが演説している際に " 分かりやすい例を上げてほしい " と言われて合成数である " 57 " を挙げてしまった）
• その他の素数
  • n² + 1 の形で表せる素数^[34]：2, 5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, …
  • n⁴ + 1 の形で表せる素数^[35]：2, 17, 257, 1297, 65537, 160001, …
  • n⁴ + (n + 1)⁴ の形で表せる素数^[36]：17, 97, 337, 881, 3697, …
  • ある数の約数の和になる素数^[37]：3, 7, 13, 31, 127, 307, 1093, …

未解決問題

• 双子素数の予想：双子素数は無数に存在する、という予想。
• ゴールドバッハの予想：6 以上の全ての偶数は 2 つの奇素数の和で表すことができる、という予想。
• 弱いゴールドバッハ予想：7 以上の全ての奇数は 3 つの素数の和で表すことができる、という予想。ただしハラルド・ヘルフゴットによる証明が2013年に発表されている^[38][39][40]。
• ルジャンドル予想：全ての n に対し、n² と (n + 1)² の間に素数が存在するかという予想。
• 既知のフェルマー素数 (3, 5, 17, 257, 65537) 以外に、フェルマー数にフェルマー素数は存在するか？
• メルセンヌ素数は無数に存在するか？
• ソフィー・ジェルマン素数、安全素数は無数に存在するか？
• フィボナッチ数列には、素数である項が無数に現れるか？（フィボナッチ素数）
• 幸運数でも素数でもあるような数は無数に存在するか？
• ハッピー素数は無数に存在するか？
• n² + 1 の形の素数は無数に存在するか？（ブニャコフスキー予想）
• 約数の和の列になる素数は無数に存在するか？

応用

長い間、数論、その中でもとりわけ素数に関する研究は、その分野以外での応用の全くない純粋数学の見本と見なされていた。特に、イギリスの数論研究者であるハーディは、自身の研究が軍事的に何の重要性も持たないことを誇っていた。しかし、この見方は1970年代には覆されてしまった。素数が公開鍵暗号のアルゴリズムに使用できると広く知られるようになったためである。現在では素数はハッシュテーブルや擬似乱数生成にも用いられ、工学的応用上重要度の高いものとなっている。

公開鍵暗号

→詳細は「公開鍵暗号」を参照

公開鍵暗号のアルゴリズムとして、RSA暗号やディフィー・ヘルマン鍵共有といった、大きな数の素因数分解は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの（大きな）素数の掛け算は比較的簡単に（効率的に）行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。

固定ギア自転車のタイヤの寿命対策

固定ギア自転車のスプロケットやチェーンリングの歯数を素数にすることでスキッドポイントと呼ばれる摩耗点を分散化させてタイヤの寿命を向上させることができる。また、自転車や内燃機関など入力に脈動がある動力の歯車を素数にすると摩耗点が分散され歯車の寿命が向上する。

自然界の素数

自然界に現れる素数の一例として、素数ゼミと呼ばれるセミの一種がいる。アメリカ合衆国に分布するこのセミの成虫は、ある周期ごとに、13年ないしは17年間の周期で大量発生する。成虫になった後は、数週間だけを地上で成虫として過ごし交配と産卵を行う。このセミが素数周期で発生する理由として、寄生虫や捕食者に対抗するための進化であるという説や近縁種との交雑を避けるためであるという説がある。つまり、もしこのセミが12年の発生周期を持っていた場合、12の約数である2, 3, 4, 6年の寿命を持つ捕食者と同時に発生してしまうことになり、捕食対象にされやすくなる。また、地理的に近い場所で12年周期と15年周期のセミが存在した場合、60年ごとに2種は同時に発生し、交雑してしまう可能性がある。すると、雑種は発生周期がずれてしまい、同種のセミとの交尾の機会が失われる。素数の周期を持つものは交雑が起こりにくく、淘汰されにくいと考えられる^[41]。

また、ゼータ関数上の零点の分布の数式が、原子核のエネルギー間隔を表す式と一致することを示し、素数と核物理現象との関連性が示唆されている。

→詳細は「リーマン予想」を参照

コンピュータゲーム

パナソニック株式会社が2011年にリリースしたiPad用アプリケーション「Panasonic Prime Smash!」は空中に打ち上げられたボールに書かれた数字が素数であればタップして得点、合成数であればスワイプすることで割り算し、素数になったらタップして得点にするゲームである^[42]。第15回文化庁メディア芸術祭エンターテインメント部門の審査委員会推薦作品に選ばれ^[43]、第6回企業ウェブグランプリ スチューデント部門特別賞を受賞した^[44]。

2016年にイギリスの数学者クリスチャン・ローソン=パーフェクトが公開した「これは素数ですか？ (Is this prime?)」は、画面に表示される数字を素数と合成数に仕分けるゲームで、2021年7月にプレイ回数が300万回を突破した^[45]。このゲームのプログラムにはミラー–ラビン素数判定法が組み込まれている^[45]。

連続素数

連続素数和

連続数	数	参照	含まれる素数列
2	5, 8, 12, 18, 24, 30, 36, 42, 52, 60, 68, 78, 84, …	A001043
3	10, 15, 23, 31, 41, 49, 59, 71, 83, 97, 109, …	A034961	A034962
4	17, 26, 36, 48, 60, 72, 88, 102, 120, 138, 152, …	A034963
5	28, 39, 53, 67, 83, 101, 119, 139, 161, 181, …	A034964	A034965
6	41, 56, 72, 90, 112, 132, 156, 180, 204, 228, …	A127333
7	58, 75, 95, 119, 143, 169, 197, 223, 251, 281, …	A127334	A082246
8	77, 98, 124, 150, 180, 210, 240, 270, 304, …	A127335
9	100, 127, 155, 187, 221, 253, 287, 323, 363, …	A127336	A082251
10	129, 158, 192, 228, 264, 300, 340, 382, 424, …	A127337
11	160, 195, 233, 271, 311, 353, 399, 443, 491, …	A127338	A127340
12	197, 236, 276, 318, 364, 412, 460, 510, 562, …	A127339
13	238, 279, 323, 371, 423, 473, 527, …		A127341

各連続素数和の最初の数については「[[オンライン整数列大辞典の数列 A007504]]」を、この数が素数になる数については「[[オンライン整数列大辞典の数列 A013918]]」を参照

連続素数積

連続数	数	参照
2	6, 15, 35, 77, 143, 221, 323, 437, 667, 899, 1147, 1517, 1763, …	A006094
3	30, 105, 385, 1001, 2431, 4199, 7429, 12673, 20677, 33263, 47027, …	A046301
4	210, 1155, 5005, 17017, 46189, 96577, 215441, 392863, 765049, …	A046302
5	2310, 15015, 85085, 323323, 1062347, 2800733, …	A046303
6	30030, 255255, 1616615, 7436429, 30808063, 86822723, …	A046324
7	510510, 4849845, …	A046325
8	9699690, 111546435, …	A046326
9	223092870, 3234846615, …	A046327
10	6469693230, 100280245065, …	A127342
11	200560490130, 3710369067405, …	A127343
12	7420738134810, 152125131763605, …	A127344

各連続素数積の最初の数については「素数階乗」を参照

素数砂漠

自然数で素数でないものが連続している区間を「素数砂漠」という。例えば{24, 25, 26, 27, 28} は「長さ 5 の素数砂漠」である。素数砂漠を挟む2個の素数は 3 以上であるため、共に奇数である。このことから、素数砂漠の長さは必ず奇数である。いくらでも長い素数砂漠が構成できる（#分布を参照）。

初めから60個の素数の間隔は^[46]

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. ユークリッドによる証明では、変数・数式・任意の個数を示すパラメーター n を使用せずに、定められた個数が 3個の素数 Α, Β, Γ の場合に証明している。これを「準一般的」な証明という。詳細は素数が無数に存在することの証明#ユークリッドを参照。
3. レオンハルト・オイラーによる。現代的な用語で言えば、リーマンゼータ関数のオイラー積表示を用いる^[22]。
4. ジョージ・ポーヤによる^[22][23]。
5. ヒレル・ファステンバーグによる。en:Furstenberg's proof of the infinitude of primesを参照。
6. 素数が無数に存在することの証明#サイダックを参照^[24]。
7. 『天書の証明』第1章^[23]を参照。原論文は Erdös, P. (1938-07), “Über die Reihe ∑ 1/p” (German) (pdf), Mathematica, Zutphen B: 1-2, https://users.renyi.hu/~p_erdos/1938-12.pdf。

出典

1. 「創立80周年特集」『数学』第9巻第2号、1957年、72頁、doi:10.11429/sugaku1947.9.65。
2. 「東京數學會社雑誌第四十二號附録」『東京數學會社雑誌』1881年、13頁、doi:10.11429/sugakukaisya1877.1881.42sup_1。
3. 藤原松三郎他 著、日本学士院 編『明治前 日本数学史』 第4巻、岩波書店、1959年、29頁。NDLJP:2421638。
4. オンライン整数列大辞典の数列 A40
5. “The Largest Known Primes”. The Prime Pages (2024年10月21日). 2024年10月22日閲覧。
6. 史上最大の素数発見、4100万桁超　びっちり印刷しても1万6千枚(朝日新聞、2024年10月23日)
7. “[数A]11の倍数の判定法、見分け方とその証明”. トムラボ. 2023年2月25日閲覧。
8. http://www4.math.sci.osaka-u.ac.jp/~ogawa/pdfs/v_lec/HimejiNishi-2006-12.pdf
9. Caldwell & Xiong 2012
10. Caldwell et al. 2012。古代ギリシアについては pp.3-4、アラビアについては p.6 を参照。
11. 例えば David E. Joyce's のユークリッド原論についてのコメンタリー Book VII, definitions 1 and 2 を参照。
12. Tarán 1981
13. Caldwell et al. 2012, pp. 7–13。特にStevin、Brancker、Wallis、Prestetの項を参照。
14. Caldwell et al. 2012, p. 15
15. Conway & Guy 1996, pp. 129f
16. Derbyshire 2003, p. 33
17. Conway & Guy 1996, pp. 129–130
18. φ関数についてはSierpiński 1988、p. 245を参照。約数関数についてはSandifer 2007、p. 59を参照。
19. "Arguments for and against the primality of 1".
20. "Why is the number one not prime?"
21. ユークリッド 2011, 9-20
22. Ribenboim 2001, 第1章
23. アイグナー & ツィーグラー 2012, 第1章
24. doi:10.2307/27642094 https://primes.utm.edu/notes/proofs/infinite/Saidak.html
25. この区間の最初の値はオンライン整数列大辞典の数列 A008950を、終了の値はオンライン整数列大辞典の数列 A008995をその区間幅についてはオンライン整数列大辞典の数列 A008996を参照
26. Tomás Oliveira e Silva, Goldbach conjecture verification. Retrieved 16 July 2013.
27. Jens Franke (2010年7月29日). “Conditional Calculation of pi(10²⁴)”. 2018年12月30日閲覧。
28. Prime Formulas -- from Wolfram MathWorld
29. Willans, C. P (1964-12), “On formulae for the nth prime number”, The Mathematical Gazette 48 (366): 413-415, doi:10.2307/3611701, ISSN 0025-5572, JSTOR 3611701, https://jstor.org/stable/3611701
30. Ribenboim 2001, 第3章
31. オンライン整数列大辞典の数列 A005846
32. オンライン整数列大辞典の数列 A014556
33. Jones, James P.; Sato, Daihachiro; Wada, Hideo; Wiens, Douglas (1976), "Diophantine representation of the set of prime numbers", American Mathematical Monthly 83: 449-464, doi:10.2307/2318339
34. オンライン整数列大辞典の数列 A002496
35. オンライン整数列大辞典の数列 A037896
36. オンライン整数列大辞典の数列 A152913
37. オンライン整数列大辞典の数列 A023195
38. Helfgott, H.A. (2013). "Major arcs for Goldbach's theorem". arXiv:1305.2897 [math.NT]。
39. Helfgott, H.A. (2012). "Minor arcs for Goldbach's problem". arXiv:1205.5252 [math.NT]。
40. Dossier Alexander von Humboldt-Professur - Alexander von Humboldt-Stiftung
41. 吉村 2008
42. 田崎恭子 (2011年5月16日). “素数の不思議をゲームで学ぶiPadアプリ”. リセマム (イード). https://resemom.jp/article/2011/05/16/2398.html 2023年8月24日閲覧。
43. “第15回 受賞作品文化庁メディア芸術祭エンターテインメント部門”. 文化庁メディア芸術祭. 文化庁. 2023年8月24日閲覧。
44. 池田真也 (2012年12月10日). “「第6回企業ウェブ・グランプリ」受賞サイト決定、コンテンツへの思いがグランプリへ”. Web担当者Forum (インプレス). https://webtan.impress.co.jp/e/2012/12/10/14313 2023年8月24日閲覧。
45. シヴォーン・ロバーツ (2021年7月26日). “51、57、91は素数？ 数学者が考えたオンライン・ゲームが人気”. MIT Technology Review (KADOKAWA). https://www.technologyreview.jp/s/251275/is-57-a-prime-number-theres-a-game-for-that/ 2023年8月24日閲覧。
46. オンライン整数列大辞典の数列 A001223

参考文献

• Aigner, Martin; Ziegler, Günter M. (2010), Proofs from THE BOOK (4th ed.), Springer-Verlag, ISBN 978-3-642-00856-6, https://www.springer.com/jp/book/9783642008566
  • M・アイグナー、G・M・ツィーグラー 著、蟹江幸博 訳『天書の証明』（縮刷版）丸善出版、2012年9月1日。ISBN 978-4-621-06535-8。https://pub.maruzen.co.jp/book_magazine/book_data/search/9784621065358.html。
• Caldwell, Chris K.; Reddick, Angela; Xiong, Yeng; Keller, Wilfrid (2012). “The history of the primality of one: a selection of sources”. Journal of Integer Sequences（英語版） 15 (9): Article 12.9.8. MR3005523. https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html.
• Caldwell, Chris K.; Xiong, Yeng (2012). “What is the smallest prime?”. Journal of Integer Sequences 15 (9): Article 12.9.7. MR3005530. https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.pdf.
• Conway, John Horton; Guy, Richard K. (1996), The Book of Numbers, New York: Copernicus, ISBN 978-0-387-97993-9
  • J・H・コンウェイ、R・K・ガイ 著、根上生也 訳『数の本』丸善出版、2012年1月。ISBN 978-4-621-06207-4。https://pub.maruzen.co.jp/book_magazine/book_data/search/9784621062074.html。
• R. Crandall ; C. Pomerance: Prime Numbers: A Computational Perspective, Springer, ISBN 0-387-28979-8 (2005)
  • R. Crandall ; C. Pomerance, 和田秀男（監訳）：「素数全書：計算からのアプローチ」朝倉書店、ISBN 978-4-254-11128-6（2010年9月10日).
• 真実のみを記述する会『素数表150000個』暗黒通信団、2011年8月。ISBN 978-4-87310-156-9。https://ankokudan.org/d/d.htm?detail156-detailread-j.html。
• Manfred Robert Schroeder 著、平野浩太郎・野村孝徳 共 訳『科学と通信における数論　暗号，物理学，ディジタル情報，計算法，自己相似性を含む』 〈上〉、パスカル研究会（出版）コロナ社（発売）、1995年2月1日、33-68頁。ISBN 978-4-339-08216-6。https://www.coronasha.co.jp/np/isbn/9784339082166/。
• Derbyshire, John (2003), Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, Washington, D.C.: Joseph Henry Press, ISBN 978-0-309-08549-6, OCLC 249210614
  • ジョン・ダービーシャー 著、松浦俊輔 訳『素数に憑かれた人たち　リーマン予想への挑戦』日経BP社（出版）日経BP出版センター（発売）、2004年8月30日。ISBN 978-4-8222-8204-2。https://shop.nikkeibp.co.jp/front/commodity/0000/P82040/。
• 本橋洋一『解析的整数論』 〈1〉素数分布論（第2刷）、朝倉書店〈朝倉数学大系〉、2012年（原著2009年11月1日）。ISBN 978-4-254-11821-6。https://www.asakura.co.jp/books/isbn/978-4-254-11821-6/。 - 第2刷 2012：加筆含む。
• 本橋洋一「素数の翼に乗って」（pdf）『数学通信』第10巻第1号、東京 : 日本数学会、2005年5月、4-19頁、CRID 1520572358126328192、ISSN 13421387、2024年3月14日閲覧。
• ユークリッド 著、中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵 訳『ユークリッド原論』（追補版）共立出版、2011年5月25日。ISBN 978-4-320-01965-2。https://www.kyoritsu-pub.co.jp/bookdetail/9784320019652。
• 吉村仁『17年と13年だけ大発生? 素数ゼミの秘密に迫る!』ソフトバンククリエイティブ〈サイエンス・アイ新書 072〉、2008年7月16日。ISBN 978-4-7973-4258-1。https://www.sbcr.jp/products/4797342581.html。
• Riesel, Hans (1994), Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, ISBN 978-0-8176-3743-9
• Ribenboim, Paulo (2004), The Little Book of Bigger Primes (2nd ed.), Springer-Verlag, ISBN 978-0-387-20169-6, https://www.springer.com/jp/book/9780387201696
  • Paulo Ribenboim 著、吾郷孝視 訳『素数の世界―その探索と発見―』（第2版）共立出版、2001年10月20日。ISBN 978-4-320-01684-2。https://www.kyoritsu-pub.co.jp/bookdetail/9784320016842。
• Sandifer, C. Edward (2007). How Euler Did It. MAA Spectrum. Mathematical Association of America. ISBN 978-0-88385-563-8
• Sierpiński, Wacław (1988). Elementary Theory of Numbers. North-Holland Mathematical Library. 31 (2nd ed.). Elsevier. ISBN 978-0-08-096019-7
• Tarán, Leonardo (1981). Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary. Philosophia Antiqua : A Series of Monographs on Ancient Philosophy. 39. Brill. pp. 35-38. ISBN 978-90-04-06505-5. https://books.google.com/books?id=cUPXqSb7V1wC&pg=PA35

関連項目

• 違法素数
• エマープ
• エラトステネスの篩
• 巨大な素数の一覧
• コープランド-エルデシュ定数
• 素数の一覧
• ピタゴラス素数
• プライム (小惑星) - 小惑星番号7919が1000番目の素数であることに因む小惑星。
• 半素数
• 楔数
• 素数大富豪

外部リンク

• The Prime Page
• Weisstein, Eric W. "Prime Number". mathworld.wolfram.com (英語).
• prime number in nLab
• prime - PlanetMath.（英語）
• Hazewinkel, Michiel, ed. (2001), “Prime number”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Prime_number