素数

素数（または素数）は、1 より大きい自然数で、2 つのより小さい自然数の積ではない数です。1より大きい自然数で素数でない数は合成数と呼ばれます。たとえば、5 は、1 × 5または5 × 1 の積として表記する場合、5 自身を含む唯一の方法であるため、素数です。一方、4 は、両方の数が 4 より小さい積 (2 × 2) であるため、合成数です。素数は、算術の基本定理により、数論において中心的な存在です。算術の基本定理とは、1 より大きいすべての自然数は、それ自体が素数であるか、または、その位数まで一意となる素数の積として因数分解できるかのいずれかである、というものです。

素数であるという性質は素数性と呼ばれる。与えられた数が素数であるかどうかを調べる単純だが時間のかかる方法は試し割りと呼ばれ、2から までの任意の整数の倍数であるかどうかをテストする。より高速なアルゴリズムには、高速だが誤りの可能性が小さいミラー・ラビン素数性テストや、多項式時間で常に正しい答えを出すが実用的であるには遅すぎるAKS素数性テストなどがある。特に高速な方法は、メルセンヌ数などの特殊な形式の数に対して利用できる。2024年10月現在、最大の素数は41,024,320桁のメルセンヌ素数である。^{[1] [2]}${\displaystyle n}$${\displaystyle n}$${\displaystyle {\sqrt {n}}}$^{[アップデート]}

紀元前300年頃にユークリッドが証明したように、素数は無限にあります。素数と合成数を区別する単純な公式は知られていません。しかし、大きな自然数における素数の分布は、統計的にモデル化できます。その方向での最初の結果は、19世紀末に証明された素数定理であり、ランダムに選択された大きな数が素数である確率は、その桁数、つまり対数に反比例するというものです。

素数に関する歴史的な疑問の多くは、いまだに解決されていない。その中には、2 より大きいすべての偶数は 2 つの素数の和として表せるというゴールドバッハの予想や、差が 2 である素数のペアは無限に存在するという双子素数予想などがある。こうした疑問から、数の解析的側面や代数的側面に焦点を当てた数論のさまざまな分野の発展が促進された。素数は、大きな数を素因数に分解することの難しさを利用する公開鍵暗号など、情報技術のさまざまなルーチンで使用されている。抽象代数では、素数のように一般化された方法で動作するオブジェクトには、素元と素イデアルが含まれる。

自然数（1、2、3、4、5、6など）が1より大きく、2つのより小さい自然数の積として表すことができない場合、その数は素数（または素数）と呼ばれます。1より大きい数で素数でない数は合成数と呼ばれます。^[3]言い換えれば、項目を複数の項目からなるより小さな等しいサイズのグループに分割できない場合、^[4]または点を幅と高さが1点を超える長方形のグリッドに配置できない場合、 は素数です。 ^[5]たとえば、1から6までの数の中で、2、3、5は素数です。^[6]これらは（余りなしで）割り切れる数が他にないからです。1は定義で明示的に除外されているため、素数ではありません。4 = 2 × 2と6 = 2 × 3はどちらも合成数です。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

自然数の約数は、割り切れる自然数です。すべての自然数は、1 とそれ自身の両方を約数として持ちます。他の約数を持つ場合、それは素数ではありません。これは、素数の同等の定義につながります。つまり、素数とは、ちょうど 2 つの正の約数を持つ数です。その 2 つは、1 とその数自身です。1 には 1 つの約数、つまりそれ自身しかないため、この定義では素数ではありません。^[7]同じことを別の方法で表現すると、数が1 より大きく、かつ、どの数も割り切れない場合、その数は素数です。^[8]${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2,3,\dots ,n-1}$${\displaystyle n}$

最初の25個の素数（100未満のすべての素数）は次のとおりです。^[9]

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（OEISのシーケンスA000040）。​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​

2より大きい偶数は どれも素数ではありません。なぜなら、そのような数はどれも積 として表すことができるからです。したがって、2以外のすべての素数は奇数であり、奇素数と呼ばれます。^[10]同様に、通常の10進法で表すと、5より大きいすべての素数は1、3、7、または9で終わります。他の数字で終わる数はすべて合成数です。つまり、0、2、4、6、または8で終わる10進数は偶数であり、0または5で終わる10進数は5で割り切れます。^[11]${\displaystyle n}$${\displaystyle 2\times n/2}$

素数全体の集合は、 （太字の大文字P）^[12]または（黒板太字の大文字P） ^[13]で表されることもあります。${\displaystyle \mathbf {P} }$${\displaystyle \mathbb {P} }$

紀元前1550年頃のリンド数学パピルスには、素数と合成数のさまざまな形式のエジプトの分数展開が記載されています。 ^[14]しかし、素数の研究に関する現存する最古の記録は、それらをプロトス・アリトモス（πρῶτος ἀριθμὸς ）と呼んだ古代ギリシャの数学者によるものです。ユークリッドの原論（紀元前300年頃）は、素数の無限性と算術の基本定理を証明し、メルセンヌ素数から完全数を構成する方法を示しています。^[15]もう一つのギリシャの発明であるエラトステネスの篩は、今でも素数のリストを作成するために使用されています。^{[16] [17]}

西暦1000年頃、イスラムの数学者イブン・アル＝ハイサム（アルハゼン）はウィルソンの定理を発見し、素数はを割り切れる数であると特徴づけた。彼はまた、すべての完全数はメルセンヌ素数を使ったユークリッドの構成から来ると推測したが、証明することはできなかった。^[18]もう一人のイスラムの数学者イブン・アル＝バンナ・アル＝マラクシは、エラトステネスのふるいは、上限の平方根までの素因数だけを考慮することで高速化できることを観察した。^[17]フィボナッチはイスラム数学の革新をヨーロッパに持ち込んだ。彼の著書『算盤の書』 （1202年）は、平方根までの約数だけを使って素数かどうかをテストするための試し割りを記述した最初の本である。 ^[17]${\displaystyle n}$${\displaystyle (n-1)!+1}$

