整除

概述

整除（Divisibility）是数论中最基本的关系：整数 $a$ 整除整数 $b$（记作 $a\mid b$），当且仅当 $b$ 是 $a$ 的整数倍。整除关系是数论算法（如最大公约数、素数分解、模运算）的基础概念。

定义

形式化定义

设 $a,b\in \mathbb{Z}$，$a\ne 0$。称 $a$ 整除 $b$（$a$ divides $b$），记作 $a\mid b$，当且仅当存在整数 $k\in \mathbb{Z}$ 使得： $b=ka$

此时也称：

• $a$ 是 $b$ 的因数（divisor / factor）
• $b$ 是 $a$ 的倍数（multiple）

若 $a$ 不整除 $b$，记作 $a\nmid b$。

基本性质

核心性质

设 $a,b,c\in \mathbb{Z}$，$a\ne 0$：

1. 自反性（部分）：$a\mid a$（取 $k=1$）
2. 传递性：若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$
   • 证明：$b=k_{1}a$，$c=k_{2}b=k_2{k}_{1}a$，故 $a\mid c$
3. 线性组合封闭性：若 $a\mid b$ 且 $a\mid c$，则对任意 $x,y\in \mathbb{Z}$，$a\mid (xb+yc)$
   • 证明：$b=k_{1}a$，$c=k_{2}a$，故 $xb+yc=(x{k}_1+y{k}_2)a$
4. 大小关系：若 $a\mid b$ 且 $b\ne 0$，则 $|a|\le |b|$
5. 平凡因数：$\pm 1$ 整除任何整数；任何非零整数整除 $0$

特殊整除规则

• 整除判别法：
  • $2\mid b$：$b$ 的末位为偶数
  • $3\mid b$：$b$ 的各位数字之和被 3 整除
  • $4\mid b$：$b$ 的末两位组成的数被 4 整除
  • $5\mid b$：$b$ 的末位为 0 或 5
  • $9\mid b$：$b$ 的各位数字之和被 9 整除
  • $11\mid b$：$b$ 的奇数位数字之和与偶数位数字之和的差被 11 整除

与其他数论概念的关系

最大公约数（GCD）

$\gcd (a,b)=\max \{d\in {\mathbb{Z}}^{+}\mid d\mid a\text{ 且 }d\mid b\}$

• 欧几里得算法：$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$，时间复杂度 $O(\log (\min (a,b)))$
• Bézout 定理：$\gcd (a,b)=d$ 当且仅当存在整数 $x,y$ 使得 $ax+by=d$

素数与唯一分解定理

算术基本定理

每个大于 1 的正整数都可以唯一地表示为素数的乘积（不计顺序）： $n=p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k}$

模运算

整除关系与模运算直接相关：$a\mid b$ 当且仅当 $b\equiv 0(\mathrm{mod}a)$。

应用场景

• 最大公约数：欧几里得算法是算法导论中数论算法的基础
• 素数分解：试除法、Pollard’s rho 算法等均基于整除性判断
• 模运算：RSA 公钥密码学、哈希函数等依赖模运算，而模运算以整除为基础
• 线性丢番图方程：$ax+by=c$ 有整数解当且仅当 $\gcd (a,b)\mid c$

参见

• 公钥密码学