素数 - Wikiwand

素数（そすう、英: prime あるいは prime number）とは、 $2$ 以上の自然数で、正の約数が $1$ とその数自身のみであるもののことである。正の約数の個数が $2$ である自然数と言い換えることもできる。 $1$ より大きい自然数で素数でないものは合成数と呼ばれる。例えば、 $5$ は素数である。なぜなら、 $5$ を自然数の積として書くには、「1×5」か「5×1」しかないからである。しかし、 $4$ を自然数の積で表すと、「1×4」、「4×1」の他に「2×2」があり、両方の数が4より小さいので合成数である。よって素数ではない。

Thumb — 「prime」は素数。「composite」は合成数。合成数は長方形に並べることができるが、素数は長方形に並べられない。

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

一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環 $\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,\dots

素数が無数に存在することは、紀元前3世紀頃のエウクレイデス（以下ユークリッド）の著書『原論』で既に証明されていた。そこでの証明は、背理法により次のようになる：

『素数全体は有限個と仮定して、全ての素数の総乗に1を足した数をNとする。Nはどの素数で割っても余りが1となる。一方、Nはどの素数よりも大きいので、Nは素数ではない。すなわち、Nはある素数で割り切れる。これは、Nを素数で割った余りが1であることに矛盾する。ゆえに、素数は無数にある。』

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

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

定義と例

さらに見る 100 以下の素数一覧 ...

$100$ 以下の素数一覧
	0 $2$	$3$	00	0 $5$	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, \dots$ ）
一の位から見て奇数番目の位の数の和と、偶数番目の位の数の和との差が11の倍数であれば、11の倍数である（11で割り切れる）。（100以上では、 $110, 121, 132, 143, 154, 165, 176, 187, 198, 209, \dots$ ）^[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 \times 3 = 1 \times 2 \times 3 = 1 2 \times 2 \times 3 = 1 3 \times 2 \times 3 = \dots

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

歴史

要約

視点

この節の加筆が望まれています。

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

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

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

ユークリッドによる証明

『原論』第9巻命題20^[21]: 素数の個数はいかなる定められた素数の個数よりも多い。; 定められた個数の素数を $p 1, p 2, \dots, p n$ とせよ。 $p 1, p 2, \dots, p n$ より多い個数の素数があると主張する。
『原論』による証明^{[注釈 2]}: 定められた素数の個数が $n$ 個であるとき、 $n$ 個の素数を小さい順番に並べて $i$ 番目の素数を $p i$ とする。; $1 < p 1 < p 2 < \dots < p n .$; このとき、 $n$ 個の素数をすべて掛け合わせた数に $1$ を加えた数を $q$ とすると、; $q = p 1 \times p 2 \times \dots \times 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 1 \times p 2 \times \dots \times p n + 1$ の代わりに $q = p 1 \times p 2 \times \dots \times p n - 1$ を考えても同様に証明できることを示した。
例: 自然数の有限集合 $A$ の全ての要素を掛け合わせた自然数を $f (A)$ とする。; 定められた個数の素数からなる集合を $A 3 = {2, 3, 5}$ とするとき、 $f (A 3) = 2 \times 3 \times 5 + 1 = 31$ は素数なので、新しい素数 $31$ が得られる。したがって、定められた個数より多くの素数が存在する。; 定められた個数の素数からなる集合を $A 4 = {2, 3, 5, 31}$ とするとき、 $f (A 4) = 2 \times 3 \times 5 \times 31 + 1 = 931 = 7 \times 7 \times 19$ なので、新しい素数 $7$ と $19$ が得られる。したがって、定められた個数より多くの素数が存在する。

他の証明

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

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

素数判定と素因数分解

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

与えられた自然数 $n$ が素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。最も素朴な方法は、 $2$ から $\sqrt n$ 以下の素数まで順番に割っていく、試し割り法と呼ばれる方法である。 $n$ が $\sqrt 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 \leq 2 n

を満たす素数

p

が存在する」（ベルトランの仮説、チェビシェフの定理）

この主張は「任意の素数 $p$ の次の素数は $2 p$ 未満」とも言い換えられる。したがって、2024年12月現在知られている最大の素数 $2136279841 - 1$ の次の素数は $2136279842 - 2$ 未満である。

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

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

素数計数

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

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

分布の視覚化

素数に関連する主な性質

要約

視点

素数の逆数和

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

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

エルデシュによる証明

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

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

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

$n$ 以下の自然数のうち最大素因数が $p N$ 以下のものからなる集合を $A n$ とする。任意の $k \in A n$ に対して、

k = u 2 v

（

v

の各素因数の指数は全て

1

）

と表示すると、 $v$ は高々 $2 N$ 通り、 $u 2 \leq k \leq n$ より

# A n \leq 2 N \sqrt n

…(2)

$A n c$ の元は、 $p N +1$ 以上の素因数を少なくとも1つ持つから、(1) より

\#{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$ より

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n/2 < #An

…(3)

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

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

その他の性質

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

ここで

m = 10

とすると、十進表記において一の位が

1, 3, 7, 9

である素数はどれも無数にあることが分かる。

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

5 ( = 3 2 - 22), 16 ( = 5 2 - 32), 21 ( = 5 2 - 22), 24 ( = 7 2 - 52), 40 ( = 7 2 - 32), \dots

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

素数生成式

要約

視点

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

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

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

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 2 - n + 41$

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

ルビーの多項式：

$f (n) = 36 n 2 - 810 n + 2753$

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

$103 n 2 - 3945 n + 34891$ (Ruby)
$47 n 2 - 1701 n + 10181$ (Fung)

は $n = 0, \dots, 42$ で全て素数となる。

$36 n 2 - 2358 n + 36809$ (Willium)

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

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

$n 3 - 34 n 2 + 381 n - 1511$ (Goetgheluck)
$2 n 3 - 45 n 2 + 331 n - 3191$ (Goetgheluck)

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

多変数多項式

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

wz + h + j - q = 0

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

16(k + 1) 3 (k + 2)(n + 1) 2 + 1 - f 2 = 0

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

e 3 (e + 2)(a + 1) 2 + 1 - o 2 = 0

(a 2 - 1) y 2 + 1 - x 2 = 0

16 r 2 y 4 (a 2 - 1) + 1 - u 2 = 0

n + l + v - y = 0

(a 2 - 1) l 2 + 1 - m 2 = 0

ai + k + 1 - l - i = 0

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

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

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

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

特殊な形をした素数

メルセンヌ素数： $2 n - 1$ （ $n$ は素数、 $n = 2, 3, 5, 7, 13, \dots$ ）
フェルマー素数： $2 2 n + 1$
オイラー素数： $n 2 + n + 41$
階乗素数
- $n! + 1$ 型 $(n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, \dots)$
- $n! - 1$ 型 $(n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, \dots)$
素数階乗素数： $p # \pm 1$ （ $p$ は素数、 $p #$ は $p$ の素数階乗）
レピュニット $R 2, R 19, R 23, \dots$ （ $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$ と $2 p + 1$ がともに素数である時の $p$ のこと)
安全素数（ $p$ と $2 p + 1$ がともに素数であるときの $2 p + 1$ のこと)
スーパー素数（素数列における素数番目の素数）
切り捨て可能素数（「素な素数」。与えられた基数において $0$ を含まず、左右一方の端から順に数を取り除いた数がすべて素数となる素数）
陳素数（ $p + 2$ が半素数またはともに素数）
正則素数（円の $p$ 分体の類数を割り切らない奇素数）
非正則素数（円の $p$ 分体の類数を割り切る奇素数）
フィボナッチ素数（フィボナッチ数の数列に含まれる素数）
ヴィーヘリッヒ素数 ( $2 p - 1 \equiv 1 (mod p 2)$ を満たす素数 $p$ )
グロタンディーク素数（57のことでグロタンディークが演説している際に " 分かりやすい例を上げてほしい " と言われて合成数である " 57 " を挙げてしまった）
その他の素数
- $n 2 + 1$ の形で表せる素数^[34]： $2, 5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, \dots$
- $n 4 + 1$ の形で表せる素数^[35]： $2, 17, 257, 1297, 65537, 160001, \dots$
- $n 4 + (n + 1) 4$ の形で表せる素数^[36]： $17, 97, 337, 881, 3697, \dots$
- ある数の約数の和になる素数^[37]： $3, 7, 13, 31, 127, 307, 1093, \dots$