1640年、ピエール・ド・フェルマーは（証明なしに）フェルマーの小定理（後にライプニッツとオイラーにより証明された）を述べた。^{[19]フェルマーはまた、}フェルマー数 の素数性を調査した。^[20]また、マリン・メルセンヌはメルセンヌ素数、すなわち自身が素数である形の素数を研究した。 [ ^21]クリスチャン・ゴールドバッハは、すべての偶数は2つの素数の和であるというゴールドバッハ予想を、1742年にオイラーに宛てた手紙の中で定式化した。 ^[22]オイラーは、すべての完全偶数はメルセンヌ素数から構成できるというアルハゼンの予想（現在のユークリッド・オイラーの定理）を証明した。 ^[15]彼は素数の無限性と素数の逆数の和の発散を証明する際に、この分野に数学的解析学の手法を導入した。^[23] 19世紀初頭、ルジャンドルとガウスは、 が無限大に近づくにつれ、 までの素数の数は（は の自然対数）に漸近すると予想した。この高い素数密度の弱い帰結は、任意の に対してとの間に素数が存在するという、ベルトランの公準であり、これは1852年にパフヌティ・チェビシェフによって証明された。^[24]ベルンハルト・リーマンの1859年のゼータ関数に関する論文のアイデアは、ルジャンドルとガウスの予想を証明するための概要を描いた。密接に関連するリーマン予想は未証明のままであるが、リーマンの概要は1896年にアダマールとラ・ヴァレー・プッサンによって完成され、その結果は現在では素数定理として知られている。^[25] 19世紀のもう一つの重要な成果は、等差数列に関するディリクレの定理であり、特定の等差数列には無限個の素数が含まれるというものである。^[26]${\displaystyle 2^{2^{n}}+1}$${\displaystyle 2^{p}-1}$${\displaystyle p}$ ${\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots }$${\displaystyle x}$${\displaystyle x}$${\displaystyle x/\log x}$${\displaystyle \log x}$${\displaystyle x}$${\displaystyle n>1}$${\displaystyle n}$${\displaystyle 2n}$

多くの数学者が、実際に試し割りが適用できる数よりも大きな数に対する素数判定に取り組んできました。特定の数形式に限定された手法としては、フェルマー数に対するペパンの検定（1877年）^{[27] 、} プロスの定理（1878年頃）^[28] 、ルーカス・レーマー素数判定（1856年発案）、一般化されたルーカス素数判定^[17]などがあります。

1951年以来、知られている最大の素数はすべて、コンピュータによるこれらのテストを使用して発見されています。^[a]より大きな素数の探索は、インターネットメルセンヌ素数探索やその他の分散コンピューティングプロジェクトを通じて、数学界以外でも関心を集めています。^{[9] [30]}素数は純粋数学以外ではほとんど応用がないという考えは、1970年代に公開鍵暗号とRSA暗号が発明され、素数が基礎として使用されるようになったときに打ち砕かれました。^[33]

コンピュータによる素数判定と因数分解の実用的重要性が増したことにより、無制限の形式の大きな数を処理できる改良された方法が開発されました。^{[16] [34] [35]}素数に関する数学的理論も、任意の長さの素数の等差数列が存在するというグリーン・タオ定理（2004年）や、有限サイズの素数ギャップが無限に存在するというYitang Zhangによる2013年の証明によって前進しました。^[36]

初期のギリシャ人のほとんどは、1を数としても考えていなかったため^{[37] [38]、 1の素数性を考慮することはできなかった。}ニコマコス、イアンブリコス、ボエティウス、カッシオドルスなど、ギリシャおよび後期ローマの伝統に属する少数の学者も、素数は奇数の細分であると考えたため、2も素数とは考えなかった。しかし、ユークリッドや他のギリシャの数学者の大多数は、2を素数とみなした。中世イスラムの数学者は、 1は数ではないという点でギリシャ人の大部分に従った。^[37]中世およびルネサンスまでに、数学者は1を数として扱うようになり、17世紀までには、一部の数学者が1を最初の素数として含めた。^[39] 18世紀半ば、クリスティアン・ゴールドバッハは、レオンハルト・オイラーとの書簡の中で1を素数として挙げている。^[40]しかし、オイラー自身は1を素数とは考えていなかった。^[41] 19世紀の多くの数学者は依然として1を素数とみなしており、^[42]デリック・ノーマン・レーマーは1914年に出版した1000万未満の素数のリストに1を含めた。^{[43] 1を含む素数のリストは}1956年まで出版され続けた。^{[44] [45]}しかし、この頃、20世紀初頭までに、数学者は1を素数として分類すべきではないことに同意し始めた。^[42]

1 が素数とみなされると、素数に関する多くの記述を不自然に言い換える必要が出てきます。たとえば、算術の基本定理は、1 より大きい素数への因数分解という観点から言い換える必要があります。なぜなら、すべての数は、1 の任意の数による因数分解を複数持つことになるからです。 ^[42]同様に、エラトステネスのふるいも、 1 を素数として扱うと正しく動作しません。なぜなら、1 の倍数 (つまり、他のすべての数) がすべて除去され、1 という単一の数だけが出力されるからです。^[45]素数のその他のより技術的な特性も、数 1 には当てはまりません。たとえば、オイラーのトーティエント関数や約数の合計関数の式は、素数と 1 では異なります。^{[46] 20 世紀初頭までに、数学者は、1 は素数としてリストされるべきではなく、「}単位」として独自の特別なカテゴリに分類されるべきだということに同意し始めました。^[42]

数を素数の積として表すことを、その数の素因数分解といいます。例:

${\displaystyle {\begin{aligned}50&=2\times 5\times 5\\&=2\times 5^{2}.\end{aligned}}}$

積の項は素因数と呼ばれます。同じ素因数が複数回出現することもあります。この例では、素因数が2つあります。素数が複数回出現する場合、累乗を使用して同じ素数の複数のコピーをグループ化することができます。たとえば、上記の積の2番目の書き方では、はの平方または2乗を表します。${\displaystyle 5.}$${\displaystyle 5^{2}}$${\displaystyle 5.}$

素数が数論や数学全般にとって中心的な重要性を持つのは、算術の基本定理に由来する。^[47]この定理は、1 より大きいすべての整数は、1 つ以上の素数の積として表すことができることを述べている。さらに強い意味として、この積は、同じ数の任意の 2 つの素因数分解は、順序は異なる可能性があるものの、同じ素数のコピーが同じ数だけ存在するという意味で一意である。^{[48]したがって、}整数因数分解アルゴリズムを使用して因数分解を見つける方法は多数あるが、それらはすべて同じ結果を生成する必要がある。したがって、素数は自然数の「基本的な構成要素」と考えることができる。^[49]

