素数：修订间差异

2026年9月20日 (日) 07:17的最新版本

素数（prime number），又称质数，是大于 1、只有 1 和自身两个正因数的整数，例如 2、3、5、7、11。大于 1 而不是素数的整数称为合数，例如 $12 = 3 \cdot 4$ 。0 和 1 既不是素数，也不是合数。

素数在乘法中扮演基本因子的角色。12 可以拆成 $3 \cdot 4$ ，再把 4 拆成 $2 \cdot 2$ ，得到 $12 = 2 \cdot 2 \cdot 3$ 。其中 2 和 3 已经不能继续拆成两个大于 1 的整数之积；分解便在素数处停下来。

为什么从 2 开始

1 只有一个正因数，不符合“恰有两个正因数”的定义。它在乘法中的作用也与素因子不同：给 $12 = 2 \cdot 2 \cdot 3$ 添上任何多个 1，都没有改变分解的信息。把 1 单独看作乘法的单位，就能直接讨论那些真正构成整数的因子。

2 是唯一的偶素数。任何大于 2 的偶数都含有因数 2，而这个因数既不是 1，也不是它自身。奇数则可能是素数，也可能是合数，例如 9、15、21 都有更小的因子。

素数定义在这里针对正整数。分解负整数时，可以先提出负号，再分解绝对值；0 则被每个正整数整除，不属于素数和合数的分类范围。

判断一个数是不是素数

判定 97 时，可以依次试除，但不必一直试到 96。若 $n = a b$ ，其中 $1 < a \leq b$ ，那么 $a^{2} \leq a b = n, a \leq \sqrt{n} .$ 所以合数总有一个不超过平方根的非平凡因数。若这个因数还不是素数，可以继续分解，最终得到一个同样不超过平方根的素因子。

97 的平方根在 9 与 10 之间，候选素因子只有 2、3、5、7。97 是奇数，不能被 2 整除；各位数字和为 16，不能被 3 整除；末位不是 0 或 5，不能被 5 整除；最后 $97 = 7 \cdot 13 + 6$ ，也不能被 7 整除。因此 97 是素数。数字和判据的理由可见同余。

再看 221。它的平方根小于 15，需要检查 2、3、5、7、11、13。前几个因子均不成功，但 $221 = 13 \cdot 17,$ 所以 221 是合数。平方根界包括等号，例如 49 的因数 7 就恰好等于其平方根。

这类试除法对较小的整数很直接：只要把规定范围的候选因子检查完，就能从“没有找到因子”推出素性。整数很大时，候选数量也会很大，因而还需要更高效的素性判定算法。

用筛法找出一整段素数

若要找出所有不超过 50 的素数，逐个对每个整数试除会重复很多工作。埃拉托色尼筛法改为一次删掉同一个素数的合数倍数。

先列出 2 到 50。保留 2，划去 4、6、8 等更大的偶数。下一个未被划去的数是 3，保留它，划去 9、12、15 等倍数；其中 6 已经在第一轮划去。接下来保留 5、7，分别处理它们的倍数。留下 $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.$ 共有 15 个。

下图把保留的素数用金框标出，合数划去，角上的 p 表示首先筛掉它的素因子。例如 25 标 p=5，49 标 p=7；1 因不大于 1，从一开始就不参加筛选。图底的 π(50) 表示不超过 50 的素数个数。先看这两个平方位置，再看被 2、3 划去的整列数字，可以核对为什么只需四轮。

一到五十的数字表，十五个素数用金框保留，合数划线并标出首次筛除的素因子，二十五和四十九分别标五和七 — 筛到 7 后，所有不超过 50 的合数都有了对应的小素因子。

每个被划去的数都有一个比自身小的因子。反过来，任何不超过 50 的合数都有一个不超过 $\sqrt{50} < 8$ 的素因子，因此经过 2、3、5、7 四轮以后，所有合数都已被划去。

处理素数 p 时，从 $p^{2}$ 开始划就够了。比它小的倍数 $2 p, 3 p, \dots, (p - 1) p$ ，已经含有小于 p 的素因子，早先就被处理过。这个观察减少了重复标记，但保留了同一筛选结果。筛法名称与古希腊的 Eratosthenes 相联系，相关史料见 MacTutor 素数史。

整数分解为何总能完成

以 360 为例，可以先分成 $36 \cdot 10$ ： $360 = (2^{2} \cdot 3^{2}) (2 \cdot 5) = 2^{3} \cdot 3^{2} \cdot 5.$ 也可以先分成 $8 \cdot 45$ ，最终仍得到三个 2、两个 3、一个 5。算术基本定理说明，这不是该例的巧合：每个大于 1 的整数都有素数分解，而且除因子顺序外分解唯一。