未解決問題

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

応用

要約

視点

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

公開鍵暗号

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

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

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

この節は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2024年7月)

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

自然界の素数

自然界に現れる素数の一例として、素数ゼミと呼ばれるセミの一種がいる。アメリカ合衆国に分布するこのセミの成虫は、ある周期ごとに、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, \dots$	A001043
3	$10, 15, 23, 31, 41, 49, 59, 71, 83, 97, 109, \dots$	A034961	A034962
4	$17, 26, 36, 48, 60, 72, 88, 102, 120, 138, 152, \dots$	A034963
5	$28, 39, 53, 67, 83, 101, 119, 139, 161, 181, \dots$	A034964	A034965
6	$41, 56, 72, 90, 112, 132, 156, 180, 204, 228, \dots$	A127333
7	$58, 75, 95, 119, 143, 169, 197, 223, 251, 281, \dots$	A127334	A082246
8	$77, 98, 124, 150, 180, 210, 240, 270, 304, \dots$	A127335
9	$100, 127, 155, 187, 221, 253, 287, 323, 363, \dots$	A127336	A082251
10	$129, 158, 192, 228, 264, 300, 340, 382, 424, \dots$	A127337
11	$160, 195, 233, 271, 311, 353, 399, 443, 491, \dots$	A127338	A127340
12	$197, 236, 276, 318, 364, 412, 460, 510, 562, \dots$	A127339
13	$238, 279, 323, 371, 423, 473, 527, \dots$		A127341

閉じる

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

連続素数積

さらに見る 連続数, 数 ...

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

→詳細は「素数の間隔」を参照

脚注

Loading content...

参考文献

Loading content...

外部リンク

Loading content...

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

定義と例

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

1 は素数か

歴史

ユークリッドによる証明

他の証明

素数判定と素因数分解

分布

素数計数

分布の視覚化

素数に関連する主な性質

素数の逆数和

その他の性質

素数生成式

1変数多項式

多変数多項式

特殊な形をした素数

未解決問題

応用

公開鍵暗号

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

自然界の素数

コンピュータゲーム

連続素数

連続素数和

連続素数積

素数砂漠

脚注

参考文献

関連項目

外部リンク