素因数分解の一意性の証明のいくつかはユークリッドの補題に基づいています。が素数であり、整数の積を割り切れる場合、を割り切れるか、 を割り切れる（またはその両方）場合。^[50]逆に、数が積を割り切れるときに常に積の少なくとも1つの因数を割り切れるという性質を持つ場合、は素数でなければなりません。^[51]${\displaystyle p}$${\displaystyle p}$${\displaystyle ab}$${\displaystyle a}$${\displaystyle b,}$${\displaystyle p}$${\displaystyle a}$${\displaystyle p}$${\displaystyle b}$${\displaystyle p}$${\displaystyle p}$

素数は 無限に存在する。別の言い方をすると、

2、3、5、7、11、13、...

素数の無限性には終わりがない。この命題は古代ギリシャの数学者ユークリッドにちなんでユークリッドの定理と呼ばれている。この命題の最初の証明はユークリッドによるものとされているからである。素数の無限性については、オイラーによる解析的証明、フェルマー数に基づくゴールドバッハの証明^[52]、一般位相幾何学を用いたファーステンベルクの証明^[53]、クンマーのエレガントな証明^[54]など、他にも多くの証明が知られている。

ユークリッドの証明^{[55]は、素数の}有限リストはどれも不完全であることを示している。鍵となる考え方は、与えられたリスト内の素数を掛け合わせて足し合わせることである。リストが素数で構成されている場合、これは数を与える。 ${\displaystyle 1.}$${\displaystyle p_{1},p_{2},\ldots ,p_{n},}$

${\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}$

基本定理によれば、は素因数分解できる。 ${\displaystyle N}$

${\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}$

1 つ以上の素因数を持つ。はこれらの因数のそれぞれで割り切れますが、指定されたリスト内のどの素数で割っても余りは 1 になります。したがって、 の素因数はいずれも指定されたリストには含まれません。すべての素数の有限リストは存在しないため、素数は無限に存在することになります。 ${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$

最小の素数の積に1を加えた数をユークリッド数と呼ぶ。^[56]最初の5つは素数だが、6番目、

${\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}$

合成数です。

素数に対する効率的な公式は知られていない。例えば、複数の変数であっても、素数値だけを取る非定数多項式は存在しない。 ^{[57]しかし、すべての素数、または素数だけをエンコードする式は数多く存在する。1つの可能な公式は}ウィルソンの定理に基づいており、数2を何度も生成し、他のすべての素数を1回だけ生成する。^{[58]また、9つの変数と1つのパラメータからなる}ディオファントス方程式の集合があり、次の特性を持つ。パラメータが素数となるのは、結果として得られる方程式系が自然数に対して解を持つ場合のみである。これを使用して、すべての正の値が素数であるという特性を持つ単一の式を得ることができる。 ^[57]

素数生成公式の他の例としては、ミルズの定理とライトの定理が挙げられる。これらは、実定数とがあり、 ${\displaystyle A>1}$${\displaystyle \mu }$

${\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor }$

は、最初の式では任意の自然数に対して素数であり、2番目の式では任意の数の指数に対して素数である。 ^[59]ここで、は床関数を表し、問題の数以下の最大の整数である。しかし、これらは素数を生成するのに役立たない。なぜなら、またはの値を計算するために、まず素数を生成しなければならないからである^[57]${\displaystyle n}$${\displaystyle \lfloor {}\cdot {}\rfloor }$${\displaystyle A}$${\displaystyle \mu .}$

素数に関する予想は数多く提出されている。多くの場合初等的な定式化しか持たないこれらの予想の多くは何十年にもわたって証明に耐えてきた。1912年のランダウの問題4つすべてが未だに解決されていない。 ^[60]その1つがゴールドバッハの予想で、 2より大きいすべての偶数は2つの素数の和として表せるというものである。 ^[61] 2014年の時点で、この予想は^[62]までのすべての数について検証されている。これよりも弱い主張も証明されている。例えば、ヴィノグラドフの定理によれば、十分に大きい奇数はすべて3つの素数の和として表せる。^[63]チェンの定理によれば、十分に大きい偶数はすべて素数と半素数（2つの素数の積）の和として表せる。^[64]また、10より大きい任意の偶数は6つの素数の和として表せる。^[65]このような問題を研究する数論の分野は加法数論と呼ばれています。^[66]${\displaystyle n}$^[update]${\displaystyle n=4\cdot 10^{18}.}$

もう一つのタイプの問題は、連続する素数間の差である素数ギャップに関するものである。任意の大きさの素数ギャップの存在は、任意の自然数に対して、その数列が合成数で構成されていることに注意することでわかる^[67]。しかし、大きな素数ギャップはこの議論が示すよりずっと早い時期に発生する。^[68]たとえば、長さ 8 の最初の素数ギャップは素数 89 と 97 の間にあり、^[69]よりもはるかに小さい。差が 2 である素数のペアである双子素数は無限に存在すると予想されており、これが双子素数予想である。ポリニャックの予想は、より一般的には、すべての正の整数に対して、差が である連続する素数のペアが無限に存在することを述べている。 ^[70]アンドリカの予想、^[70]ブロカールの予想、^[71]ルジャンドルの予想、^[72]オッペルマンの予想^[71]はすべて、からまでの素数間の最大ギャップは最大でおよそ であるはずであることを示唆しており、これはリーマン予想から導かれることが知られている結果であるが、はるかに強いクラメールの予想では、最大ギャップサイズが と設定されている。 ^[70]素数のギャップは、2つ以上の素数間の差のパターンである素数組に一般化できる。その無限性と密度は、最初のハーディ・リトルウッド予想の対象であり、これは、素数が、素数定理によって与えられた密度を持つランダムな数列と同様に動作するという経験則に動機付けられている。 ^[73]${\displaystyle n!+2,n!+3,\dots ,n!+n}$${\displaystyle n-1}$${\displaystyle n.}$${\displaystyle 8!=40320.}$${\displaystyle k,}$${\displaystyle 2k.}$ ${\displaystyle 1}$${\displaystyle n}$${\displaystyle {\sqrt {n}},}$${\displaystyle O((\log n)^{2}).}$${\displaystyle k}$

解析的数論は、連続関数、極限、無限級数、および無限と無限小の関連数学の観点から数論を研究します。

この研究分野は、レオンハルト・オイラーと彼の最初の主要な成果であるバーゼル問題の解決から始まりました。この問題は、今日ではリーマンゼータ関数の 値として認識されている無限和の値を求めています。この関数は素数と密接に関連しており、数学における最も重要な未解決問題の1つであるリーマン予想とも関連しています。オイラーは であることを示しました。^[74] この数の逆数 は、広い範囲から一様にランダムに選択された2つの数が互いに素である（共通の因数を持たない）極限確率です。 ^[75]${\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,}$${\displaystyle \zeta (2)}$${\displaystyle \zeta (2)=\pi ^{2}/6}$${\displaystyle 6/\pi ^{2}}$

大きな素数の分布、例えば与えられた大きな閾値より小さい素数がいくつあるかという問題は素数定理によって記述されるが、-番目の素数に対する有効な公式${\displaystyle n}$は知られていない。等差数列に関するディリクレの定理は、その基本形では、線形多項式が

${\displaystyle p(n)=a+bn}$

互いに素な整数を持ち、無限に多くの素数値を取る。この定理のより強い形式は、これらの素数値の逆数の和が発散し、同じ値を持つ異なる線形多項式がほぼ同じ割合の素数を持つということを述べている。高次多項式における素数の割合についての推測は定式化されているが、証明されていないため、（整数引数に対して）無限に多く素数となる二次多項式が存在するかどうかは不明である。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$

素数が無限に存在するというオイラーの証明は、素数の逆数の和を考慮している。

${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.}$

オイラーは、任意の実数 に対して、この和が より大きい素数が存在することを示した。^[76]これは、素数が無限に存在することを示している。なぜなら、素数が有限個であれば、和は を超えて増加するのではなく、最大の素数で最大値に達するからである。この和の増加率は、メルテンスの第2定理によってより正確に記述される。^[77]比較のために、和 ${\displaystyle x}$${\displaystyle p}$${\displaystyle x}$${\displaystyle x}$

${\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}}$

