素数

${\displaystyle \mathbb{N}\subseteq <!--\; \subseteq \; -->\mathbb{Z}\subseteq <!--\; \subseteq \; -->\mathbb{Q}\subseteq <!--\; \subseteq \; -->\mathbb{R}\subseteq <!--\; \subseteq \; -->\mathbb{C}}$进数
数学常数

圆周率 ${\displaystyle \mathrm{\pi <!--\; \pi \; -->}=3.141592653\dots <!--\; \dots \; -->}$)。

除了前述可应用于任何自然数n之上的测试外，一些更有效率的素性测试适用于特定数字之上。例如，卢卡斯素性测试需要知道 − 1的素因数，而卢卡斯-莱默素性测试则需要以 + 1的素因数作为输入。例如，这些测试可应用在检查

是否为一素数。此类形式的素数称之为阶乘素数。其他具p+1或p-1之类形式的素数还包括索菲·热尔曼素数（具2p+1形式的素数，其中p为素数）、素数阶乘素数、费马素数与梅森素数（具2 − 1形式的素数，其中p为素数）。卢卡斯-雷默素性测试对这类形式的数特别地快。这也是为何自电脑出现以来，最大已知素数总会是梅森素数的原因。

费马素数具下列形式

其中，k为任意自然数。费马素数以皮埃尔·德·费马为名，他猜想此类数字均为素数。费马认为均为素数的理由为此串列的前5个数字（3、5、17、257及65537）为素数。不过，₅却为合数，且直至2015年发现的其他费马数字也全都是合数。一个正n边形可用尺规作图，当且仅当

其中，m为任意个不同费马素数之乘积，及i为任一自然数，包括0。

下列表格给出各种形式的最大已知素数。有些素数使用分散式计算找到。2009年，互联网梅森素数大搜索因为第一个发现具至少1,000万个数位的素数，而获得10万美元的奖金。电子前哨基金会亦为具至少1亿个数位及10亿个数位的素数分别提供15万美元及25万美元的奖金。

给定一合数n，给出一个（或全部）素因数的工作称之为n的约数分解。椭圆曲线分解是一个依靠椭圆曲线上的运算来分解素因数的算法。

1975年，数论学家唐·察吉尔评论素数 {displaystyle n}  <  < 2 − 2，其中n为大于3的任一自然数。第一个公式可由威尔逊定理导出，每个不同的n会对应到不同的素数，除了数字2会有多个n对应到外。不过，这两个公式都需要先计算出A或μ的值来。

不存在一个只会产生素数值的非常数多项式，即使该多项式有许多个变量。不过，存在具9个变量的丢番图方程，其参数具备以下性质：该参数为素数，当且仅当其方程组有自然数解。这可被用来获得其所有“正值”均为素数的一个公式。

素数计算函数π(n)被定义为不大于n的素数之数量。例如，π(11) = 5，因为有5个素数小于或等于11。已知有算法可比去计算每个不大于n的素数更快的速率去计算π(n)的值。素数定理表示，π(n)的可由下列公式近似给出：

亦即，π(n)与等式右边的值在n趋近于无限大时，会趋近于1。这表示，小于n的数字为素数的可能性（大约）与n的数位呈正比。对π(n)更精确的描述可由对数积分给出：

素数定理亦蕰涵著对第n个素数（如₁ = 2、₂ = 3等）的大小之估算：当数字大到某一程度时，的值会变得约略为 log()。特别的是，素数间隙，即两个连续素数与₊₁间的差会变得任意地大。后者可由数列 ! + 2, ! + 3,…, ! + （其中n为任一自然数）看出。

等差数列是指由被一固定数（模）q除后会得到同一余数的自然数所组成之集合。例如：

是一个等差数列，模q = 9。除了3以外，其中没有一个数会是素数，因为3 + 9 = 3(1 + 3)，所以此一数列里的其他数字均为合数。（一般来所有大于q的素数都具有#· + 的形式，其中0 <  < #，且m没有不大于q的素因数。）因此，数列

只在a与q 互素（其最大公约数为1）之时，可以有无限多个素数。若满足此一必要条件，狄利克雷定理表示，该数列含有无限多个素数。下图描述 = 9时的情形：数字每遇到9的倍数就会再再由下往上缠一次。素数以红底标记。行（数列）开始于a = 3, 6, 9者至多只包含一个素数。其他行（a = 1, 2, 4, 5, 7, 8）则均包含无限多个素数。更甚之，素数以长期来看，会均匀分布于各行之中，亦即每个素数模9会与6个数其中一数同余的概率均为1/6。

