素数

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

1 を素数とみなすと、素数に関する多くの記述を不自然に書き換える必要が生じる。例えば、算術の基本定理は、1 より大きい素数への因数分解という観点から言い換える必要がある。なぜなら、すべての数は、任意の数の 1のコピーを含む複数の因数分解を持つことになるからである。 ^{[ 40 ] [ 44 ]}同様に、エラトステネスの篩は、1 を素数として扱うと正しく機能しない。なぜなら、1 の倍数 (つまり、他のすべての数) をすべて排除し、単一の数 1だけを出力するからである。 ^{[ 43 ]}素数のその他のより技術的な性質も、数 1 には当てはまらない。例えば、オイラーのトーシェント関数や約数の和関数 の公式は、素数と1では異なる。^{[ 45 ]}

数を素数の積として表すことを、その数の素因数分解という。 ^{[ 46 ]}例えば：

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

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

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

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

素数は無限に存在します。別の言い方をすれば、数列は無限に存在します。

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

素数の無限性は無限である。この主張は、この主張の最初の証明が古代ギリシャの数学者ユークリッドに帰せられていることから、ユークリッドの定理と呼ばれている。素数の無限性に関する証明は他にも多数知られており、オイラーによる解析的証明、フェルマー数に基づくゴールドバッハの証明^{[ 52 ]}、一般位相を用いたフュルステンベルクの証明^{[ 53 ]}、クンマーの背理法による証明^{[ 54 ] [ 55 ]}などがある。