は無限大になるほど増えない（バーゼル問題を参照）。この意味では、素数は自然数の平方よりも頻繁に出現するが、どちらの集合も無限大である。^[78]ブルンの定理によれば、双子素数の逆数の和は、 ${\displaystyle n}$

${\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,}$

は有限である。ブルンの定理により、双子素数は無限に存在するという双子素数予想をオイラー法で解くことはできない。 ^[78]

素数計算関数は より大きくない素数の個数として定義される。^[79]例えば、は 11 以下の素数が 5 個あるためである。マイセル・レーマー法などの方法は、 までの各素数を列挙するよりも速く の正確な値を計算することができる。^[80]素数定理によれば、 はに漸近的であり、 は と表される。 ${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle \pi (11)=5}$${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle \pi (n)}$${\displaystyle n/\log n}$

${\displaystyle \pi (n)\sim {\frac {n}{\log n}},}$

は、が無限大に大きくなるにつれて、と右辺の分数の比が1 に近づくことを意味します。 ^[81]これは、 より小さいランダムに選ばれた数が素数である可能性は、の桁数に（ほぼ）反比例することを意味します。^[82] また、番目の素数は に比例し、^[83] したがって、素数ギャップの平均サイズは に比例します。^[68] のより正確な推定値は、オフセット対数積分によって与えられます^[81]${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n\log n}$${\displaystyle \log n}$${\displaystyle \pi (n)}$

${\displaystyle \pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.}$

等差数列とは、数列内の連続する数がすべて同じ差を持つ有限または無限の数列である。^[84]この差は数列の係数と呼ばれる。 ^[85]例えば、

3、12、21、30、39、…、

は、9を法とする無限等差数列である。等差数列では、すべての数を法で割ったときの余りは同じである。この例では、余りは3である。法9と余り3はどちらも3の倍数であるため、数列のすべての要素も3の倍数である。したがって、この数列には素数が1つだけ含まれており、それは3である。一般に、無限数列は

${\displaystyle a,a+q,a+2q,a+3q,\dots }$

剰余と法が互いに素である場合にのみ、その数列は複数の素数を持つことができる。それらが互いに素である場合、等差数列に関するディリクレの定理は、その数列には無限個の素数が含まれることを主張する。^[86]${\displaystyle a}$${\displaystyle q}$

グリーン・タオ定理は、素数のみからなる任意に長い有限等差数列が存在することを示している。^{[36] [87]}

オイラーは、関数

${\displaystyle n^{2}-n+41}$

は に対して素数を与えるが、それ以降の値の中には合成数が現れる。^{[88] [89]}この現象の説明を求めることで、ヒーグナー数の深層代数的数論と類数問題が生まれた。^[90]ハーディ・リトルウッド予想 F は、整数係数を持つ二次多項式の値の中の素数の密度を、対数積分と多項式係数を用いて予測する。二次多項式が無限に多くの素数値を取ることが証明されたことはない。^[91]${\displaystyle 1\leq n\leq 40}$

ウラム螺旋は、自然数を2次元のグリッドに配置し、原点を囲む同心円状の正方形に螺旋状に並べ、素数が強調表示される。視覚的には、素数は特定の対角線に集中しているように見え、他の対角線には集中していないように見える。これは、一部の二次多項式が他の多項式よりも素数値をとる頻度が高いことを示唆している。^[91]

1859年に始まった数学における最も有名な未解決問題の一つであり、ミレニアム懸賞問題の1つであるリーマン予想は、リーマンゼータ関数の零点がどこにあるかを問うものです。この関数は複素数上の解析関数です。実部が1より大きい複素数の場合、それはすべての整数の無限和と素数の 無限積の両方に等しくなります。 ${\displaystyle \zeta (s)}$${\displaystyle s}$

${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.}$

オイラーによって発見された、和と積のこの等式は、オイラー積と呼ばれています。^[92]オイラー積は算術の基本定理から導き出され、ゼータ関数と素数との密接な関係を示しています。^[93] これは、素数が無限に存在するという別の証明につながります。つまり、素数が有限個しかない場合、和と積の等式は においても有効ですが、和は発散し（これは調和級数です）、積は有限であるため矛盾が生じます。^[94]${\displaystyle s=1}$ ${\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots }$