格林-陶定理证明，存在由任意多个素数组成的等差数列。一个奇素数p可表示成两个平方数之和 = 2 + 2，当且仅当p同余于1模4（费马平方和定理）。

欧拉指出函数

于　0 ≤ < 40时会给出素数，此一事实导致了艰深的代数数论，或更具体地说为黑格纳数。当n更大时，该函数会给出合数值。哈代- 李特伍德猜想（Hardy-Littlewood conjecture）能给出一个有关具整数系数a、b与c的二次多项式

的值为素数之概率的一个渐近预测，并能以对数积分Li(n)及系数a、b、c来表示。不过，该程式已被证实难以取得：仍未知是否存在一个二次多项式（ ≠ 0）能给出无限多个素数。乌岚螺旋将所有自然数以螺旋的方法描绘。令人惊讶的是，素数会群聚在某些对角线上，表示有些二次多项式会比其他二次多项式给出更多个素数值来。

黎曼ζ函数ζ(s)被定义为一无穷级数

其中，s为实数部分大于1的一个复数。由算术基本定理可证得，该级数会等于下面的无穷乘积

ζ函数与素数密切相关。例如，存在无限多个素数这个事实也可以使用ζ函数看出：若只有有限多个素数，则ζ(1)将会是个有限值。不过，调和级数1 + 1/2 + 1/3 + 1/4 + ...会发散，所以必须有无限多个素数。另一个能看见ζ函数的丰富性，并一瞥现代代数数论的例子为下面的恒等式（巴塞尔问题，由欧拉给出）：

ζ(2)的倒数6/π2，是两个随机选定的数字会互素的概率。

未被证明的“黎曼猜想”，于1859年提出，表示除 = −2, −4, ...,外，ζ函数所有的根，其实数部分均为1/2。此一猜想与素数间的关连在于，该猜想实际上是在说，素数在正整数中出现频率和统计学的随机不同；若假设为真，素数计算函数便可有效掌握，在大数时不再需要近似求值。从物理的观点来看，这大约是在说，素数分布的不规则性仅来自于随机的噪声。从数学的观点来看，则大约是在说，素数的渐近分布（素数定理表示小于x的素数约有x/log x个）在x周围的区间内，于区间长度远小于x的平方根时亦成立。此一猜想一般认为是正确的。

除了黎曼猜想之外，还有许多其他的猜想存在。虽然这些猜想的陈述大多很简单，但许多猜想经过了数十年仍提不出证明，如4个兰道问题，从1912年提出至今仍然未解。其中一个为哥德巴赫猜想，该猜想认为每个大于2的偶数n都可表示成两个素数之和。至于2011年2月，这个猜想对最大达 = 2 · 1017的所有数字都会成立。较弱形式的哥德巴赫猜想已被证明，如维诺格拉多夫定理，该定理表示每个足够大的奇数都可表示成三个素数之和。陈氏定理表示，每个足够大的偶数都可表示成一个素数与一个半素数（两个素数的乘积）之和。此外，任一个偶数均可写成六个素数之和。数论研究这些问题的分支称之为加法数论。反哥德巴赫猜想，所有的正偶数n都可以表示成两个素数之差，但此猜想可由波利尼亚克猜想类推证明。

其他猜想处理是否有无限多个具某些限制的素数这类问题。据猜想，存在无限多个斐波那契素数与无限多个梅森素数，但没有无限多个费马素数。还不知道是否存在无限多个维费里希素数与欧几里得素数。

第三种类型的猜想涉及到素数的分布情形。据猜想，存在无限多对孪生素数，即有无限多对相差2的素数（孪生素数猜想）。波利尼亚克猜想是比孪生素数猜想更强的一个猜想，该猜想表示存在无限多对相差2n的连续素数。据猜想，存在无限多个具2 + 1形式的素数。上述猜想都是申策尔猜想的特例。布罗卡猜想表示，在两个大于2的连续素数之平方数之间，总是会有至少4个素数。勒让德猜想表示，对每个正整数n，2与( + 1)2间总会存在一个素数。克拉梅尔猜想可导出勒让德猜想。

长期以来，数论，尤其是对素数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪。然而，此一观点在1970年代时遭到粉碎，当素数被公开宣布可以作为产生公钥加密算法的基础之时。素数现在也被用在杂凑表与伪乱数产生器（英语：Pseudo-random number generator）里。

旋转机被设计成在每个转片上有不同数目的销，在每个转片上的销的数量都会是素数，亦或是会与其他转片上的销的数量互素。这有助于在重复所有的组合之前，让所有转片的可能组合都能出现过一次。