ユークリッドの証明は、有限個の素数のリストはすべて不完全であることを示している。^{[ 56 ]}重要なアイデアは、任意のリスト内の素数を掛け合わせて、${\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つ以上の素因数を持つ。${\displaystyle N}$はこれらの因数のそれぞれで割り切れるが、${\displaystyle N}$は、与えられたリストにある素数のいずれかで割ったときの余りが 1 なので、 の素因数はどれも 1 ではありません。${\displaystyle N}$与えられたリストには含まれている可能性があります。すべての素数を有限のリストにまとめることはできないため、素数は無限に存在するはずです。

最小の素数の積に 1 を加えることによって形成される数は、ユークリッド数と呼ばれます。^{[ 57 ]}最初の 5 個は素数ですが、6 個目は、

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

は合成数です。

素数を求める効率的な公式は知られていません。例えば、複数の変数を含む非定数多項式であっても、素数のみを取るものはありません。^{[ 58 ]}しかし、すべての素数、または素数のみを符号化する式は多数存在します。考えられる公式の1つはウィルソンの定理に基づいており、2を何度も生成し、他のすべての素数をちょうど1回生成します。^{[ 59 ]}また、9つの変数と1つのパラメータを持つディオファントス方程式のセットがあり、次の性質を持ちます。パラメータが素数であるのは、結果として得られる方程式系が自然数上で解を持つ場合のみです。これを利用して、すべての正の値が素数であるという性質を持つ単一の公式を得ることができます。^{[ 58 ]}

素数生成式の他の例は、ミルズの定理とライトの定理から得られます。これらは、実定数が存在すると主張しています。${\displaystyle A>1}$そして${\displaystyle \mu }$そのため

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

任意の自然数に対して素数である${\displaystyle n}$最初の式では、そして2番目の式では任意の数の指数が用いられます。 [ ^{60 ]ここ}で${\displaystyle \lfloor {}\cdot {}\rfloor }$は床関数を表し、対象となる数以下の最大の整数です。ただし、これらは素数を生成するのには役立ちません。 の値を計算するには、まず素数を生成する必要があるからです。${\displaystyle A}$または​${\displaystyle \mu .}$^{[ 58 ]}

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

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

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

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

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

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

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

${\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 ,}$

は有限である。ブルンの定理により、無限に多くの双子素数が存在するという双子素数予想を解決するためにオイラーの方法を使用することは不可能である。 ^{[ 79 ]}

素数計数関数${\displaystyle \pi (n)}$は、以下である素数の数として定義される。${\displaystyle n}$⁠ . ^{[ 80 ]}例えば、 ⁠${\displaystyle \pi (11)=5}$11以下の素数は5つあるため、 Meissel–Lehmerアルゴリズム などの方法で正確な値を計算できます。${\displaystyle \pi (n)}$素数を列挙するよりも速く${\displaystyle n}$⁠ . ^{[ 81 ]}素数定理は次のように述べている。${\displaystyle \pi (n)}$は漸近的に に近づく${\displaystyle n/\log n}$⁠、これは次のように表されます。

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

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

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

等差数列とは、連続する数がすべて同じ差を持つ有限または無限の数列のことです。^{[ 85 ]}この差は数列の絶対値と呼ばれます。 ^{[ 86 ]}例えば、

${\displaystyle 3,12,21,30,39,...,}$

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

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

複数の素数を持つことができるのは、その余りが${\displaystyle a}$⁠そしてモジュラス⁠${\displaystyle q}$は互いに素である。互いに素であれば、等差数列に関するディリクレの定理によれば、数列には無限個の素数が含まれる。 ^{[ 87 ]}

9 を法とする等差数列における素数。細い水平帯の各行は、9 を法とする 9 つの数列のうちの 1 つを示しており、素数は赤色でマークされています。0、3、または 6 を法とする数列には、最大で 1 つの素数 (3) が含まれます。残りの 1、2、4、5、7、および 8 を法とする数列には、無限に多くの素数が含まれており、各数列に含まれる素数の数はほぼ同じです。

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

オイラーは関数が

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

素数を生成する${\displaystyle 1\leq n\leq 40}$ただし、合成数はその後の値の中に現れます。 ^{[ 89 ] [ 90 ]}この現象の説明を探求した結果、ヘーグナー数の深い代数的数論とクラス数問題が生まれました。 ^{[ 91 ]}ハーディ・リトルウッド予想Fは、整数係数の二次多項式の値の中に素数がどれだけ存在するか対数積分と多項式係数で予測します。無限に多くの素数値をとる二次多項式は証明されていません。 ^{[ 92 ]}

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

ロシアの数学者ヴィクトル・ブニャコフスキーは1857年に、任意の1変数多項式が${\displaystyle f(x)}$整数係数を用いると、数列に無限個の素数が生じる。${\displaystyle f(1),f(2),f(3),\dots }$多項式は、その最高次係数が正であり、有理数体上で既約であり、そのような数列の値が 1 より大きい共通因数を持たないという条件を満たさなければならない。この予想は、ポーランドの数学者Andrzej Schinzelの仮説 Hによって一般化され、後にDickson の予想、そしてBateman–Horn の予想において多変数多項式に拡張された。^{[ 94 ]}

数学における最も有名な未解決問題の一つで、1859年に提起され、ミレニアム懸賞問題の一つでもあるのが、リーマン予想である。これは、リーマンゼータ関数の零点がどこにあるのかを問うものである。${\displaystyle \zeta (s)}$位置が特定されています。この関数は複素数上の解析関数です。^{[ 95 ]}複素数の場合⁠${\displaystyle s}$実部が 1 より大きい場合、それはすべての整数に関する無限和と素数に関する 無限積の両方に等しくなります。$${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.}$$ オイラーによって発見されたこの和と積の等式は、オイラー積と呼ばれます。^{[ 96 ]}オイラー積は算術の基本定理から導き出すことができ、ゼータ関数と素数の密接な関係を示しています。^{[ 97 ]} これは、素数が無限に存在するという別の証明につながります。もし素数が有限個しか存在しないとしたら、和と積の等式は ⁠でも成り立つはずです。${\displaystyle s=1}$しかし、和は発散する（これは調和級数である）${\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots }$⁠ ) 積は有限になるので矛盾が生じる。 ^{[ 98 ]}

