素数

素数（そすう、）とは、 以上の自然数で、正の約数が と自分自身のみであるもののことである。正の約数の個数が である自然数と言い換えることもできる。 より大きい自然数で素数でないものは合成数と呼ばれる。
日本では、 の日本語への訳語は「素数」とすることが1881年（明治14年）に決まった。
一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環 formula_1 での素数は有理素数（ゆうりそすう、）と呼ばれることもある。
最小の素数は である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。
素数が無数に存在することは、紀元前3世紀頃のエウクレイデス（以下ユークリッド）の著書『原論』で既に証明されていた。そこでの証明は、背理法により次のようになる：
自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。
分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2021年4月現在で知られている最大の素数は、2018年12月7日に発見された、それまでに分かっている中で51番目のメルセンヌ素数 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ。
定義と例.
素数とは、自明な正の因数（ と自分自身）以外に因数を持たない自然数であり、 でない数のことである。つまり、正の因数の個数が 2 である自然数である。
例えば、 は、正の因数が のみなので素数である。
素数でない 以上の自然数を合成数と呼ぶ。
合成数であることの判定法として、たとえば下記の4条件がある：
逆に、この4条件を、全て満たさない数でも素数とは限らない。例えば、 は、正の因数が なので素数ではない。
また、 以外の素数は、最も近い6の倍数との差が か である。
 でない素数は奇数であり、奇素数と呼ぶ。
100以下の素数は25個存在し、小さい順に次の通りである。
さらに、1000以下の素数は100以下のものを含め168個存在する（100以下を除けば143個）。101以上で1000以下の素数は小さい順に次の通りである。
素因数分解の可能性・一意性.
「 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する（算術の基本定理）。素因数分解の可能性から、素数全体の成す集合は、2以上の自然数全体の成す集合とその乗法からなる半群の最小の生成系である。
素数の定義である「 と自分自身でしか割り切れない」という条件（既約性）は、抽象代数学において、環の既約元の概念（一部の環では素元の概念と一致する）に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えばネーター環では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。
1 は素数か.
現代の定義では は素数ではない。歴史を通しても を素数に含めない数学者が多数派であったが、20世紀初頭の環論の成熟まで定義は統一されていなかった。プラトンやアリストテレスを含むほとんどの古代ギリシアの哲学者は を数とさえ見なさず、素数性の考察の対象としなかった。スペウシッポスは を数と見なし素数としたが、当時としては異端であった。この時代には素数を奇数の一部分と考え、 を素数に含めない数学者もいた（ただしユークリッドをはじめとする多数派は を素数に含めている）。アラビアではおおむね古代ギリシアに倣って は数でないとされた。中世からルネサンスにかけて、 が数として扱われるようになり、 を最初の素数とする数学者も現れた。18世紀半ば、ゴールドバッハはオイラーに宛てた書簡で を素数に挙げている（ただしオイラー自身は を素数とは考えていなかった）。19世紀にも少数派だが を素数に含める数学者はかなりいた。ハーディの『A Course of Pure Mathematics』では、1933年に出版された第6版までは を素数に含めているが、1938年の第7版から を最小の素数とするよう改訂されている。の を含む素数表は1956年まで出版された。ルベーグは を素数だと考えた最後の専門的な数学者だと言われている。
 も素数と定義すると、素数に関する多くの定理で、もとの「素数」を「 以外の素数」と呼び替える記述の修正が必要になる。例えば の素因数分解は、（積の順序を除いても）