リーマン予想によれば、ゼータ関数の零点はすべて負の偶数か、実部が1/2の複素数である。^[95]素数定理の最初の証明は、実部が1の零点は存在しないというこの仮説の弱い形に基づいていたが、^{[96] [97]}より基本的な証明もいくつか見つかっている。^{[98]素数計算関数は、}リーマンの明示的な公式によって、各項がゼータ関数の零点の1つに由来する和として表すことができる。この和の主項は対数積分であり、残りの項は和が主項の上下に変動する原因となる。^[99]この意味で、零点は素数がどれだけ規則的に分布しているかを制御する。リーマン予想が正しいとすれば、これらの変動は小さくなり、 素数定理によって与えられる素数の漸近分布は、はるかに短い区間（数に近い区間では長さが の平方根程度）でも成り立つことになる。^[97]${\displaystyle x}$${\displaystyle x}$

モジュラー演算は、自然数を法として、数 のみを使用することで通常の演算を変更します。他の自然数は、 で割った後の余りで置き換えることによって、このシステムにマッピングできます。^[100]モジュラー和、差、積は、整数の通常の和、差、積の結果に同じ余りによる置き換えを実行して計算されます。^[101]整数が等しいことは、モジュラー演算における合同に対応します。と は、で割った後の余りが同じである場合に合同です（ を法として書きます） 。^[102]ただし、この数体系では、すべての非ゼロ数による除算は、法が素数である場合に限り可能です。たとえば、素数を法として、 による除算が可能です。、両辺に を掛けて分母をクリアすると、有効な式 が得られるためです。ただし、合成法 では、 による除算は不可能です。に対する有効な解法はありません。 を で乗じて分母を消去すると、左辺は になり、右辺は または になります。抽象代数の用語では、除算を実行できるということは、素数を法とするモジュラ演算が体、より具体的には有限体を形成し、他の法では環しか生成されず、体は生成されないことを意味します。^[103]${\displaystyle \{0,1,2,\dots ,n-1\}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\equiv y}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 7}$${\displaystyle 3}$${\displaystyle 2/3\equiv 3{\bmod {7}}}$${\displaystyle 3}$${\displaystyle 2\equiv 9{\bmod {7}}}$${\displaystyle 6}$${\displaystyle 3}$${\displaystyle 2/3\equiv x{\bmod {6}}}$${\displaystyle 3}$${\displaystyle 2}$${\displaystyle 0}$${\displaystyle 3}$

素数に関するいくつかの定理は、モジュラー算術を使って定式化できる。例えば、フェルマーの小定理は、 (mod )ならば(mod )である、と述べている 。^[104]これを のすべての選択肢について合計すると、次の式が得られる。 ${\displaystyle a\not \equiv 0}$${\displaystyle p}$${\displaystyle a^{p-1}\equiv 1}$${\displaystyle p}$${\displaystyle a}$

${\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},}$

が素数であるときはいつでも成立する。 ジューガの予想によれば、この等式は が素数であるための十分条件でもある。 ^[105]ウィルソンの定理によれば、整数が素数となるのは、階乗がを法として合同な場合のみである。合成数の場合、その因数の1つがnと の両方を割り切るため、この条件は成立せず、したがって不可能である。^[106]${\displaystyle p}$${\displaystyle p}$ ${\displaystyle p>1}$ ${\displaystyle (p-1)!}$${\displaystyle -1}$${\displaystyle p}$${\displaystyle \;n=r\cdot s\;}$${\displaystyle (n-1)!}$${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$

整数の- 進数順序は、の素因数分解におけるのコピーの数です。同じ概念は、分数の - 進数順序をと定義することで、整数から有理数に拡張できます。任意の有理数の- 進絶対値は と定義されます 。整数にその- 進絶対値を掛けると、その因数分解における の因数が打ち消され、他の素数だけが残ります。2 つの実数間の距離がその距離の絶対値で測定できるのと同様に、2 つの有理数間の距離は- 進距離、つまり差の - 進絶対値で測定できます。この距離の定義では、2 つの数は、その差が の大きなべき乗で割り切れるときに近い (距離が小さい) です。実数が有理数とその距離から形成できるのと同様に、追加の極限値を追加して完全な体を形成することで、 - 進距離を持つ有理数を別の完全な体である- 進数に拡張できます。^{[107] [108]}${\displaystyle p}$ ${\displaystyle \nu _{p}(n)}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle m/n}$${\displaystyle \nu _{p}(m)-\nu _{p}(n)}$${\displaystyle p}$${\displaystyle |q|_{p}}$${\displaystyle q}$${\displaystyle |q|_{p}=p^{-\nu _{p}(q)}}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

順序、絶対値、およびそれらから導かれる完備体のこの図は、代数体とその付値（体の乗法群から完全に順序付けられた加法群への特定の写像。順序とも呼ばれる）、絶対値（体から実数への特定の乗法写像。ノルムとも呼ばれる）^[107]、および場所（与えられた体が稠密な集合である完備体への拡張。完備体とも呼ばれる）^[109]に一般化できる。たとえば、有理数から実数への拡張は、数間の距離がそれらの差の通常の絶対値である場所です。対応する加法群への写像は絶対値の対数になりますが、これは付値のすべての要件を満たしていません。オストロフスキーの定理によれば、同値性の自然な概念を除き、実数と-進数、およびその順序と絶対値は、有理数上の唯一の付値、絶対値、場所です。^[107]局所-大域原理により、有理数に関する特定の問題は、それぞれの場所からの解をつなぎ合わせることで解決できるようになり、これもまた数論における素数の重要性を強調している。^[110]${\displaystyle p}$

可換環は、加算、減算、乗算が定義されている代数構造です。整数は環であり、整数の素数は、素元と既約元という2 つの異なる方法で環に一般化されています。環の元は、ゼロでなく、乗法逆元を持たず (つまり、単位ではない)、次の要件を満たす場合、素数と呼ばれます。が の 2 つの元の積を割り切るときはいつでも、またはの少なくとも 1 つも割り切ります。元が既約であるとは、単位でも他の 2 つの非単位元の積でもないことです。整数の環では、素元と既約元は同じ集合を形成します。 ${\displaystyle p}$${\displaystyle R}$${\displaystyle p}$${\displaystyle xy}$${\displaystyle R}$${\displaystyle x}$${\displaystyle y}$

${\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.}$

任意の環において、すべての素元は既約である。その逆は一般には成立しないが、一意の因数分解領域に対しては成立する。^[111]

