合数是能够表示为两个更小的正整数之积的大于1的正整数。等价地说,合数除了1和自身以外,还有其他正因数。与合数相对的是素数,素数恰好有两个正因数。每个大于1的整数都属于这两类中的一类,且不可能同时属于两类。两者的区分是数论的基础。
定义与示例
对于整数 ,如果存在整数 和 ,使得
那么 就是合数。
最小的一些合数依次为
例如,,所以12是合数。它的正因数为 。9也是合数,因为 :两个因数不必互不相同。
最小的合数是4。每个大于2的偶数都是合数,因为它能被2整除;但合数也可以是奇数,例如9、15和25。
1既不是素数,也不是合数,因为它只有一个正因数。标准定义也不包括零和负整数。无论是否约定将零计入自然数,都不影响这一分类。
素因数分解
算术基本定理指出,每个大于1的整数都可以分解为素数的乘积,而且除了因数的排列顺序以外,这种分解是唯一的。因此,任何这样的整数都可以写成
其中, 是互不相同的素数, 是正整数。
数 是合数,当且仅当
这里对素因数的计数包含重数。例如,
按重数计有五个素因数,但只有两个不同的素因数。
的正因数个数通常记为 ,其值为
对于每个素数 ,分别从0到 中选取一个指数,就能得到一个因数。因此,大于1的整数是合数,当且仅当它有两个以上的正因数。
重要类型
以下几类数刻画了合数的因数分解结构:
- **半素数**是恰好两个素数的乘积,计数时包含重数。例如 、 和 。
- 素数幂具有 的形式,其中 为素数。当 时,它是合数。
- 无平方因子的合数没有重复的素因数。例如, 是无平方因子的,而 则不是。
这些类别之间有重叠:6既是半素数,又是无平方因子的数;9既是半素数,又是素数幂。
合数的判定
试除法
每个合数 都有一个不大于 的素因数。证明如下:将 写成 ,其中 。于是 ,所以 ;因此, 至少有一个素因数也不大于 。
由此可以得到一种基本的检验方法:用每个不超过 的素数去除 。只要找到一个这样的因数,就能证明 是合数。如果这些素数都不能整除 ,那么 就是素数。
例如,要检验91,只需考虑素数2、3、5和7。由于 ,它是合数。
试除法对较小的数很有效,但当输入的数很大时,计算开销就会变得很高。其最坏情况下的运行时间随输入数的位数呈指数增长。
筛法与素性检验
埃拉托斯特尼筛法通过将较小素数的倍数标记为合数,找出给定上界以内的所有素数。处理素数 时,可以从 开始标记,因为更小的 的倍数已经有更小的素因数。
对于单个大整数,素性检验可以在不求出其因数的情况下判定它是否为素数。许多方法使用模算术。如果一个数不满足素数必须满足的某个必要条件,就能证明它是合数;通过某项检验则不一定能证明它是素数,除非该检验提供了确定性的判据。
判定一个数是合数与求出它的因数,是两项不同的计算任务。一项检验可以证明某个数是合数,而不必给出它的非平凡因数。
分布
合数有无穷多个:仅大于2的偶数就已经构成了一个无穷集合。
连续合数段的长度也可以任意长。对于任意整数 ,考虑
其中感叹号表示阶乘。每一项 都能被 整除,且大于 ,所以它们是 个连续的合数。这一构造证明了任意长的连续合数段都存在,但通常不能给出最早出现的相应长度的连续合数段。
合数在正整数中的自然密度为1。若 表示不超过 的素数个数,则对于 ,不超过 的合数个数为
由素数定理可知,,因此,随着 增大,不超过 的正整数中合数所占的比例趋于1。这并不意味着素数最终会停止出现。
历史与计算意义
古希腊数学中已经出现了素数与合数的区分。《几何原本》第七卷将合数定义为能被某个数“量尽”的数,其中“量尽”指的是整除。
在现代计算中,整数分解研究将整数分解为因数,并最终分解为素数的过程。将已知因数相乘在计算上较为容易,而对于适当选取的素数构成的足够大的乘积,用已知的经典方法进行因数分解则可能困难得多。
这种难易差异是RSA密码系统的基础,其公开模数通常是两个不同的大素数的乘积。在标准RSA中,分解该模数即可恢复私钥。不过,一个数是合数并不意味着它在计算上难以分解:具有小素因数或特殊代数结构的整数可能很容易分解。