と無数に与えられることになり、一意性は「 を含む素数」については成り立たない。エラトステネスの篩においては、 も素数とすると、 の倍数（すなわち他のすべての数）を消去し、残った唯一の数 を出力するので機能しない。さらに、 以外の素数で成り立つ様々な性質がある（例えば、自然数とそれに対応するオイラーのφ関数や約数関数の値との関係など）。20世紀初頭までに は素数ではなく「単数」という特別な分類に属するという見方が一般的になった。
歴史.
紀元前1600年頃のエジプト第2中間期において、素数の初等的な性質が部分的に知られていたことが、リンド数学パピルスなどの資料によって示唆されている。例えば分数をエジプト式分数で表す場合、素数と合成数の場合で異なる計算をしなければならないからである。しかし、記録に残っている限りにおいて、明確に素数を研究対象としたのは古代ギリシア人が最初である。紀元前約300年頃に書かれたユークリッドの『原論』には素数が無数に存在することや、その他の素数の性質が証明されている。また、ユークリッドはメルセンヌ素数から完全数を構成する方法を示している。ギリシアの数学者、エラトステネスに因んで名付けられたエラトステネスの篩は、素数を列挙するための計算方法である。
古代ギリシア時代の後、17世紀になるまで素数の研究にはそれほどの進展が無かった。1640年に、ピエール・ド・フェルマーはフェルマーの小定理を（未証明ではあるが）述べた。この定理は後にライプニッツとオイラーによって証明された。
素数が無数に存在することは既に古代ギリシア時代から知られていて、ユークリッドが彼の著作『原論』の中で証明している。
他の証明.
上記のユークリッドによる証明以外にも、素数が無数に存在することの証明方法が存在する。
素数判定と素因数分解.
与えられた自然数 が素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。最も素朴な方法は、 から 以下の素数まで順番に割っていく、試し割り法と呼ばれる方法である。 が 以下の全ての素数で割り切れなければ は素数である。試し割り法は、 が大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割り法よりも高速なアルゴリズムが考案されている。また、特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。
上記の通り2を除く偶数、2桁以上で末尾が5の数、数字和が3の倍数となる数は合成数と分かるのでそれを省き、7以上の素数を順番に割る方法がある。
分布.
ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。
これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。
 以下の素数の個数を （素数計数関数）とすると、
が成り立つ。この定理は、1792年に15歳のカール・フリードリヒ・ガウスによって予想されていた（ガウスが最初に予想したのかどうかは不明）。この定理の証明は、ゼータ関数と複素関数論を用いる高度なものであったが、1949年にアトル・セルバーグとポール・エルデシュは独立に初等的な証明を与えた。この評価式はリーマン予想を仮定すると大幅に精度をよくすることができる。
次のような定理もある。
この主張は「任意の素数 の次の素数は 未満」とも言い換えられる。したがって、2017年5月現在知られている最大の素数 の次の素数は 未満である。
一方で、例えば と の間に素数が存在するかという問題は未解決である（ルジャンドル予想）。
素数が全く無い区間は、いくらでも長いものがあることが知られている。 に対して、連続する 個の自然数 はそれぞれ、それらより小さい で割り切れるので、どれも素数でない。 は任意にとれるから、素数が全く無いいくらでも長い区間があると言える。これは一例にすぎず、実際にはもっと小さい所で、素数が全く無い長い区間が生じるようである。例えば、 から まで個連続で合成数である。
素数計数.
2015年に、ゴールドバッハの予想検証プロジェクトは 以下の全ての素数（9京5676兆2609億388万7607個、約 10個）を計算したと報告したが、結果は保存されていない。しかしながら、素数計数関数を計算するには、実際に素数を数えるより高速な公式が存在する。この公式を使って、 以下に 19垓2532京391兆6068億396万8923個（約 2個）の素数があると計算された。
また、別の計算によると、リーマン予想が真であると仮定した場合、 以下に 184垓3559京9767兆3492億86万7866個（約 2個）の素数が存在する。
素数に関連する主な性質.
素数の逆数和.
素数の逆数の和は（無限大に）発散する。この命題は『素数は無数に存在する』という命題を含んでいる（有限個ならば収束、すなわち発散しないはずである）が、それだけではなく素数の分布に関してより多くの情報を提供している。
この結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。以下の証明はポール・エルデシュによる、より直接的で、また簡潔な証明である。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。
素数の逆数和は収束すると仮定する。 番目の素数を で表すと、
を満たす が存在する。
 以下の自然数のうち最大素因数が 以下のものからなる集合を とする。任意の に対して、