算術の基本定理は、定義により、一意の因数分解領域でも成り立ちます。そのような領域の例としては、ガウス整数 があります。これは、という形式の複素数環で、 は虚数単位を表し、は任意の整数です。その素元はガウス素数として知られています。整数の中で素数であるすべての数がガウス整数でも素数であるわけではありません。たとえば、数 2 は、2 つのガウス素数と の積として表すことができます。3 mod 4 に一致する有理素数 (整数の素元) はガウス素数ですが、1 mod 4 に一致する有理素数はそうではありません。^{[112]これは、} 2 つの平方の和に関するフェルマーの定理の結果であり、奇数の素数は 2 つの平方の和 として表すことができ、したがって が1 mod 4 のときとして因数分解できると述べています^。[113]${\displaystyle \mathbb {Z} [i]}$${\displaystyle a+bi}$${\displaystyle i}$${\displaystyle a}$${\displaystyle b}$${\displaystyle 1+i}$${\displaystyle 1-i}$${\displaystyle p}$${\displaystyle p=x^{2}+y^{2}}$${\displaystyle p=(x+iy)(x-iy)}$${\displaystyle p}$

すべての環が一意の因数分解領域を持つわけではありません。たとえば、数環(整数と) では、数には2 つの因数分解 があり、4 つの因数はどちらもそれ以上簡約できないため、一意の因数分解はありません。一意の因数分解をより大規模な環のクラスに拡張するために、数の概念をイデアル の概念に置き換えることができます。イデアルとは、環の元のペアのすべての和と、環の元と元のすべての積を含む環の元の部分集合です。 素イデアルは、素元によって生成される主イデアルが素イデアルであるという意味で素元を一般化したものであって、可換代数、代数的数論、代数幾何学における重要なツールであり、研究対象です。整数環の素イデアルは、イデアル (0)、(2)、(3)、(5)、(7)、(11)、... である。算術の基本定理はラスカー・ノイマン定理に一般化され、ノイマン可換環のあらゆるイデアルを素数冪の適切な一般化である一次イデアルの交差として表現する。^[114]${\displaystyle a+b{\sqrt {-5}}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle 21}$${\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})}$

環のスペクトルは、点が環の素イデアルである幾何学的空間である。^[115] 数論幾何学もこの概念の恩恵を受けており、多くの概念が幾何学と数論の両方に存在する。たとえば、素イデアルを拡大体に持ち上げたときの因数分解や分岐は、代数的数論の基本問題であり、幾何学における分岐とある程度類似している。これらの概念は、整数のみに関係する数論的問題でも役立つことがある。たとえば、二次数体の整数環の素イデアルは、整数素数を法とする平方根の存在に関する命題である二次の相互性を証明するのに使用できる。 ^[116]フェルマーの最終定理を証明しようとする初期の試みは、クンマーによる正則素数の導入につながった。整数素数は、円分整数の一意な因数分解の失敗と関連している。^[117]代数体における複数の素イデアルの積に何個の整数素数が因数分解できるかという問題は、チェボタレフの密度定理によって解決される。この定理は、円分整数に適用すると、等差数列における素数に関するディリクレの定理を特別なケースとして持つ。^[118]

有限群の理論では、シローの定理は、素数のべき乗が群の位数を割り切る場合、群には位数の部分群があることを意味している。ラグランジュの定理によれば、素数位数の群は巡回群であり、バーンサイドの定理によれば、位数が2つの素数でのみ割り切れる群は解ける。^[119]${\displaystyle p^{n}}$${\displaystyle p^{n}}$

長い間、数論全般、特に素数の研究は純粋数学の典型的な例とみなされており、素数の歯車の歯を使って摩耗を均等に分散させる以外には数学以外への応用はなかった。^{[ b ] 特に、}イギリスの数学者GH ハーディなどの数論学者は、軍事的に全く意味のない研究を行っていることを誇りにしていた。^[121]

数論の純粋さというこの考えは、1970年代に素数が公開鍵暗号アルゴリズム作成の基礎として使用できることが公表されたときに打ち砕かれました。^[33] これらの応用により、素数を使った計算アルゴリズム、特に素数判定、つまり与えられた数が素数であるかどうかを判定する方法の重要な研究がなされるようになりました。最も基本的な素数判定ルーチンである試し割りは、大きな数には遅すぎるため役に立ちません。現代の素数判定の1つのグループは任意の数に適用できますが、より効率的な判定は特殊なタイプの数に対して使用できます。ほとんどの素数判定テストは、引数が素数かどうかのみを判定します。合成引数の素因数(またはそのすべての素因数)も提供するルーチンは因数分解アルゴリズムと呼ばれます。素数は、チェックサム、ハッシュテーブル、疑似乱数生成器の計算にも使用されます。

与えられた整数が素数であるかどうかをチェックする最も基本的な方法は、試し割りと呼ばれる。この方法は、2 からの平方根までの各整数で割り算する。 を均等に割り切れる整数は合成数として確立され、そうでない場合は素数である。 平方根よりも大きい整数は、 の場合、2 つの因数のうちの 1 つが の平方根以下であるため、チェックする必要は無い。別の最適化は、この範囲の因数として素数のみをチェックすることである。^[122]たとえば、37 が素数かどうかを確認するには、この方法では 2 から までの範囲の素数、つまり 2、3、5 で 37 を割ります。各割り算でゼロ以外の余りが生成されるため、37 は確かに素数である。${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n=a\cdot b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle n}$${\displaystyle {\sqrt {37}}}$

この方法は説明が簡単であるが、大きな整数の素数性をテストするには実用的ではない。なぜなら、実行するテストの数は、これらの整数の桁数の関数として指数関数的に増加するからである。 ^[123]しかし、このフィルターを通過する数に対してより複雑な方法を使用する前に、小さな因数を持つ合成数を素早く発見するために、除数のサイズの平方根よりも小さい制限で、試行除算が依然として使用されている。^[124]

コンピュータが登場する前は、与えられた限界までの素数や素因数分解をすべて列挙した数学表が一般的に印刷されていました。 ^[125]素数のリストを生成する最も古い既知の方法は、エラトステネスの篩と呼ばれています。^[126]アニメーションはこの方法の最適化された変種を示しています。^[127]同じ問題に対するもう1つの漸近的に効率的なふるい分け方法は、アトキンの篩です。^[128]高度な数学では、篩理論が同様の方法を他の問題に適用します。^[129]

