合数
hé shù
合数是大于1的整数，拥有两个以上的因数，即除了1和它本身外还能被其他数整除。
Definition
合数是大于 $1$ 且除了 $1$ 和它本身之外，还能被至少一个其他数整除的正整数，也就是说它拥有两个以上的因数。等价地说，大于 $1$ 的合数 $n$ 可以写成两个都大于 $1$ 的整数的乘积，且至少存在一个满足 $1 < d < n$ 的因数 $d$；任意合数 $n$ 的最小质因数不超过 $\sqrt{n}$。更一般地，在环论中，合成元素是指可约元素，即能表示为两个既非单位又非零的元素之乘积；质元素与不可约元素之间的区别（二者在唯一分解整环中重合，但在一般环中不然）是代数数论的核心内容。
Example
$12$ 是合数，因为它可以被 $1$、$2$、$3$、$4$、$6$、$12$ 整除，共六个因数。要检验 $97$ 是否为质数，只需检查不超过 $\sqrt{97} \approx 9.8$ 的质数（即 $2, 3, 5, 7$）：没有一个能整除它，所以 $97$ 是质数；而 $91 = 7 \times 13$ 则是合数。卡迈克尔数，如 $561 = 3 \times 11 \times 17$，是能够通过费马素性检验（对所有与其互质的底数）的合数，这说明仅凭费马检验不足以证明素性。
Key Insight
若一个大于 $1$ 的数不是质数，它就是合数，而每个合数都可以分解成若干质数。只需检查到 $\sqrt{n}$ 这一事实，使得埃拉托斯特尼筛法和试除法对中等大小的数都相当高效。密码学中使用的大多数素性检验（如 Miller-Rabin 检验）都是概率性的而非确定性的，因为确定性的素性证明速度更慢；AKS 算法（2002年）是第一个多项式时间的确定性素性检验算法。