リーマン予想は、ゼータ関数の零点はすべて負の偶数か、実部が1/2 に等しい複素数であると述べている。 ^{[ 99 ]}素数定理の元の証明は、実部が 1 に等しい零点が存在しないというこの予想の弱い形式に基づいていたが、^{[ 100 ] [ 101 ]}他のより初歩的な証明も見つかっている。^{[ 102 ]}素数計数関数は、各項がゼータ関数の零点のいずれかから来る和として、リーマンの明示的な公式で表すことができる。この和の主項は対数積分であり、残りの項によって和は主項の上と下で変動する。^{[ 103 ]}この意味で、零点は素数の分布の規則性を制御する。リーマン予想が正しい場合、これらの変動は小さくなり、 素数定理によって与えられる素数の漸近分布は、より短い区間（長さが約 の平方根）でも成り立つ。${\displaystyle x}$数値付近の区間について${\displaystyle x}$⁠ ). ^{[ 101 ]}

モジュラー算術は、数値のみを使用して通常の算術を変更します。${\displaystyle \{0,1,2,\dots ,n-1\}}$自然数の場合${\displaystyle n}$を法と呼びます。他の自然数は、で割った余りで置き換えることで、このシステムに対応付けることができます。${\displaystyle n}$[ 104 ^{]モジュラー和、差、積は、通常の}整数の和、差、積の結果に同じ剰余による置換を行うことによって計算されます。 ^{[ 105 ]}整数の等号は、モジュラー算術における合同に対応します。${\displaystyle x}$そして​​${\displaystyle y}$⁠は合同である（表記）${\displaystyle x\equiv y}$モッド​${\displaystyle n}$⁠ ) で割った後の余りが同じ場合⁠${\displaystyle n}$[ 106 ^]この数体系では、^{法が素数である場合に限り、}すべての非ゼロ数による除算が可能です。例えば、素数7を法とした場合、3による除算が可能^です。${\displaystyle 2/3\equiv 3{\bmod {7}}}$なぜなら、両辺に3を掛けて分母を消去すると、有効な式が得られるからである。${\displaystyle 2\equiv 9{\bmod {7}}}$しかし、合成法の法則が6の場合、3で割ることは不可能です。有効な解はありません。${\displaystyle 2/3\equiv x{\bmod {6}}}$分母を消去するために 3 を掛けると、左辺は 2 になり、右辺は 0 または 3 になります。抽象代数の用語では、除算を実行できるということは、素数を法とするモジュラー演算が体、より具体的には有限体を形成することを意味し、他の法は環のみを与え、体は与えません。^{[ 107 ]}