先证明分解存在。使用强归纳法：假定小于 n 而大于 1 的整数都已有素数分解。如果 n 本身是素数，已经完成；否则写成 $n = a b$ ，其中 a、b 都大于 1 且小于 n。将它们各自的素数分解相乘，就得到 n 的分解。从最小的情形 n=2 开始，这个论证覆盖所有大于 1 的整数。

不同的拆分为何得到同一结果

唯一性依赖一个关键性质：若素数 p 整除乘积 ab，则 p 整除 a 或 b。 若 p 不整除 a，由于 p 的正因数只有 1 和 p，便有 $gcd (p, a) = 1$ 。裴蜀等式给出整数 u、v，使 $u p + v a = 1.$ 两边乘以 b，得到 $u p b + v a b = b$ 。左边第一项含因子 p，第二项由 $p ∣ a b$ 也被 p 整除，所以 p 整除 b。这叫欧几里得引理。对三个或更多因子的乘积，可以反复应用同一结论。

现在设某个整数有两份素数分解。第一份的首个素因子 p 整除第二份的整个乘积，因此整除其中某个素因子 q。素数 q 的正因数只有 1 和 q，而 $p > 1$ ，所以 $p = q$ 。从两份乘积中各约去一次这个因子，再对剩下的乘积重复。若一份先约尽而另一份还有素因子，就会得到 1 等于若干大于 1 的整数之积，这是不可能的。因此两份因子及其出现次数全部匹配。

素因子指数怎样描述全部因数

回到 $360 = 2^{3} \cdot 3^{2} \cdot 5$ 。它的每个正因数，都从这份因子清单中选择一些因子，故形式为 $2^{α} 3^{β} 5^{γ}, 0 \leq α \leq 3, 0 \leq β \leq 2, 0 \leq γ \leq 1,$ 其中各指数为整数。指数 α 有 4 种选择，β 有 3 种，γ 有 2 种；唯一分解保证不同的选择不会得到同一个数。因此正因数共有 $4 \cdot 3 \cdot 2 = 24$ 个。

与 $84 = 2^{2} \cdot 3 \cdot 7$ 比较时，共同因数不能使用只出现在一边的素数，也不能使用超过任何一边供给量的指数。于是最大公因数为 $gcd (360, 84) = 2^{2} \cdot 3 = 12.$ 共同倍数则至少要包含两边要求的全部因子，各素数取较大指数，得到 $lcm (360, 84) = 2^{3} \cdot 3^{2} \cdot 5 \cdot 7 = 2520.$ 复核有 $12 \cdot 2520 = 360 \cdot 84$ ，与最大公因数和最小公倍数的乘积关系一致。

完全平方数也能由指数辨认。一个整数平方时，每个素因子的指数都加倍，因此全为偶数；反过来，若所有指数都是偶数，把指数减半便得到整数平方根。360 中 2 与 5 的指数为奇数，所以它不是完全平方数。

同样的整除性质还可证明素数的平方根是无理数。假设 $\sqrt{p} = a / b$ ，其中 a、b 为互素正整数，则 $a^{2} = p b^{2}$ 。由素数引理， $p ∣ a$ ，令 $a = p c$ ，代入并约去一个 p，得到 $p c^{2} = b^{2}$ 。再用引理得 $p ∣ b$ ，与 a、b 互素矛盾。

素数是否会在某处用完

假设已经列出有限多个素数 $p_{1}, \dots, p_{k}$ ，把它们相乘再加 1： $N = p_{1} p_{2} \dots p_{k} + 1.$ 清单中的每个素数除 N 都余 1，所以没有一个能整除 N。但 $N > 1$ ，一定有素因子；这个素因子必定不在清单中。因此任意有限清单都不能列完素数，素数有无限多个。

构造出的 N 本身未必是素数。例如取前六个素数， $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509.$ 虽然得到合数，它的素因子仍在原清单之外，这已经足够完成论证。欧几里得《几何原本》第九卷命题二十给出了超出任意有限素数清单的论证，原文见 Joyce 编注的 IX.20。

无限多也允许相邻素数之间出现很长的空档。给定正整数 m，取 $N = (m + 1)!$ ，这里的阶乘表示从 1 到 m+1 的整数连乘。于是 $N + 2, N + 3, \dots, N + m + 1$ 分别被 2、3、……、m+1 整除，而且每项都大于相应因数。这就构成连续 m 个合数。m 可以任意大，故合数连续出现的长度没有固定上界。

从素性检验到整体分布

