素数
素数（そすう、）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。
一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環 Z {\displaystyle \mathbb {Z} } での素数は<b data-parsoid='{"dsr":[377,387,3,3]}'>有理素数（ゆうりそすう、）と呼ばれることもある。
最小の素数は 2 である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。
（(sequence A40 in the OEIS)）
素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。
自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。
分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2018年12月現在で知られている最大の素数は、2018年12月に発見された、それまでに分かっている中で51番目のメルセンヌ素数 282589933 − 1 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ[1]。
素数とは、自明な正の因数（1 と自分自身）以外に因数を持たない自然数であり、1 でない数のことである。つまり、正の因数の個数が 2 である自然数である。例えば、2 は、正の因数が 1, 2 のみなので素数である。一方で 91 は、正の因数が 1, 7, 13, 91 なので素数ではない。素数ではない 2 以上の自然数を合成数と呼ぶ。更に 2 を除く素数は奇数であり、奇素数</b>と呼ぶ。十進表記（10 = 2×5）では、2, 5 以外の素数は、一の位が 1, 3, 7, 9 のいずれかである。
100以下の素数は25個存在し、小さい順に次の通りである。
（(sequence A40 in the OEIS)）
さらに、1000以下の素数は100以下のものを含め168個存在する。101以上の1000以下の素数は小さい順に次の通りである。
「2 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する（算術の基本定理）。すなわち、「素数全体」の成す集合は、自然数全体の成す集合の（乗法に関する）最小の生成系である。言い換えれば、これは「素数は自然数の構成要素である」などとなる。
素数の定義である「1 と自分自身でしか割り切れない」という条件（既約性）は、抽象代数学において、環の既約元の概念（一部の環では素元の概念と一致する）に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えばネーター環では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。
素数の定義を「自明でない（1 と自分自身以外）約数の積に分解できない自然数」と考えた場合、「1 を素数の定義に含めるか含めないか」が問題となる。古代ギリシアでは、1 はそもそも数（自然数）であるとさえ見なされなかった[2]ので、1 は素数ではなかった。一方、19世紀には、1 は素数であると考える数学者が多く存在した。例えば、レーマーの 10,006,721 までの素数表（後の1956年に再版[3]）では、素数は 1 から始まるものとして書かれている[4]。アンリ・ルベーグは、1 を素数だと考えた最後の専門的な数学者だと言われている[5]。
1 は素数であると仮定しても、素因数分解の可能性は成り立ち、数学の大部分の命題ではそのままの文面で変わらず有効であるが、素因数分解の一意性は成り立たなくなる。1 が素数だとすると、例えば 6 の素因数分解は、（積の順序を除いても）
6 = 2 × 3 = 1 × 2 × 3 = 12 × 2 × 3 = …
と無数の素因数分解を与えることになり、一意性が成り立たなくなる。さらに、1 以外の素数で成り立つ様々な性質がある（例えば、自然数とそれに対応するオイラーのφ関数や約数関数の値との関係など）[6][7]。
紀元前1600年頃のエジプト第2中間期において、素数に関する知識が部分的に知られていたことが、リンド数学パピルスなどの資料によって示唆されている。例えば分数をエジプト式分数で表す場合、素数と合成数の場合で異なる計算をしなければならないからである。しかし、記録に残っている限りにおいて、明確に素数を研究対象としたのは古代ギリシア人が最初である。紀元前約300年頃に書かれたユークリッドの『原論』には素数が無数に存在することや、その他の素数の性質が証明されている。また、ユークリッドはメルセンヌ素数から完全数を構成する方法を示している。ギリシアの数学者、エラトステネスに因んで名付けられたエラトステネスの篩（ふるい）は、素数を列挙するための計算方法である。
古代ギリシア時代の後、17世紀になるまで素数の研究にはそれほどの進展が無かった。1640年に、ピエール・ド・フェルマーはフェルマーの小定理を（未証明ではあるが）述べた。この定理は後にライプニッツとオイラーによって証明された。
素数が無数に存在することは既に古代ギリシア時代から知られていて、ユークリッドが彼の著作『原論』[8]の中で証明している。
『原論』第9巻 命題20[8] 素数の個数はいかなる定められた素数の個数よりも多い。 定められた個数の素数を p1, p2, …, pn とせよ。p1, p2, …, pn より多い個数の素数があると主張する。 『原論』による証明 定められた素数の個数が n 個であるとき、n 個の素数を小さい順番にならべて i 番目の素数を pi とする。 1 < p1 < p2 < … < pn. このとき、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 が得られる。したがって、定められた個数より多くの素数が存在する。
上記のユークリッドによる証明以外にも、素数が無数に存在することの証明方法が存在する。
素数の逆数の和が発散することを利用した証明（#素数の逆数和を参照） 2つの異なるフェルマー数が互いに素であることを利用した証明 整数の集合に、等差数列の族を開基とする位相を入れる証明 n ≥ 2 に対して、n(n + 1) は少なくとも相異なる2個の素因数を持つことを利用した証明。おそらく最も短い証明。
与えられた自然数 n が素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。最も素朴な方法は、2 から √n 以下の素数まで順番に割っていく、試し割り</b>と呼ばれる方法である。n が √n 以下の全ての素数で割り切れなければ n は素数である。試し割りは、n が大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割りよりも高速なアルゴリズムが考案されている。また、特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。
ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。素数のない、いくらでも長い区間が存在する。例えば、n ≥ 2 に対して、連続する n − 1 個の自然数 n! + 2, …, n! + n はそれぞれ、より小さい 2, …, n で割り切れるので、どれも素数でない。また、比較的小さな数では、114 から 126 まで13個連続で合成数である。（この区間の最初の値は(sequence A008950 in the OEIS)を、終了の値は(sequence A008995 in the OEIS)をその区間幅については(sequence A008996 in the OEIS)を参照）
これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。
x 以下の素数の個数を （素数計数関数）とすると、
π ( x ) ∼ ∫ 2 x d t log ⁡ t ∼ x log ⁡ 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 ≤ 2<i>n を満たす素数 p が存在する」（ベルトランの仮説、チェビシェフの定理）
この主張は「任意の素数 p の次の素数は 2<i>p 未満」とも言い換えられる。したがって、2017年5月現在知られている最大の素数 274207281 − 1 の次の素数は 274207282 − 2 未満である。
しかしながら、例えば n2 と (n + 1)2 の間に素数が存在するかという問題は未解決である（ルジャンドル予想）。
2015年に、ゴールドバッハの予想検証プロジェクトは 4 × 1018 以下の全ての素数（9京5676兆2609億388万7607個、約 1017個）を計算したと報告した[9][10]が、結果は保存されていない。しかしながら、素数計数関数を計算するには、実際に素数を数えるより高速な公式が存在する。この公式を使って、1023 以下に 19垓2532京391兆6068億396万8923個（約 2×1021個）の素数があると計算された。
また、別の計算によると、リーマン予想が真であると仮定した場合、1024 以下に 184垓3559京9767兆3492億86万7866個（約 2×1022個）の素数が存在する[11]。
エラトステネスの篩 ウラムの螺旋 プリヒタの素数円
素数の逆数の和は（無限大に）発散する。この命題は『素数は無数に存在する』という命題を含んでいる（有限個ならば収束、すなわち発散しないはずである）が、それだけではなく素数の分布に関してより多くの情報を提供している。
この結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。以下の証明はポール・エルデシュによる、より直接的で、また簡潔な証明である。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。
素数の逆数和は収束すると仮定する。i 番目の素数を pi で表すと、
∑ i = N + 1 ∞ 1 p i < 1 2 ⋯ ( 1 ) {\displaystyle \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 ≤ 2N√n …(2)
Anc の元は、pN+1 以上の素因数を少なくとも1つ持つから、(1) より
# A n c ≤ ∑ i = N + 1 ∞ [ n p i ] ≤ n ∑ i = N + 1 ∞ 1 p i < n 2 {\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}}}
#Anc = n − #An より
n/2 < #An …(3)
(2), (3) より n/2 < 2N √n, ∴ n < 22<i>N+2。これは n の任意性に矛盾。（証明終）
双子素数に限ると、逆数和は B2 = 1.902… に収束することが証明されている（ブルン定数）。
(a, m) = 1 のとき、等差数列： には素数の項が無数に含まれている。（ディリクレの算術級数定理） 素数 p に対して、(a, p) = 1 ⇒ ap−1 ≡ 1 (mod p)（フェルマーの小定理） p が素数 ⇔ (p − 1)! ≡ −1 (mod p)（ウィルソンの定理） 素数の2乗差は 5 の倍数, 3 の倍数, 8 の倍数のいずれかである。
5 ( = 32 − 22), 16 ( = 52 − 32), 21 ( = 52 − 22), 24 ( = 72 − 52), 40 ( = 72 − 32), …
n 番目の素数を求める素数生成式は存在しないと主張されることがあるが、これは誤りである[12]。
オイラーの発見した式：
f(n) = n2 − n + 41
は、自然数 n が で全て素数となる。これは、虚二次体 Q ( − 163 ) {\displaystyle \mathbb {Q} ({\sqrt {-163}})} の類数が 1 であることと関係している[13][14]。一般に、 で多項式 f(n) = n2 − n + p が素数の値を取るとき、素数 p の値を「オイラーの幸運数」という。p = 2, 3, 5, 11, 17, 41（(sequence A014556 in the OEIS)）
f(n) = 36<i>n2 − 810<i>n + 2753
は n = 0, …, 44 で全て素数となる。 同様に
103<i>n2 − 3945<i>n + 34891 (Ruby) 47<i>n2 − 1701<i>n + 10181 (Fung)
は で全て素数となる。
36<i>n2 − 2358<i>n + 36809 (Willium)
は で絶対値は全て素数となる。
高い次数での多項式はあまり知られていないが
n3 − 34<i>n2 + 381<i>n − 1511 (Goetgheluck) 2<i>n3 − 45<i>n2 + 331<i>n − 3191 (Goetgheluck)
は で絶対値は全て素数となる。 ただし の で −107 を取るなど、同じ素数が何度も出現する場合がある。
多変数の多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、k + 2 が素数となる必要十分条件は、次のディオファントス方程式が自然数解を持つことである[15]：
wz + h + j − q = 0 (gk + 2<i>g + k + 1)(h + j) + h − z = 0 (16<i>k + 1)3(k + 2)(n + 1)2 + 1 − f2 = 0 2<i>n + p + q + z − e = 0 e3(e + 2)(a + 1)2 + 1 − o2 = 0 (a2 − 1)y2 + 1 − x2 = 0 16<i>r2y4(a2 − 1) + 1 − u2 = 0 n + l + v − y = 0 (a2 − 1)l2 + 1 − m2 = 0 ai + k + 1 − l − i = 0 [{a + u2(u2 − a)}2 − 1](n + 4<i>dy)2 + 1 − (x + cu)2 = 0 p + l(a − n − 1) + b(2<i>an + 2<i>a − n2 − 2<i>n − 2) − m = 0 q + y(a − p − 1) + s(2<i>ap + 2<i>a − p2 − 2<i>p − 2) − x = 0 z + pl(a − p) + t(2<i>ap − p2 − 1) − pm = 0
誤解されやすいが、素数が無数に存在することの、#ユークリッドによる証明で使われる手順からは、必ずしも素数を得ることができない。なぜなら最初の仮定「最大の素数 pn が存在する」が正しくないからである。実際に、n = 6 で
2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509
と、自明でない約数に分解できてしまう（最小の反例）。
メルセンヌ素数：2n − 1（n は素数が必要、n = 2, 3, 5, 7, 13, …） フェルマー素数：22n + 1 オイラー素数：n2 + 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 の素数階乗） レピュニット 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 と 2<i>p + 1 がともに素数） 安全素数（p と (p − 1) / 2 がともに素数） スーパー素数（素数列における素数番目の素数） 切り捨て可能素数（与えられた基数において 0 を含まず、左右から数を取っていった数がすべて素数である素数） 陳素数（p + 2 が半素数またはともに素数） 正則素数（円の p 分体の類数を割り切らない奇素数） 非正則素数（円の p 分体の類数を割り切る奇素数） フィボナッチ素数（フィボナッチ数の数列に含まれる素数） その他の素数 n2 + 1 の形で表せる素数：2, 5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, …（(sequence A002496 in the OEIS)） n4 + 1 の形で表せる素数：2, 17, 257, 1297, 65537, 160001, …（(sequence A037896 in the OEIS)） n4 + (n + 1)4 の形で表せる素数：17, 97, 337, 881, 3697, …（(sequence A152913 in the OEIS)）
双子素数の予想：双子素数は無数に存在する、という予想。 ゴールドバッハの予想：6 以上の全ての偶数は 2 つの奇素数の和で表すことができる、という予想。 弱いゴールドバッハ予想：7 以上の全ての奇数は 3 つの素数の和で表すことができる、という予想。ただしハラルド・ヘルフゴットによる証明が2013年に発表されている[16][17][18]。 ルジャンドル予想：全ての n に対し、n2 と (n + 1)2 の間に素数が存在するかという予想。 既知のフェルマー素数以外に、フェルマー数にフェルマー素数は存在するか？ メルセンヌ素数は無数に存在するか？ ソフィー・ジェルマン素数、安全素数は無数に存在するか？ フィボナッチ数列には、素数である項が無数に現れるか？（フィボナッチ素数） 幸運数でも素数でもあるような数は無数に存在するか？ ハッピー素数は無数に存在するか？ n2 + 1 の形の素数は無数に存在するか？（ブニャコフスキー予想）
長い間、数論、その中でもとりわけ素数に関する研究は、その分野以外での応用の全くない純粋数学の見本と見なされていた。特に、イギリスの数論研究者であるハーディは、自身の研究が軍事的に何の重要性も持たないことを誇っていた。しかし、この見方は1970年代には覆されてしまった。素数が公開鍵暗号のアルゴリズムに使用できると広く知られるようになったためである。現在では素数はハッシュテーブルや擬似乱数生成にも用いられ、工学的応用上重要度の高いものとなっている。
公開鍵暗号のアルゴリズムとして、RSA暗号やディフィー・ヘルマン鍵共有といった、大きな数の素因数分解は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの（大きな）素数の掛け算は比較的簡単に（効率的に）行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。
自然界に現れる素数の一例として、素数ゼミと呼ばれるセミの一種がいる。アメリカ合衆国に分布するこのセミの成虫は、ある周期ごとに、13年ないしは17年間の周期で大量発生する。成虫になった後は、数週間だけを地上で成虫として過ごし交配と産卵を行う。このセミが素数周期で発生する理由として、寄生虫や捕食者に対抗するための進化であるという説や近縁種との交雑を避けるためであるという説がある。つまり、もしこのセミが12年の発生周期を持っていた場合、12の約数である2, 3, 4, 6年の寿命を持つ捕食者と同時に発生してしまうことになり、捕食対象にされやすくなる。また、地理的に近い場所で12年周期と15年周期のセミが存在した場合、60年ごとに2種は同時に発生し、交雑してしまう可能性がある。すると、雑種は発生周期がズレてしまい、同種のセミとの交尾の機会が失われる。素数の周期を持つものは交雑が起こりにくく、淘汰されにくいと考えられる[19]。
また、ゼータ関数上の零点の分布の数式が、原子核のエネルギー間隔を表す式と一致することを示し、素数と核物理現象との関連性が示唆されている。
整数の平方根や円周率などのように、素数にも語呂合わせによる記憶術がある。以下に挙げる。
Text "和書" ignored (help); Unknown parameter |coauthors= ignored (|author= suggested) (help) Text "和書" ignored (help); Unknown parameter |coauthors= ignored (|author= suggested) (help); Check date values in: |date= (help) Text "和書" ignored (help); Check date values in: |date= (help) Text "和書" ignored (help) Text "和書" ignored (help) Text "和書" ignored (help); Unknown parameter |origdate= ignored (|orig-year= suggested) (help) - 第2刷 2012：加筆含む。 Text "和書" ignored (help); Check date values in: |date= (help) Text "和書" ignored (help) Text "和書" ignored (help)
違法素数 エマープ エラトステネスの篩 巨大な素数の一覧 コープランド-エルデシュ定数 素数の一覧 ピタゴラス素数 プライム (小惑星) - 小惑星番号7919が1000番目の素数であることに因む小惑星。
in nLab at PlanetMath.org.