国际标准书号的最后一码为校验码，其算法使用到了11是个素数的这个事实。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的素数次数的使用也得到了证明。实验表明，素数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

“模运算”使用下列数字修改了一般的运算

其中n是个固定的自然数，称之为“模”。计算加法、减法及乘法都与一般的运算一样，不过负数或大于 − 1的数字出现时，会被除以n所得的余数取代。例如，对n=7，3+5为1，而不是8，因为8除以7余1。这通常念为“3+5同余于1模7”，并标记为

同样地，6 + 1 ≡ 0 (mod 7)、2 - 5 ≡ 4 (mod 7)，因为 -3 + 7 = 4，以及3 · 4 ≡ 5 (mod 7)，因为12除以7余5。加法与乘法在整数里常见的标准性质在模运算里也依然有效。使用抽象代数的说法，由上述整数所组成之集合，亦标记为Z/nZ，且因此为一可交换环。不过，除法在模运算里不一定都是可行的。例如，对n=6，方程

的解x会类比于2/3，无解，亦可透过计算3 · 0、...、3 · 5模6看出。不过，有关素数的不同性质如下：除法在模运算里是可行的，当且仅当n为素数。等价地说，n为素数，当且仅当所有满足2 ≤ ≤ − 1的整数m都会与n 互素，亦即其公约数只有1。实际上，对n=7，方程

会有唯一的解 = 3。因此，对任何素数p，Z/Z（亦标记为F）也会是个体，或更具体地说，是个有限域，因为该集合包含有限多（即p）个元素。

许多定理可以透过从此一抽象的方式检查F而导出。例如，费马小定理表示

，其中a为任一不被p整除的整数。该定理即可使用这些概念证得。这意味着

吾乡-朱加猜想表示，上述公式亦是p为素数的必要条件。另一个费马小定理的推论如下：若p为2与5之外的其他素数，1/总是个循环小数，其周期为 − 1或 − 1的约数。分数1/依q（10以外的整数）为基底表示亦有类似的效果，只要p不是q的素因数的话。威尔逊定理表示，整数 > 1为素数，当且仅当阶乘 ( − 1)! + 1可被p整除。此外，整数n > 4为合数，当且仅当 ( − 1)!可被n整除。

许多数学领域里会大量使用到素数。举有限群的理论为例，西罗定理即是一例。该定理表示，若G是个有限群，且为素数p可整除G的阶的最大幂次，则G会有个阶的子群。此外，任意素数阶的群均为循环群（拉格朗日定理）。

几个公开金钥加密算法，如RSA与迪菲－赫尔曼金钥交换，都是以大素数为其基础（如512位元的素数常被用于RSA里，而1024位元的素数则一般被迪菲-赫尔曼金钥交换所采用）。RSA依靠计算出两个（大）素数的相乘会比找出相乘后的数的两个素因数容易出许多这个假设。迪菲－赫尔曼金钥交换依靠存在模幂次的有效算法，但相反运算的离散对数仍被认为是个困难的问题此一事实。

周期蝉属里的蝉在其演化策略上使用到素数。蝉会在地底下以幼虫的形态度过其一生中的大部分时间。周期蝉只会在7年、13年或17年后化蛹，然后从洞穴里出现、飞行、交配、产卵，并在至多数周后死亡。此一演化策略的原因据信是因为若出现的周期为素数年，掠食者就很难演化成以周期蝉为主食的动物。若周期蝉出现的周期为非素数年，如12年，则每2年、3年、4年、6年或12年出现一次的掠食者就一定遇得到周期蝉。经过200年以后，假设14年与15年出现一次的周期蝉，其掠食者的平均数量，会比13年与17年出现一次的周期蝉，高出2%。虽然相差不大，此一优势似乎已足够驱动天择，选择具素数年生命周期的这些昆虫。

据猜测，ζ函数的根与复数量子系统的能阶有关。

素数的概念是如此的重要，以致此一概念被以不同方式推广至数学的不同领域里去。通常，“质”（prime）可在适当的意义下，用来表示具有最小性或不可分解性。例如，质体是指一个包含0与1的体F的最小子域。质体必为有理数或具有p个元素的有限域，这也是其名称的缘由。若任一对象基本上均可唯一地分解成较小的部分，则这些较小的部分也会用“质”这个字来形容。例如，在纽结理论里，质纽结是指不可分解的纽结，亦即该纽结不可写成两个非平凡纽结的连通和。任一纽结均可唯一地表示为质纽约的连通和。质模型与三维质流形亦为此类型的例子。