试除和筛法提供确定的因子检验；有些更快的检验则利用同余性质。费马小定理说，若 p 为素数且 p 不整除 a，则 $a^{p - 1} \equiv 1 (\mod p) .$ 同余符号表示两边除以 p 有相同余数。若某个整数不满足相应等式，就可以排除它是素数；满足等式，却还可能是合数。

例如 $341 = 11 \cdot 31$ ，而 $2^{10} = 1024 = 3 \cdot 341 + 1$ 。连续相乘可得 $2^{340} = (2^{10})^{34} \equiv 1 (\mod 341)$ 。341 因而通过了底数 2 的这项检验。费马小定理给出素数应有的性质，这个例子说明该性质本身还不足以反推素性。

另一个研究方向是不再逐个判定，而是统计素数有多少。记 $π (x)$ 为不超过 x 的素数个数，例如上面的筛选得到 $π (50) = 15$ 。素数定理指出 $lim_{x \to \infty} \frac{π (x)}{x / \log x} = 1,$ 其中 $\log$ 为自然对数。它说明 $x / \log x$ 给出了大范围计数的相对近似，不是每个 x 处的精确等式。证明需要进一步的分析方法。

Hadamard 与 de la Vallée Poussin 在 1896 年分别证明了素数定理。MacTutor 素数史记录了从古代无限性和筛法，到近代整体分布研究的发展。素数虽然没有固定的等距排列，却具有唯一分解、可检验的整除规律，以及可精确表述的分布定理。

参考资料

Karl-Dieter Crisman，Number Theory: In Context and Interactive：素数、筛法、分解与分布。
同书，To Infinity and Beyond。
Euclid，Elements，IX.20，David Joyce 编注。
J. J. O’Connor、E. F. Robertson，Prime numbers。
相关条目：整数整除、同余、逻辑。