と表示すると、 は高々 通り、 より
 の元は、 以上の素因数を少なくとも1つ持つから、(1) より
 より
(2), (3) より , ∴ 。これは の任意性に矛盾。（証明終）
双子素数に限ると、逆数和は に収束することが証明されている（ブルン定数）。
素数生成式.
 番目の素数を求める素数生成式は存在しないと主張されることがあるが、これは誤りである（ウィルソンの定理やを用いたものが存在する）。しかしながら、そのような式でなものは知られていない。
1変数多項式.
オイラーの発見した式：
は、自然数 が で全て素数となる。これは、虚二次体 formula_5 の類数が であることと関係している。一般に、 で多項式 が素数の値を取るとき、素数 の値を「オイラーの幸運数」という。オイラーの幸運数は の6つのみであり、これらはすべてヘーグナー数と対応する。
ルビーの多項式：
は で全て素数となる。
同様に
は で全て素数となる。
は で絶対値は全て素数となる。
高い次数での多項式はあまり知られていないが
は で絶対値は全て素数となる。
ただし の で を取るなど、同じ素数が何度も出現する場合がある。
多変数多項式.
多変数の多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、 が素数となる必要十分条件は、次のディオファントス方程式が自然数解を持つことである：
応用.
長い間、数論、その中でもとりわけ素数に関する研究は、その分野以外での応用の全くない純粋数学の見本と見なされていた。特に、イギリスの数論研究者であるハーディは、自身の研究が軍事的に何の重要性も持たないことを誇っていた。しかし、この見方は1970年代には覆されてしまった。素数が公開鍵暗号のアルゴリズムに使用できると広く知られるようになったためである。現在では素数はハッシュテーブルや擬似乱数生成にも用いられ、工学的応用上重要度の高いものとなっている。
公開鍵暗号.
公開鍵暗号のアルゴリズムとして、RSA暗号やディフィー・ヘルマン鍵共有といった、大きな数の素因数分解は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの（大きな）素数の掛け算は比較的簡単に（効率的に）行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。
自然界の素数.
自然界に現れる素数の一例として、素数ゼミと呼ばれるセミの一種がいる。アメリカ合衆国に分布するこのセミの成虫は、ある周期ごとに、13年ないしは17年間の周期で大量発生する。成虫になった後は、数週間だけを地上で成虫として過ごし交配と産卵を行う。このセミが素数周期で発生する理由として、寄生虫や捕食者に対抗するための進化であるという説や近縁種との交雑を避けるためであるという説がある。つまり、もしこのセミが12年の発生周期を持っていた場合、12の約数である2, 3, 4, 6年の寿命を持つ捕食者と同時に発生してしまうことになり、捕食対象にされやすくなる。また、地理的に近い場所で12年周期と15年周期のセミが存在した場合、60年ごとに2種は同時に発生し、交雑してしまう可能性がある。すると、雑種は発生周期がずれてしまい、同種のセミとの交尾の機会が失われる。素数の周期を持つものは交雑が起こりにくく、淘汰されにくいと考えられる。
また、ゼータ関数上の零点の分布の数式が、原子核のエネルギー間隔を表す式と一致することを示し、素数と核物理現象との関連性が示唆されている。
素数砂漠.
自然数で素数でないものが連続している区間を「素数砂漠」という。例えば は「長さ 5 の素数砂漠」である。素数砂漠を挟む2個の素数は 以上であるため、共に奇数である。このことから、素数砂漠の長さは必ず奇数である。いくらでも長い素数砂漠が構成できる（#分布を参照）。
初めから60個の素数の間隔は
語呂合わせ.
1、2桁の素数の暗記方法として、次のような語呂合わせが考え出されている。
素数の一般項.
素数の一般項で、よく知られているものは、