任意の数が素数かどうかを判定する最新の最速のテストには、確率的（またはモンテカルロ ）アルゴリズムがあり、これは、誤った答えがランダムに生成される可能性がわずかにあることを意味します。^[130]たとえば、与えられた数に対するSolovay–Strassen 素数判定テストでは、から までの中からランダムに数を選択し、べき乗剰余を使用してが で割り切れるかどうかを確認します。^[c]割り切れる場合は「はい」と答え、そうでない場合は「いいえ」と答えます。 が本当に素数である場合は常に「はい」と答えますが、 が合成数である場合は、最大で 1/2 の確率で「はい」と答え、少なくとも 1/2 の確率で「いいえ」と答えます。^[131]このテストを同じ数で回繰り返すと、合成数が毎回テストに合格する確率は最大で です。これはテストの回数とともに指数的に減少するため、繰り返しテストに合格する数は素数であるという高い信頼性（確実性ではないが）が得られます。一方、テストに失敗した場合、その数は確かに合成数です。^[132] このようなテストに合格する合成数は擬素数と呼ばれる。^[131]${\displaystyle n}$${\displaystyle p}$${\displaystyle a}$${\displaystyle 2}$${\displaystyle p-2}$${\displaystyle a^{(p-1)/2}\pm 1}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle n}$${\displaystyle 1/2^{n}}$

対照的に、他のいくつかのアルゴリズムは、答えが常に正しいことを保証します。つまり、素数は常に素数であると判断され、合成数は常に合成数であると判断されます。たとえば、これは試し割りに当てはまります。正しい出力が保証されたアルゴリズムには、AKS素数判定テストなどの決定論的（非ランダム）アルゴリズムと、楕円曲線素数証明のいくつかのバリエーションなどのアルゴリズムによるランダム選択が最終的な答えに影響を与えないランダム化 ラスベガスアルゴリズムの両方が含まれます。^[130]楕円 曲線法は、数値が素数であると結論付けると、すぐに検証できる素数証明書を提供します。 ^[134]楕円曲線素数判定テストは、正確さが保証された素数判定テストの中で実際には最も高速ですが、その実行時分析は厳密な証明ではなくヒューリスティックな議論 に基づいています。AKS素数判定は数学的に証明された時間計算量を持っていますが、実際には楕円曲線素数証明よりも遅くなります。^[135]これらの方法は、乱数を生成してテストし、素数が見つかるまでランダムに大きい素数を生成するために使用できます。これを行うと、より高速な確率テストにより、ほとんどの合成数をすばやく排除してから、正しいことが保証されたアルゴリズムを使用して残りの数が素数であるかどうかを検証できます。^[d]

次の表は、これらのテストのいくつかを示しています。テストの実行時間は、テストされる数、および確率的アルゴリズムの場合は実行されるテストの数で表されます。さらに、は任意の小さな正の数であり、log は指定されていない底に対する対数です。大きな O 表記は、各時間境界に定数係数を掛けて、無次元単位から時間単位に変換する必要があることを意味します。この係数は、アルゴリズムを実行するために使用されるコンピュータの種類などの実装の詳細に依存しますが、入力パラメータやには依存しません。 ${\displaystyle n}$${\displaystyle k}$${\displaystyle \varepsilon }$${\displaystyle n}$${\displaystyle k}$

前述のあらゆる自然数に適用されるテストに加えて、特別な形式の数については素数かどうかをより迅速にテストすることができます。たとえば、ルーカス・レーマー素数テストでは、ミラー・ラビンテストを1回繰り返すのと同じ時間で、メルセンヌ数（ 2の累乗より1小さい数）が素数かどう^{かを決定論的に判定できます。 [140]}これが、1992年以降（2018年12月現在^[update]）最大の素数は常にメルセンヌ素数であった理由です。^[141]メルセンヌ素数は無限にあると推測されています。^[142]

次の表は、様々な種類の既知の最大の素数を示しています。これらの素数の一部は、分散コンピューティングを使用して発見されています。2009年、Great Internet Mersenne Prime Searchプロジェクトは、1000万桁以上の素数を初めて発見した人に10万ドルの賞金を授与しました。^[143]電子フロンティア財団も、1億桁以上と10億桁以上の素数に対してそれぞれ15万ドルと25万ドルの賞金を提供しています。^[144]