@@ 第1行： / 第1行： @@
-'''素数'''（prime number），又称质数，是大于一、恰有一和自身两个正因数的整数。大于一而不是素数的整数称为合数；零和一都不属于这两类。素数的核心作用是构成正整数乘法的不可再分因子：每个大于一的整数都能分解成素数乘积，并且除因子顺序外分解唯一。素数研究既包括单个整数的判定，也包括所有素数的整体分布，这两类问题需要不同的方法。
+'''素数'''（prime number），又称质数，是大于 1、只有 1 和自身两个正因数的整数，例如 2、3、5、7、11。大于 1 而不是素数的整数称为合数，例如 <math>12=3\cdot4</math>。0 和 1 既不是素数，也不是合数。
-== 乘法分类为何把一排除在外 ==
+素数在乘法中扮演基本因子的角色。12 可以拆成 <math>3\cdot4</math>，再把 4 拆成 <math>2\cdot2</math>，得到 <math>12=2\cdot2\cdot3</math>。其中 2 和 3 已经不能继续拆成两个大于 1 的整数之积；分解便在素数处停下来。
-十二可以写成三乘四，还可继续分成 <math>2\cdot2\cdot3</math>；其中二和三无法再写成两个大于一的整数之积。这种“分解终点”促成了素数概念。与加法不同，乘法中存在特殊单位一，乘上一不会改变原数，所以必须把它与真正提供因子的素数分开。
-一只有一个正因数，而不是两个，因此不满足素数定义。更结构性的原因是：若允许一作为素因子，任何分解都可任意插入若干个一，唯一分解的陈述便要额外排除这些无效因子。现代定义直接把单位与素数分开，使定理清楚表达真正的乘法信息。这不是为了临时照顾某个例题，而是使分类与后续理论相容。
+== 为什么从 2 开始 ==
+只有一个正因数，不符合“恰有两个正因数”的定义。它在乘法中的作用也与素因子不同：给 <math>12=2\cdot2\cdot3</math> 添上任何多个 1，都没有改变分解的信息。把 1 单独看作乘法的单位，就能直接讨论那些真正构成整数的因子。
-零的正因数不止两个，因为每个正整数都整除零；它同样不是素数。负数不列入本文素数定义，负整数的分解可以把负号提出，再分解绝对值。更广泛的代数理论会讨论素元与单位，但在初等整数论里，采用正素数可避免因正负号产生重复表示。
+是唯一的偶素数。任何大于 2 的偶数都含有因数 2，而这个因数既不是 1，也不是它自身。奇数则可能是素数，也可能是合数，例如 9、15、21 都有更小的因子。
-二是唯一的偶素数：任何大于二的偶数都有因数二，且这个因数既不是一也不是自身。奇数却未必是素数，例如九和二十一都是合数。“除二以外素数都是奇数”只有一个方向，不能反过来当成判定规则。很多关于素数的错误猜测，都来自把必要条件误当成充分条件。
+素数定义在这里针对正整数。分解负整数时，可以先提出负号，再分解绝对值；0 则被每个正整数整除，不属于素数和合数的分类范围。
-== 为何试除只需到平方根 ==
+== 判断一个数是不是素数 ==
-若整数 <math>n>1</math> 为合数，可写成 <math>n=ab</math>，其中 <math>1<a\le b<n</math>。于是 <math>a^2\le ab=n</math>，所以至少一个非平凡因数不超过平方根。该因数还有一个素因子，同样不超过平方根。因此只需检查不超过 <math>\sqrt n</math> 的素数是否整除 <math>n</math>，即可判定它是否为素数。
+判定 97 时，可以依次试除，但不必一直试到 96。若 <math>n=ab</math>，其中 <math>1<a\le b</math>，那么
+<math display="block">a^2\le ab=n,\qquad a\le\sqrt n.</math>
+所以合数总有一个不超过平方根的非平凡因数。若这个因数还不是素数，可以继续分解，最终得到一个同样不超过平方根的素因子。
-例如判定九十七。因为平方根在九与十之间，只需检查二、三、五、七。它是奇数，数字和为十，末位既不是零也不是五，分别排除前三者；除以七得到十三余六，排除最后一个。所以九十七是素数。这里“没有找到因数”能成为证明，是因为已经检查了由定理保证充分的完整范围，而不是只试了几个方便的小数。
+的平方根在 9 与 10 之间，候选素因子只有 2、3、5、7。97 是奇数，不能被 2 整除；各位数字和为 16，不能被 3 整除；末位不是 0 或 5，不能被 5 整除；最后 <math>97=7\cdot13+6</math>，也不能被 7 整除。因此 97 是素数。数字和判据的理由可见[[同余]]。
-再看二百二十一。平方根小于十五，候选素因子为二、三、五、七、十一、十三。前五者均不能整除，但 <math>221=13\cdot17</math>，所以是合数。这个例子显示，排除常见的小因子还不够；必须覆盖全部必要候选，或者使用另一种有证明保障的判定方法。
+再看 221。它的平方根小于 15，需要检查 2、3、5、7、11、13。前几个因子均不成功，但
+<math display="block">221=13\cdot17,</math>
+所以 221 是合数。平方根界包括等号，例如 49 的因数 7 就恰好等于其平方根。
-平方根边界必须包含等号。若只检查严格小于平方根的数，会把四十九这类素数平方漏掉。实现时还应先排除小于二的输入，避免空循环被误解释为“没有因数所以是素数”。对于很大的整数，可比较候选因子的平方与原数，或使用整数平方根，避免浮点近似在边界处造成错误。
+这类'''试除法'''对较小的整数很直接：只要把规定范围的候选因子检查完，就能从“没有找到因子”推出素性。整数很大时，候选数量也会很大，因而还需要更高效的素性判定算法。
-== 筛法一次处理一段整数 ==
+== 用筛法找出一整段素数 ==
-埃拉托色尼筛法把从二到某个上界的整数写成列表：保留最小尚未被删去的数，并删去它更大的倍数；然后继续处理下一个尚未被删去的数。最小未删数必为素数，因为若它合成于更小因子，早已在较小素因子的步骤中被删去。
+若要找出所有不超过 50 的素数，逐个对每个整数试除会重复很多工作。埃拉托色尼筛法改为一次删掉同一个素数的合数倍数。
-以五十为上界，先删去大于二的偶数，再删去三、五、七的合数倍数。此后无需继续筛，因为下一个素数十一的平方已经超过五十。保留下来的素数为
+先列出 2 到 50。保留 2，划去 4、6、8 等更大的偶数。下一个未被划去的数是 3，保留它，划去 9、12、15 等倍数；其中 6 已经在第一轮划去。接下来保留 5、7，分别处理它们的倍数。留下
 <math display="block">2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.</math>