素数に関するいくつかの定理は、モジュラー算術を用いて定式化できる。例えば、フェルマーの小定理は、もし${\displaystyle a\not \equiv 0}$(mod ⁠${\displaystyle p}$⁠）、それから${\displaystyle a^{p-1}\equiv 1}$(mod ⁠${\displaystyle p}$⁠ ) ^{[ 108 ]}すべての選択肢についてこれを合計すると⁠${\displaystyle a}$⁠は方程式を与える

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

いつでも有効${\displaystyle p}$は素数である。 ジューガ予想によれば、この方程式は の十分条件でもある。${\displaystyle p}$素数であること。 ^{[ 109 ]}ウィルソンの定理によれば、整数は${\displaystyle p>1}$素数であるのは、階乗が${\displaystyle (p-1)!}$は${\displaystyle -1}$モッド​${\displaystyle p}$合成数の場合 ${\displaystyle n=r\cdot s}$これは成り立たない。なぜなら、その因数の1つがnとを割り切るからである。${\displaystyle (n-1)!}$⁠、そして${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$不可能である。^{[ 110 ]}

その​${\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 \vert q\vert _{p}=p^{-\nu _{p}(q)}}$整数にその整数を掛ける${\displaystyle p}$⁠ -進絶対値は の因数を打ち消します⁠${\displaystyle p}$⁠因数分解では、他の素数だけが残ります。2 つの実数間の距離がそれらの差の絶対値で測定できるのと同様に、2 つの有理数間の距離はそれらの⁠ で測定できます。${\displaystyle p}$⁠ -進距離、${\displaystyle p}$それらの差の絶対値の⁠進数。この距離の定義では、2 つの数の差が⁠の高次のべき乗で割り切れる場合、2 つの数は近い (距離が小さい) と言えます。${\displaystyle p}$実数が有理数とその距離から、追加の極限値を加えて完全体を形成するのと同様に、有理数も⁠${\displaystyle p}$⁠ -進距離は別の完全体、つまり に拡張できます。${\displaystyle p}$-進数。 ^{[ 111 ] [ 112 ]}

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

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

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

任意の環において、すべての素元は既約である。一般にはその逆は成り立たないが、一意分解領域については成り立つ。^{[ 115 ]}

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

すべての環が一意分解領域であるとは限りません。たとえば、数の環では${\displaystyle a+b{\sqrt {-5}}}$（整数の場合）${\displaystyle a}$そして​​${\displaystyle b}$⁠ ) 番号${\displaystyle 21}$2つの因数分解を持つ${\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})}$⁠、4 つの因数のいずれもこれ以上簡約できないため、一意の因数分解を持ちません。一意の因数分解をより大きなクラスの環に拡張するために、数の概念をイデアルの概念に置き換えることができます。イデアルとは、環の要素のサブセットであり、その要素のペアのすべての和と、その要素と環の要素のすべての積を含みます。 素イデアルは、素要素によって生成される主イデアルが素イデアルであるという意味で素要素を一般化したものであり、可換代数、代数的整数論、代数幾何学において重要なツールであり研究対象です。整数環の素イデアルは、イデアル⁠です。${\displaystyle (0)}$⁠、 ⁠${\displaystyle (2)}$⁠、 ⁠${\displaystyle (3)}$⁠、 ⁠${\displaystyle (5)}$⁠、 ⁠${\displaystyle (7)}$⁠、 ⁠${\displaystyle (11)}$⁠、...算術の基本定理はラスカー・ネーターの定理に一般化され、ネーター可換環のすべてのイデアルは素数のべき乗の適切な一般化である基本イデアルの交差として。 ^{[ 118 ]}

環のスペクトルは、その環の素イデアルを点とする幾何学的空間である。^{[ 119 ]}算術幾何学もこの概念の恩恵を受けており、多くの概念が幾何学と数論の両方に存在する。例えば、代数的数論の基本的な問題である、拡大体への素イデアルの因数分解または分岐は、幾何学の分岐といくらか似ている。これらの概念は、整数のみに関係する数論の問題にも役立つことがある。例えば、二次数体の整数環の素イデアルは、整数素数を法とする平方根の存在に関する命題である二次相互性の証明に使用できる。 ^{[ 120 ]}フェルマーの最終定理を証明しようとする初期の試みは、クンマーによる正則素数の導入につながった。正則素数は、円分整数の一意因数分解の失敗に関連する整数素数である。^{[ 121 ]}代数体における多重素イデアルの積に因数分解できる整数素数がいくつあるかという問題は、チェボタレフの稠密定理によって解決され、この定理は（円分整数に適用した場合）等差数列の素数に関するディリクレの定理を特殊な場合として含んでいる。^{[ 122 ]}

有限群の理論では、シローの定理は、素数のべき乗が${\displaystyle p^{n}}$群の位数を分割すると、その群は位数 の部分群を持つ。${\displaystyle p^{n}}$ラグランジュの定理によれば、素数の位数の任意の群は巡回群であり、バーンサイドの定理によれば^、位数が2つの素数で割り切れる任意の群は可解群である。 ^[ 123 ^]

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

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

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