合成整数 が与えられたとき、1つ（またはすべて）の素因数を与える作業を の因数分解といいます。これは素数判定よりもはるかに難しく、^[151]多くの因数分解アルゴリズムが知られていますが、最も高速な素数判定法よりも時間がかかります。の非常に小さな因数を見つけるには、試し割りやポラードのローアルゴリズムを使用できます。 ^[124]また、楕円曲線因数分解は、が中程度の大きさの因数を持つ場合に効果的です。 ^[152]因数の大きさに依存しない任意の大きな数に適した方法には、二次ふるいや一般数体ふるいなどがあります。素数判定と同様に、特殊な数体ふるいなど、入力が特殊な形式であることを要求する因数分解アルゴリズムもあります。^[153] 2019年12月現在、汎用アルゴリズムによって因数分解されたことが知られている最大の数はRSA -240であり、これは240桁の10進数（795ビット）を持ち、2つの大きな素数の積である。^[154]${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$^[update]

ショアのアルゴリズムは量子コンピュータ上で多項式数のステップで任意の整数を因数分解できる。^[155]しかし、現在の技術ではこのアルゴリズムを非常に小さな数にしか実行できない。2012年10月現在^[update]、ショアのアルゴリズムを実行する量子コンピュータによって因数分解された最大の数は21である。^[156]

RSAやディフィー・ヘルマン鍵交換などの公開鍵暗号アルゴリズムは、大きな素数（2048ビットの素数が一般的）に基づいています。^[157] RSAは、積だけがわかっている場合、2つの（大きな）数とを掛け算する方が、とを計算する（互いに素であると仮定）よりもはるかに簡単（つまり効率的）であるという仮定に依存しています。^{[33]ディフィー・ヘルマン鍵交換は、}モジュラー指数演算（ の計算）には効率的なアルゴリズムがある一方で、逆演算（離散対数）は難しい問題であると考えられているという事実に依存しています。^[158]${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle xy}$${\displaystyle a^{b}{\bmod {c}}}$

素数はハッシュテーブルによく使われる。例えば、カーターとウェグマンによるユニバーサルハッシュの元々の方法は、大きな素数を法としてランダムな線形関数を選択してハッシュ関数を計算するというものだった。カーターとウェグマンはこの方法を、やはり大きな素数を法として高次多項式を使うことで-独立ハッシュに一般化した。 ^[159]ハッシュ関数と同様に、2次プロービングベースのハッシュテーブルでは、プローブシーケンスがテーブル全体をカバーできるようにするために、ハッシュテーブルのサイズに素数が使われる。^[160]${\displaystyle k}$

いくつかのチェックサム方式は素数の数学に基づいています。たとえば、国際標準図書番号で使用されるチェックサムは、残りの数を素数である 11 で割った値として定義されます。11 は素数であるため、この方式では 1 桁のエラーと隣接する桁の転置の両方を検出できます。^[161]別のチェックサム方式であるAdler-32では、 未満の最大の素数である 65521 を法とする算術演算を使用します。^{[162]素数は}、線形合同法^[163]やメルセンヌツイスター^[164]などの疑似乱数生成器でも使用されます。${\displaystyle 2^{16}}$

素数は数論において中心的な重要性を持つが、抽象代数や初等幾何学など数学の他の分野にも多くの応用がある。例えば、2次元グリッドに素数の点を配置​​して、3つが一直線にならないようにしたり、3つの点によって形成される三角形の面積が大きくなるようにしたりすることができる。^[165]別の例としては、アイゼンシュタインの基準がある。これは、多項式の係数が素数とその平方で割り切れるかどうかに基づいて、多項式が既約かどうかを判定するものである。^[166]

素数の概念は非常に重要であるため、数学のさまざまな分野でさまざまな方法で一般化されています。一般に、「素数」は適切な意味で最小性または分解不可能性を示します。たとえば、特定の体の素体とは、0 と 1 の両方を含む最小の部分体です。これは有理数の体、または素数の要素を持つ有限体のいずれかであり、そこから名前が付けられています。^[167]多くの場合、素数という単語を使用することで、2 つ目の追加の意味が意図されています。つまり、任意のオブジェクトは、本質的に一意に、その素数のコンポーネントに分解できます。たとえば、結び目理論では、素数結び目は、2 つの非自明な結び目の接続された和として記述できないという意味で分解不可能な結び目です。任意の結び目は、素数結び目の接続された和として一意に表現できます。^[168] 3 次元多様体の素数分解は、このタイプの別の例です。^[169]

数学やコンピューティングを超えて、素数は量子力学との潜在的なつながりがあり、芸術や文学では比喩的に使用されてきました。また、進化生物学ではセミのライフサイクルを説明するためにも使用されてきました。

フェルマー素数とは、

${\displaystyle F_{k}=2^{2^{k}}+1,}$

は非負の整数で表されます。^{[170]これらは、そのような数はすべて素数であると予想した}ピエール・ド・フェルマーにちなんで名付けられました。これらの数の最初の 5 つ、つまり 3、5、17、257、および 65,537 は素数ですが、 ^{[171] は}合成数であり、2017 年の時点で検証されている他のすべてのフェルマー数も合成数です。^[172]正多角形は、定規とコンパスを使用して構成できますが、 の奇数の素因数(存在する場合) が異なるフェルマー素数である場合に限ります。 ^[171]同様に、正多角形は、定規、コンパス、および角の三等分線を使用して構成できますが、 の素因数が2 または 3 の任意の数のコピーと、(空の可能性がある) 異なるピアポント素数の集合 (形式 の素数) である場合に限ります。^[173]${\displaystyle k}$${\displaystyle F_{5}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2^{a}3^{b}+1}$

が素数 のべき乗であるとき、任意の凸多角形を面積と周長が等しい小さな凸多角形に分割することは可能ですが、 が他の値であるときはこのことは知られていません。^[174]${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

1970年代のヒュー・モンゴメリーとフリーマン・ダイソンの研究に始まり、数学者と物理学者はリーマンゼータ関数の零点が量子系のエネルギー準位と関係していると推測してきた。^{[175] [176]}素数は、相互に偏りのない基数や対称で情報的に完全な正の作用素値測度などの数学的構造のおかげで、量子情報科学でも重要である。^{[177] [178]}

マジカダ属のセミが採用する進化戦略は素数を利用するものである。^[179]これらの昆虫は、その一生のほとんどを地中で幼虫として過ごす。蛹化して巣穴から出てくるのは7年、13年、または17年後で、その後は飛び回って繁殖し、数週間後には死んでしまう。生物学者は、これらの素数の繁殖周期の長さは、捕食者がこれらの周期と同期するのを防ぐために進化したと理論づけている。^{[180] [181]対照的に、}竹の開花期の間隔は数年ごとに区切られており、因数分解すると小さな素数しか含まれない滑らかな数であると仮定されている。^[182]

素数は多くの芸術家や作家に影響を与えてきた。フランスの作曲家 オリヴィエ・メシアンは素数を使って「自然現象」を通して非韻律的な音楽を作った。『貴族の生誕』（1935年）や『四つのリズムの練習曲』（1949年 - 1950年）などの作品では、異なる素数によって長さが決まるモチーフを同時に使い、予測不可能なリズムを作った。素数41、43、47、53は第3の練習曲『リズムの音』に登場する。メシアンによれば、この作曲法は「自然の動き、自由で不均等な持続時間の動きに触発された」という。^[183]

科学者カール・セーガンは、 SF小説『コンタクト』の中で、素因数分解は宇宙人との交信において2次元画像平面を確立する手段として使用できると示唆した。このアイデアは、 1975年にアメリカの天文学者フランク・ドレイクと非公式に初めて発展させたものだった。 ^[184]マーク・ハッドンの小説『夜中に犬に起こった奇妙な事件』では、語り手が物語の各部分を連続する素数で並べることで、数学の才能に恵まれたアスペルガー症候群の10代の主人公の精神状態を伝えている。^[185]パオロ・ジョルダーノの小説『素数の孤独』では、素数は孤独と孤立の比喩として使われており、整数の中の「部外者」として描かれている。^[186]

• 「素数」。数学百科事典。EMS Press。2001 [1994]。
• Caldwell、Chris、primes.utm.edu の The Prime Pages。
• BBCのIn Our Timeでの素数。
• Plus 教師および生徒パッケージ: ケンブリッジ大学のミレニアム数学プロジェクトが制作した無料のオンライン数学雑誌 Plus からの素数。

• 素因数計算機は、最大 20 桁までの任意の正の整数を因数分解できます。
• 因数分解による高速オンライン素数判定では、楕円曲線法 (最大 1000 桁の数値、Java が必要) を使用します。
• 素数の巨大なデータベース。
• 1兆までの素数。2021年2月27日にWayback Machineにアーカイブされました。