-这是完整列表，共十五个。每个被删去的数都有明确因子，每个保留的数又没有平方根以内的素因子，两侧理由共同保证正确性。
+共有 15 个。
-处理素数 <math>p</math> 时，可以从 <math>p^2</math> 开始标记，因为更小的倍数已经包含某个小于 <math>p</math> 的素因子，早在之前被处理。这个优化不改变数学结果，只减少重复工作。筛法适合批量列举一个范围内的素数；对一个位数很大的孤立整数，则通常需要别的方法，不能把两种任务的成本混为一谈。
+下图把保留的素数用金框标出，合数划去，角上的 p 表示首先筛掉它的素因子。例如 25 标 p=5，49 标 p=7；1 因不大于 1，从一开始就不参加筛选。图底的 π(50) 表示不超过 50 的素数个数。先看这两个平方位置，再看被 2、3 划去的整列数字，可以核对为什么只需四轮。
-筛法名称与古希腊的 Eratosthenes 相联系，约公元前三世纪的相关历史见 [https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/ MacTutor：Prime numbers]。这里采用现代列表与平方起点的算法表述，不表示古代文献已经逐字使用同样的程序式描述。
+[[File:Gezhi-teaching-foundation-prime-sieve.svg|frame|center|alt=一到五十的数字表，十五个素数用金框保留，合数划线并标出首次筛除的素因子，二十五和四十九分别标五和七|筛到 7 后，所有不超过 50 的合数都有了对应的小素因子。]]
-== 唯一分解需要证明存在与唯一两部分 ==
+每个被划去的数都有一个比自身小的因子。反过来，任何不超过 50 的合数都有一个不超过 <math>\sqrt{50}<8</math> 的素因子，因此经过 2、3、5、7 四轮以后，所有合数都已被划去。
-算术基本定理说，每个整数 <math>n>1</math> 都能写成素数幂的有限乘积，且各个素数及其指数唯一，因子顺序可以不同。这里“存在”保证分解总能完成，“唯一”保证不同分解过程不会得到互相矛盾的因子清单。两个结论不能只凭分解几个小数就当作理所当然。
-'''存在性证明。''' 用强归纳法。二本身为素数。对任意大于一的整数，如果它是素数，分解已经完成；如果是合数，就写成两个严格更小且大于一的整数之积。依归纳假设，两个因子都已有素数分解，把它们相乘即可。因子严格变小保证这个论证不会无限循环。
+处理素数 p 时，从 <math>p^2</math> 开始划就够了。比它小的倍数 <math>2p,3p,\ldots,(p-1)p</math>，已经含有小于 p 的素因子，早先就被处理过。这个观察减少了重复标记，但保留了同一筛选结果。筛法名称与古希腊的 Eratosthenes 相联系，相关史料见 [https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/ MacTutor 素数史]。
-'''欧几里得引理。''' 若素数 <math>p</math> 整除 <math>ab</math>，那么它整除 <math>a</math> 或 <math>b</math>。如果不整除 <math>a</math>，则 <math>\gcd(p,a)=1</math>；裴蜀等式给出整数 <math>u,v</math> 使 <math>up+va=1</math>。乘以 <math>b</math> 后，左边两项都被 <math>p</math> 整除，因此 <math>p\mid b</math>。这一步说明素数与普通合数的实质区别。
+== 整数分解为何总能完成 ==
+以 360 为例，可以先分成 <math>36\cdot10</math>：
+<math display="block">360=(2^2\cdot3^2)(2\cdot5)=2^3\cdot3^2\cdot5.</math>
+也可以先分成 <math>8\cdot45</math>，最终仍得到三个 2、两个 3、一个 5。'''算术基本定理'''说明，这不是该例的巧合：每个大于 1 的整数都有素数分解，而且除因子顺序外分解唯一。
-'''唯一性证明。''' 假设同一个整数有两份素数乘积表示。第一份中的一个素因子整除第二份乘积，由引理必整除其中某个素因子；素数的正因数只有一和自身，因此这两个素因子相同。把它们约去，对剩余乘积重复。最终所有因子逐个匹配，次数也一致，唯一性得证。
+先证明分解存在。使用强归纳法：假定小于 n 而大于 1 的整数都已有素数分解。如果 n 本身是素数，已经完成；否则写成 <math>n=ab</math>，其中 a、b 都大于 1 且小于 n。将它们各自的素数分解相乘，就得到 n 的分解。从最小的情形 n=2 开始，这个论证覆盖所有大于 1 的整数。
-常见的“拆因数树”只直接显示存在性，不自动证明唯一性。引理填补了这个逻辑缺口。类似的唯一分解性质在更一般代数系统中可能失败，所以在整数中证明它不是多余的形式工作。后续用指数比较整除、最大公因数与最小公倍数，均依赖分解确实唯一。
+=== 不同的拆分为何得到同一结果 ===
+唯一性依赖一个关键性质：'''若素数 p 整除乘积 ab，则 p 整除 a 或 b。''' 若 p 不整除 a，由于 p 的正因数只有 1 和 p，便有 <math>\gcd(p,a)=1</math>。[[整数整除|裴蜀等式]]给出整数 u、v，使
+<math display="block">up+va=1.</math>
+两边乘以 b，得到 <math>upb+vab=b</math>。左边第一项含因子 p，第二项由 <math>p\mid ab</math> 也被 p 整除，所以 p 整除 b。这叫欧几里得引理。对三个或更多因子的乘积，可以反复应用同一结论。
-== 用素因子指数计算，而不只写分解式 ==
+现在设某个整数有两份素数分解。第一份的首个素因子 p 整除第二份的整个乘积，因此整除其中某个素因子 q。素数 q 的正因数只有 1 和 q，而 <math>p>1</math>，所以 <math>p=q</math>。从两份乘积中各约去一次这个因子，再对剩下的乘积重复。若一份先约尽而另一份还有素因子，就会得到 1 等于若干大于 1 的整数之积，这是不可能的。因此两份因子及其出现次数全部匹配。
-以 <math>360=2^3\cdot3^2\cdot5</math> 为例，任何正因数都必须形如 <math>2^\alpha3^\beta5^\gamma</math>，其中 <math>0\le\alpha\le3</math>、<math>0\le\beta\le2</math>、<math>0\le\gamma\le1</math>，指数是整数。每个选择产生一个因数，不同选择因唯一分解而不重复，所以三百六十恰有 <math>4\cdot3\cdot2=24</math> 个正因数。
-再与 <math>84=2^2\cdot3\cdot7</math> 比较，共同因数只能使用两份分解都提供的素因子，指数取较小值；共同倍数则必须至少容纳两份需要，指数取较大值。因此最大公因数为 <math>2^2\cdot3=12</math>，最小公倍数为 <math>2^3\cdot3^2\cdot5\cdot7=2520</math>。复核乘积得到 <math>12\cdot2520=360\cdot84</math>。
+== 素因子指数怎样描述全部因数 ==
+回到 <math>360=2^3\cdot3^2\cdot5</math>。它的每个正因数，都从这份因子清单中选择一些因子，故形式为
+<math display="block">2^\alpha3^\beta5^\gamma,\qquad
+\le\alpha\le3,\quad0\le\beta\le2,\quad0\le\gamma\le1,</math>
+其中各指数为整数。指数 α 有 4 种选择，β 有 3 种，γ 有 2 种；唯一分解保证不同的选择不会得到同一个数。因此正因数共有 <math>4\cdot3\cdot2=24</math> 个。
-分解还判断一个正整数是否为完全平方数：当且仅当每个素因子指数都是偶数。平方会使全部指数加倍；反过来，若各指数都是偶数，全部除以二便构造出整数平方根。例如三百六十的二指数与五指数为奇数，所以不是平方数。这个判断取决于指数结构，而不必先计算近似平方根。
+与 <math>84=2^2\cdot3\cdot7</math> 比较时，共同因数不能使用只出现在一边的素数，也不能使用超过任何一边供给量的指数。于是最大公因数为
+<math display="block">\gcd(360,84)=2^2\cdot3=12.</math>
+共同倍数则至少要包含两边要求的全部因子，各素数取较大指数，得到
+<math display="block">\operatorname{lcm}(360,84)=2^3\cdot3^2\cdot5\cdot7=2520.</math>
+复核有 <math>12\cdot2520=360\cdot84</math>，与最大公因数和最小公倍数的乘积关系一致。
-由同一原理可证明素数的平方根无理。若 <math>\sqrt p=a/b</math> 是约成最简的整数比，则 <math>a^2=pb^2</math>。素数引理迫使 <math>p\mid a</math>，代回又迫使 <math>p\mid b</math>，与最简分数矛盾。这将整数因子理论与实数中的无理性联系起来，说明素数并不只是一个用于分类整数的名词。
+完全平方数也能由指数辨认。一个整数平方时，每个素因子的指数都加倍，因此全为偶数；反过来，若所有指数都是偶数，把指数减半便得到整数平方根。360 中 2 与 5 的指数为奇数，所以它不是完全平方数。
-== 素数为什么永远列不完 ==
+同样的整除性质还可证明素数的平方根是无理数。假设 <math>\sqrt p=a/b</math>，其中 a、b 为互素正整数，则 <math>a^2=pb^2</math>。由素数引理，<math>p\mid a</math>，令 <math>a=pc</math>，代入并约去一个 p，得到 <math>pc^2=b^2</math>。再用引理得 <math>p\mid b</math>，与 a、b 互素矛盾。
-取任何有限素数清单 <math>p_1,\ldots,p_k</math>，构造
+== 素数是否会在某处用完 ==
+假设已经列出有限多个素数 <math>p_1,\ldots,p_k</math>，把它们相乘再加 1：
 <math display="block">N=p_1p_2\cdots p_k+1.</math>