任意の与えられた数値が${\displaystyle n}$素数判定は確率的（またはモンテカルロ）アルゴリズムであり、誤った答えを出す可能性がわずかながらランダムに存在することを意味します。 ^{[ 134 ]}例えば、与えられた数に対するソロベイ・ストラッセンの素数判定は、${\displaystyle p}$数字を選択する${\displaystyle a}$2からランダムに${\displaystyle p-2}$そしてモジュラーべき乗を使用してチェックします${\displaystyle a^{(p-1)/2}\pm 1}$はで割り切れる${\displaystyle p}$⁠ . ^{[ d ]}そうであれば「はい」と答え、そうでなければ「いいえ」と答えます。もし⁠${\displaystyle p}$本当に素数であれば、常に「はい」と答えますが、もし${\displaystyle p}$⁠が複合である場合、確率が最大で 1/2 で「はい」、確率が少なくとも 1/2 で「いいえ」と答えます。 ^{[ 135 ]}このテストを繰り返すと、${\displaystyle n}$同じ数字に対して⁠回テストを行った場合、合成数が毎回テストに合格する確率は最大で⁠${\displaystyle 1/2^{n}}$⁠。これはテストの回数とともに指数関数的に減少するため、繰り返しテストに合格した数が素数であるという確信度は高い（ただし確実ではない）が与えられます。一方、テストが一度でも失敗した場合は、その数は確実に合成数です。 ^{[ 136 ]} このようなテストに合格した合成数は擬似素数と呼ばれます。 ^{[ 135 ]}

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

以下の表は、これらのテストの一部を示しています。実行時間は⁠の単位で示されています。${\displaystyle n}$⁠、テストする数、そして確率的アルゴリズムの場合は、数⁠${\displaystyle k}$実施されたテストの数。さらに、${\displaystyle \varepsilon }$は任意の小さな正の数であり、log は底が指定されていない対数です。ビッグオー記法は、各時間境界を無次元単位から時間単位に変換するために定数倍する必要があることを意味します。この定数倍は、アルゴリズムを実行するために使用されるコンピュータの種類などの実装の詳細に依存しますが、入力パラメータには依存しません。${\displaystyle n}$そして​​${\displaystyle k}$⁠ .

前述の自然数に適用できるテストに加えて、特殊な形式の数については素数判定をより迅速に行うことができます。例えば、ルーカス・レーマー素数判定法は、メルセンヌ数（ 2のべき乗より1小さい数）が素数であるかどうかを、ミラー・ラビン判定法の1回の反復と同じ時間で決定的に判定できます。^{[ 144 ]}このため、1992年以来（2024年10月現在） 、 既知の最大の素数は常にメルセンヌ素数であった。^{[ 145 ]}メルセンヌ素数は無限に存在すると推測されている。^{[ 146 ]}

次の表は、さまざまなタイプの既知の最大の素数を示しています。これらの素数のいくつかは、分散コンピューティングを使用して発見されました。2009年、グレートインターネットメルセンヌ素数探索プロジェクトは、少なくとも1000万桁の素数を最初に発見したとして、10万米ドルの賞金を授与されました。^{[ 147 ]}電子フロンティア財団はまた、少なくとも1億桁と10億桁の素数に対して、それぞれ15万ドルと25万ドルを提供しています。^{[ 148 ]}

合成整数が与えられた場合${\displaystyle n}$⁠、1つ（またはすべて）の素因数を求めるタスクは、の因数分解と呼ばれます。${\displaystyle n}$⁠。素数判定よりもかなり難しく、 ^{[ 156 ]}多くの因数分解アルゴリズムが知られていますが、それらは最速の素数判定法よりも遅いです。試行除法とポラードのρアルゴリズムを使用して、 の非常に小さな因数を求めることができます。${\displaystyle n}$⁠ , ^{[ 128 ]}楕円曲線分解は、次の場合に効果的です。${\displaystyle n}$は中程度の大きさの因数を持つ。 ^{[ 157 ]}因数の大きさに依存しない任意の大きな数に適した方法としては、二次篩法や一般数体篩法などがある。素数判定と同様に、入力が特別な形式であることを必要とする因数分解アルゴリズムもあり、特殊数体篩法などがある。 ^{[ 158 ]} 2019年12月現在 汎用アルゴリズムによって因数分解されたことが知られている最大の数はRSA -240であり、これは240桁の10進数（795ビット）を持ち、2つの大きな素数の積である。^{[ 159 ]}

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

