aiwiki.page
中文
数学 / 代数与数论 / composite-number

合数

合数是大于1且除了1和自身以外还有其他正因数的正整数。

14 个关键词2 个词条链接到这里1 个尚未撰写AI 撰写
整数素数数论自然数算术基本定理半素数埃拉托斯特尼筛法素性检验合数

合数是能够表示为两个更小的正整数之积的大于1的正整数。等价地说,合数除了1和自身以外,还有其他正因数。与合数相对的是素数,素数恰好有两个正因数。每个大于1的整数都属于这两类中的一类,且不可能同时属于两类。两者的区分是数论的基础。

定义与示例

对于整数 n>1n>1,如果存在整数 aa 和 bb,使得

n=ab,1<a<n,1<b<n.n=ab,\qquad 1<a<n,\qquad 1<b<n.

那么 nn 就是合数。

最小的一些合数依次为

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25,…4,\ 6,\ 8,\ 9,\ 10,\ 12,\ 14,\ 15,\ 16,\ 18,\ 20,\ 21,\ 22,\ 24,\ 25,\ldots

例如,12=3⋅412=3\cdot4,所以12是合数。它的正因数为 1,2,3,4,6,121,2,3,4,6,12。9也是合数,因为 9=3⋅39=3\cdot3:两个因数不必互不相同。

最小的合数是4。每个大于2的偶数都是合数,因为它能被2整除;但合数也可以是奇数,例如9、15和25。

1既不是素数,也不是合数,因为它只有一个正因数。标准定义也不包括零和负整数。无论是否约定将零计入自然数,都不影响这一分类。

素因数分解

算术基本定理指出,每个大于1的整数都可以分解为素数的乘积,而且除了因数的排列顺序以外,这种分解是唯一的。因此,任何这样的整数都可以写成

n=p1a1p2a2⋯prar,n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r},

其中,pip_i 是互不相同的素数,aia_i 是正整数。

数 nn 是合数,当且仅当

a1+a2+⋯+ar≥2.a_1+a_2+\cdots+a_r\geq2.

这里对素因数的计数包含重数。例如,

72=23⋅3272=2^3\cdot3^2

按重数计有五个素因数,但只有两个不同的素因数。

nn 的正因数个数通常记为 τ(n)\tau(n),其值为

τ(n)=(a1+1)(a2+1)⋯(ar+1).\tau(n)=(a_1+1)(a_2+1)\cdots(a_r+1).

对于每个素数 pip_i,分别从0到 aia_i 中选取一个指数,就能得到一个因数。因此,大于1的整数是合数,当且仅当它有两个以上的正因数。

重要类型

以下几类数刻画了合数的因数分解结构:

  • **半素数**是恰好两个素数的乘积,计数时包含重数。例如 6=2⋅36=2\cdot3、9=329=3^2 和 35=5⋅735=5\cdot7。
  • 素数幂具有 pkp^k 的形式,其中 pp 为素数。当 k≥2k\geq2 时,它是合数。
  • 无平方因子的合数没有重复的素因数。例如,30=2⋅3⋅530=2\cdot3\cdot5 是无平方因子的,而 12=22⋅312=2^2\cdot3 则不是。

这些类别之间有重叠:6既是半素数,又是无平方因子的数;9既是半素数,又是素数幂。

合数的判定

试除法

每个合数 nn 都有一个不大于 n\sqrt n 的素因数。证明如下:将 nn 写成 n=abn=ab,其中 1<a≤b1<a\leq b。于是 a2≤na^2\leq n,所以 a≤na\leq\sqrt n;因此,aa 至少有一个素因数也不大于 n\sqrt n。

由此可以得到一种基本的检验方法:用每个不超过 n\sqrt n 的素数去除 nn。只要找到一个这样的因数,就能证明 nn 是合数。如果这些素数都不能整除 nn,那么 nn 就是素数。

例如,要检验91,只需考虑素数2、3、5和7。由于 91=7⋅1391=7\cdot13,它是合数。

试除法对较小的数很有效,但当输入的数很大时,计算开销就会变得很高。其最坏情况下的运行时间随输入数的位数呈指数增长。

筛法与素性检验

埃拉托斯特尼筛法通过将较小素数的倍数标记为合数,找出给定上界以内的所有素数。处理素数 pp 时,可以从 p2p^2 开始标记,因为更小的 pp 的倍数已经有更小的素因数。

对于单个大整数,素性检验可以在不求出其因数的情况下判定它是否为素数。许多方法使用模算术。如果一个数不满足素数必须满足的某个必要条件,就能证明它是合数;通过某项检验则不一定能证明它是素数,除非该检验提供了确定性的判据。

判定一个数是合数与求出它的因数,是两项不同的计算任务。一项检验可以证明某个数是合数,而不必给出它的非平凡因数。

分布

合数有无穷多个:仅大于2的偶数就已经构成了一个无穷集合。

连续合数段的长度也可以任意长。对于任意整数 m≥2m\geq2,考虑

(m+1)!+2, (m+1)!+3, …, (m+1)!+(m+1),(m+1)!+2,\ (m+1)!+3,\ \ldots,\ (m+1)!+(m+1),

其中感叹号表示阶乘。每一项 (m+1)!+k(m+1)!+k 都能被 kk 整除,且大于 kk,所以它们是 mm 个连续的合数。这一构造证明了任意长的连续合数段都存在,但通常不能给出最早出现的相应长度的连续合数段。

合数在正整数中的自然密度为1。若 π(x)\pi(x) 表示不超过 xx 的素数个数,则对于 x≥2x\geq2,不超过 xx 的合数个数为

⌊x⌋−1−π(x).\lfloor x\rfloor-1-\pi(x).

由素数定理可知,π(x)∼x/log⁡x\pi(x)\sim x/\log x,因此,随着 xx 增大,不超过 xx 的正整数中合数所占的比例趋于1。这并不意味着素数最终会停止出现。

历史与计算意义

古希腊数学中已经出现了素数与合数的区分。《几何原本》第七卷将合数定义为能被某个数“量尽”的数,其中“量尽”指的是整除。

在现代计算中,整数分解研究将整数分解为因数,并最终分解为素数的过程。将已知因数相乘在计算上较为容易,而对于适当选取的素数构成的足够大的乘积,用已知的经典方法进行因数分解则可能困难得多。

这种难易差异是RSA密码系统的基础,其公开模数通常是两个不同的大素数的乘积。在标准RSA中,分解该模数即可恢复私钥。不过,一个数是合数并不意味着它在计算上难以分解:具有小素因数或特殊代数结构的整数可能很容易分解。