-它大于一，因此有某个素因子。清单里的每个素数都不能整除它，因为除后余一；所以这个素因子不在清单中。无论给出怎样的有限清单，总能证明还有清单以外的素数，从而素数无限多。
+清单中的每个素数除 N 都余 1，所以没有一个能整除 N。但 <math>N>1</math>，一定有素因子；这个素因子必定不在清单中。因此任意有限清单都不能列完素数，素数有无限多个。
-论证不要求 <math>N</math> 自己是素数。这一点很关键：取前六个素数，得到 <math>30031=59\cdot509</math>，它是合数，却仍有清单外的新素因子。把证明误读成“前若干素数相乘加一总是素数”，会把一个正确的存在性论证变成错误的生成公式。
-欧几里得《几何原本》第九卷命题二十已给出超出任意给定素数清单的构造论证，原文可见 [https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html Joyce 编注的 IX.20]。本文使用现代乘积记法重述其思想，不把现代符号形式与古代原文混为一谈。它回答“是否有无限多个”，并没有直接告诉人们第几万个素数是什么。
-无限多也不意味着间距有固定上界。给定正整数 <math>m</math>，令 <math>N=(m+1)!</math>，则 <math>N+2,\ldots,N+m+1</math> 分别被二到 <math>m+1</math> 整除，全部是合数。于是可以构造任意长的连续合数区间。这个简单证明与无限多素数并不冲突：整体无穷与局部稀疏可以同时成立。
-== 判定、分解与分布是不同问题 ==
-知道一个整数为合数，并不一定已经知道它的非平凡因子；知道一个数通过某种测试，也不一定已经证明它是素数。以费马小定理为例，素数 <math>p</math> 与不被它整除的整数 <math>a</math> 满足 <math>a^{p-1}\equiv1\pmod p</math>，但这一条件不能直接反用。
-合数 <math>341=11\cdot31</math> 便能通过底数二的这项检验，因为 <math>2^{10}=1024\equiv1\pmod{341}</math>，从而 <math>2^{340}\equiv1\pmod{341}</math>。这个例子并未否定费马小定理，而是否定其未经证明的逆命题。更精细的素性算法会使用额外论证或明确的概率保证，报告时应区分测试结果与可核验的证明。
-素数计数函数 <math>\pi(x)</math> 表示不超过实数 <math>x</math> 的素数个数。素数定理为
-<math display="block">\pi(x)\sim\frac{x}{\log x}\qquad(x\to\infty),</math>
-其中对数为自然对数，符号 <math>\sim</math> 表示两边比值趋于一。它描述大尺度计数，不是每个位置上精确的素数概率，也不是一个能逐个输出素数的公式。证明需要超出本条的分析工具，这里只给出准确陈述。
-Hadamard 与 de la Vallée Poussin 在 1896 年分别证明素数定理，标志着关于整体密度的猜测获得严格依据；相关历史见 [https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/ MacTutor 素数史]。从古代无限性证明到近代密度定理，研究问题已发生变化，因此不能把“素数是谁发现的”压成一个人名与年份。
-== 定义的有效范围 ==
-“素数”不是对所有数域都不变的标签。二在整数中为素数；若允许形如 <math>a+bi</math> 的高斯整数，则 <math>2=(1+i)(1-i)</math>，两因子都不是单位。这个例子不要求立即掌握整个高斯整数理论，却提醒因数必须在规定的系统内选择。换了允许的因子范围，就换了分类问题。
-所谓素数“没有规律”，通常只是说局部排列不由简单等差间距给出，不能理解成不存在任何定理或算法。筛法、唯一分解和素数定理分别是精确的算法规律、代数规律与渐近规律。把不同层次的知识区分开，比笼统宣称素数神秘更有解释力。
-同样，计算出很多例子不能替代全称证明。某个多项式在前几十个整数上产生素数，并不足以保证以后一直如此。有限验证可以发现模式、排除错误和支持猜想；从模式到定理，还需能够覆盖所有情况的论证。素数条目特别适合展示这种数学方法上的分工。
+构造出的 N 本身未必是素数。例如取前六个素数，
+<math display="block">2\cdot3\cdot5\cdot7\cdot11\cdot13+1
+=30031=59\cdot509.</math>
+虽然得到合数，它的素因子仍在原清单之外，这已经足够完成论证。欧几里得《几何原本》第九卷命题二十给出了超出任意有限素数清单的论证，原文见 [https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html Joyce 编注的 IX.20]。
-阅读素数资料时，还应区分“已知最大素数”与“最大的素数”。前者是随着计算记录变化的有限知识状态，后者由无限性定理可知根本不存在。本条不把某一次计算纪录放进概念定义，以免把数学结论与不断更新的实验边界混同；具体纪录需要注明日期和可复核的证明资料。
+无限多也允许相邻素数之间出现很长的空档。给定正整数 m，取 <math>N=(m+1)!</math>，这里的阶乘表示从 1 到 m+1 的整数连乘。于是
+<math display="block">N+2,\ N+3,\ \ldots,\ N+m+1</math>
+分别被 2、3、……、m+1 整除，而且每项都大于相应因数。这就构成连续 m 个合数。m 可以任意大，故合数连续出现的长度没有固定上界。
-== English overview ==
+== 从素性检验到整体分布 ==
-<div lang="en" class="math-english-summary">
+试除和筛法提供确定的因子检验；有些更快的检验则利用同余性质。费马小定理说，若 p 为素数且 p 不整除 a，则
-A prime is an integer greater than one with exactly two positive divisors: one and itself. One is excluded because it is a multiplicative unit, not a genuine building block of factorization. Every integer greater than one factors into primes, uniquely up to the order of the factors.
+<math display="block">a^{p-1}\equiv1\pmod p.</math>
+同余符号表示两边除以 p 有相同余数。若某个整数不满足相应等式，就可以排除它是素数；满足等式，却还可能是合数。
-Trial division needs only prime candidates up to the square root. A sieve efficiently lists all primes within a bounded interval, whereas testing one large integer is a different computational task. The fundamental theorem of arithmetic requires separate proofs of existence and uniqueness; Euclid's lemma supplies the key step for uniqueness.
+例如 <math>341=11\cdot31</math>，而 <math>2^{10}=1024=3\cdot341+1</math>。连续相乘可得 <math>2^{340}=(2^{10})^{34}\equiv1\pmod{341}</math>。341 因而通过了底数 2 的这项检验。费马小定理给出素数应有的性质，这个例子说明该性质本身还不足以反推素性。
-Euclid's infinitude argument produces a prime outside any finite list. It does not claim that the product of listed primes plus one is always prime. Prime gaps can nevertheless be arbitrarily long. Primality testing, finding factors, and estimating prime density are distinct questions. The prime number theorem describes asymptotic counting, not an exact local probability. Worked examples illustrate factorization, divisor counts, greatest common divisors, and a composite number that passes a basic Fermat test.
+另一个研究方向是不再逐个判定，而是统计素数有多少。记 <math>\pi(x)</math> 为不超过 x 的素数个数，例如上面的筛选得到 <math>\pi(50)=15</math>。'''素数定理'''指出
-</div>
+<math display="block">\lim_{x\to\infty}\frac{\pi(x)}{x/\log x}=1,</math>
+其中 <math>\log</math> 为自然对数。它说明 <math>x/\log x</math> 给出了大范围计数的相对近似，不是每个 x 处的精确等式。证明需要进一步的分析方法。
-== 编者评注（AI 辅助） ==
+Hadamard 与 de la Vallée Poussin 在 1896 年分别证明了素数定理。[https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/ MacTutor 素数史]记录了从古代无限性和筛法，到近代整体分布研究的发展。素数虽然没有固定的等距排列，却具有唯一分解、可检验的整除规律，以及可精确表述的分布定理。
-本条围绕分类边界与唯一分解组织内容，先解释一为何排除，再区分分解存在性和唯一性。无穷性证明中特别给出“乘积加一仍可能合成”的反例，避免把证明改造成错误公式。内容由 AI 辅助整理；编者不以“毫无规律”概括素数，因为算法、代数结构与渐近计数各有明确规律。超出本条的素数定理只陈述范围，没有以简短直觉冒充完整证明。
-== 参考资料与后续阅读 ==
+== 参考资料 ==
-* [https://math.gordon.edu/ntic/ntic/ntic.html Karl-Dieter Crisman，Number Theory: In Context and Interactive]：素数、筛法、分解与分布的开放教材。
+* [https://math.gordon.edu/ntic/ntic/ntic.html Karl-Dieter Crisman，Number Theory: In Context and Interactive]：素数、筛法、分解与分布。
-* [https://math.gordon.edu/ntic/ntic/section-inf-primes.html 同书，To Infinity and Beyond]：素数无限性的讨论。
+* [https://math.gordon.edu/ntic/ntic/section-inf-primes.html 同书，To Infinity and Beyond]。
-* [https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html Euclid，Elements，IX.20，David Joyce 编注]：超出任意有限素数清单的原始论证。
+* [https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html Euclid，Elements，IX.20，David Joyce 编注]。
-* [https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/ J. J. O’Connor、E. F. Robertson，Prime numbers]：筛法与素数定理等历史节点。
+* [https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/ J. J. O’Connor、E. F. Robertson，Prime numbers]。
-* 前置可读[[整数整除]]；继续阅读[[同余]]、[[群]]和[[逻辑]]。
+* 相关条目：[[整数整除]]、[[同余]]、[[逻辑]]。
 [[分类:数论]]