RSAやDiffie-Hellman鍵交換などのいくつかの公開鍵暗号アルゴリズムは、大きな素数（2048ビット素数が一般的）に基づいています。^{[ 162 ]} RSAは、2つの（大きな）数の乗算を実行する方がはるかに簡単（つまり、効率的）であるという仮定に基づいています。${\displaystyle x}$そして​​${\displaystyle y}$計算するよりも${\displaystyle x}$そして​​${\displaystyle y}$（互いに素であると仮定）積のみ${\displaystyle xy}$は既知である。^{[ 31 ]} Diffie–Hellman鍵交換は、モジュラべき乗（計算）のための効率的なアルゴリズムが存在するという事実に基づいている。${\displaystyle a^{b}{\bmod {c}}}$⁠ )、一方、逆演算（離散対数）は難しい問題と考えられている。 ^{[ 163 ]}

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

チェックサム方式の中には、素数の数学に基づいているものがあります。例えば、国際標準図書番号（ISBN）で使用されるチェックサムは、素数である11を法として数値の余りを取ることで定義されます。11は素数であるため、この方式では1桁の誤りと隣接する桁の転置の両方を検出できます。^{[ 166 ]}別のチェックサム方式であるAdler-32は、65521を法とする演算を使用します。65521は、11未満の最大の素数です。${\displaystyle 2^{16}}$⁠ . ^{[ 167 ]}素数は、線形合同法乱数発生器^{[ 168 ]}やメルセンヌツイスター^{[ 169 ]}などの擬似乱数発生器にも使用されます。

フェルマー素数は次の形式の素数である。

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

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

任意の凸多角形を に分割することは可能である。${\displaystyle n}$面積と周囲長が等しいより小さな凸多角形の場合、${\displaystyle n}$は素数のべき乗ですが、他の値についてはこのことはわかっていません。${\displaystyle n}$⁠ . ^{[ 179 ]}

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

Magicicada属のセミが用いる進化戦略は素数を利用している。^{[ 184 ]}これらの昆虫は一生のほとんどを地下の幼虫として過ごす。7年、13年、または17年後に蛹になり、巣穴から出てくると、飛び回り、繁殖し、そしてせいぜい数週間後に死ぬ。生物学者は、これらの素数で表される繁殖周期の長さは、捕食者がこれらの周期に同調するのを防ぐために進化してきたと理論づけている。^{[ 185 ] [ 186 ]}対照的に、竹の開花の間隔が数年に及ぶことは、素因数分解に小さな素数しか含まない滑らかな数であると仮説が立てられている。^{[ 187 ]}

素数は多くの芸術家や作家に影響を与えてきました。フランスの作曲家オリヴィエ・メシアンは、「自然現象」を通して無拍子音楽を創造するために素数を用いました。 『主の降誕』 （1935年）や『4つのリズム練習曲』 （1949～1950年）などの作品では、異なる素数で与えられる長さのモチーフを同時に用いて予測不可能なリズムを作り出しています。素数41、43、47、53は、3番目の練習曲「リズミックなネウマ」に登場します。メシアンによれば、この作曲方法は「自然の動き、自由で不均等な長さの動きに触発されたもの」です。^{[ 188 ]}

科学者カール・セーガンは、 SF小説『コンタクト』の中で、素因数分解をエイリアンとの通信で2次元の画像平面を確立する手段として使用できると示唆した。このアイデアは、1975年にアメリカの天文学者フランク・ドレイクと非公式に初めて展開されたものである。 ^{[ 189 ]}マーク・ハッドンの小説『夜中に犬が吠えた奇妙な事件』では、語り手が物語の各セクションを連続する素数で並べることで、アスペルガー症候群の数学の才能を持つ10代の主人公の精神状態を伝えている。^{[ 190 ]}パオロ・ジョルダーノの小説『素数の孤独』では、素数は孤独と孤立のメタファーとして使用され、整数の中で「部外者」として描かれている。^{[ 191 ]} 1992年の強盗映画『スニーカーズ』では、大きな数を素早く素数に因数分解してコンピュータの暗号化システムを破る架空の方法が登場する。^{[ 192 ] [ 193 ] [ 194 ]}