素数应用于任一可交换环R（具加法、减法与乘法的代数结构）的元素，可产生两个更为一般的概念：“素元”与“不可约元素”。R的元素称为素元，若该元素不为0或单位元，且给定R内的元素x与y，若p可除以xy，则p可除以x或y。一元素称为不可约元素，若该元素不为单位元，且无法写成两个不是单位元之环元素的乘积。在整数环Z里，由素元所组成的集合等于由不可约元素所组成的集合，为

在任一环R里，每个素元都是不可约元素。反之不一定成立，但在唯一分解整环里会成立。

算术基本定理在唯一分解整环里仍然成立。此类整环的一个例子为高斯整数Z，由具a + bi（其中a与b为任意整数）形式的复数所组成之集合。其素元称之为“高斯素数”。不是所有的素数都是高斯素数：在这个较大的环Z之中，2可被分解成两个高斯素数 (1 + i)与 (1 - i)之乘积。有理素数（即在有理数里的素元），具4k+3形式者为高斯素数；具4k+1形式者则不是。

在环论里，数的概念一般被理想所取代。“素理想”广义化了素元的概念，为由素元产生的主理想，是在交换代数、代数数论与代数几何里的重要工具与研究对象。整数环的素理想为理想 (0)、(2)、(3)、(5)、(7)、(11)、…算术基本定理被广义化成准素分解，可将每个在可交换诺特环里的理想表示成准素理想（为素数幂次的一适合广义化）的交集。

透过环的谱这个概念，素理想成为代数几何对象的点。算术几何也受益于这个概念，且许多概念会同时存在于几何与数论之内。例如，对一扩张域的素理想分解（这是代数数论里的一个基本问题），与几何里的分歧具有某些相似之处。此类分歧问题甚至在只关注整数的数论问题里也会出现。例如，二次域的整数环内的素理想可被用来证明二次互反律。二次互反律讨论下面二次方程

是否有整数解，其中x为整数，p与q为（一般）素数。早期对费马最后定理证明之尝试，于恩斯特·库默尔引入正则素数后达到了高潮。正则素数是指无法在由下列式子（其中₀、…、−1为整数，ζ则是能使ζ = 1的复数）

组成的环里，使得唯一分解定理失效的素数。

赋值理论研究由一个体K映射至实数R的某个函数（称之为赋值）。每个此类赋值都能给出一个 K上的拓扑，且两个赋值被称为等价，若两者有相同拓扑。K的素数为一赋值的等价类。例如，一个有理数q的p进赋值被定义为整数()，使得

其中r与s不被p所整除。例如，₃(18/7) = 2。p进范数被定义为

特别的是，当一个数字乘上p时，其范数会变小，与一般的绝对赋值（亦称为无限素数）形成明显的对比。当透过绝对赋值完备有理数会得出由实数所组成的体，透过p进范数完备有理数则会得出由p进数所组成的体。实际上，依据奥斯特洛夫斯基定理，上述两种方法是完备有理数的所有方法。一些与有理数或更一般化之整体域有关的算术问题，可能可以被变换至完备（或局部）体上。此一局部-全域原则再次地强调了素数对于数论的重要性。

素数也影响了许多的艺术家与作家。法国作曲家奥立佛·梅湘使用素数创造出无节拍音乐。在《La Nativite du Seigneur》与《Quatre etudes de rythme》等作品里，梅湘同时采用由不同素数给定之长度的基调，创造出不可预测的节奏：第三个练习曲《Neumes rythmiques》中出现了素数41、43、47及53。据梅湘所述，此类作曲方式是“由自然的运动，自由且不均匀的持续运动中获得的灵感”。

NASA科学家卡尔·萨根在他的科幻小说《接触未来》（）里，认为素数可作为与外星人沟通的一种方式。这种想法是他与美国天文学家法兰克·德雷克于1975年闲聊时形成的。

许多电影，如《异次元杀阵》（）、《神鬼尖兵》（）、《越爱越美丽》（）及《美丽境界》（），均反映出大众对素数与密码学之神秘的迷恋。保罗·裘唐诺所著的小说《素数的孤独》（The Solitude of Prime Numbers）里，素数被用来比喻寂寞与孤独，被描述成整数之间的“局外人”。

荒木飞吕彦所创作的日本漫画《JoJo的奇妙冒险》第六部《石之海》的反派普奇神父喜欢数素数，他认为素数是孤独的数字，并透过数素数安抚他紧张的情绪。