整除
贡献者： int256
定义 1 整除
假设对于整数 $a$ 与非 $0$ 整数 $b$，存在第 $3$ 个整数 $c$ 使得
\begin{equation}
a = bc ~,
\end{equation}
就称 $a$ 能被 $b$
整除（divisible）。记作 $b | a$，称 $b$ 是 $a$ 的一个
因子（divisor）。
有时也用记号 $\nmid$、$\not{\mid}$ 表示不整除，也就是做除法会有余数，例如 $2 \not{\mid}~ 5 $。
推论 1 整除的性质
对于整数 $a$ 与非零整数 $b$，显然有：
- $1 | a$；
- $b | 0$，$b | b$。
另外整除还有传递性等性质。
定理 1 整除的传递性
若 $b|a$，$c|b$，则 $c|a$。
定理 2
若 $b|a$，则对于非零整数 $c \neq 0$ 有 $(bc) | (ac)$。
定理 3
若 $c|a$ 并且 $c|b$，则对于任意整数 $m$ 与 $n$ 都有 $c | (ma + nb)$。
定义 2
符号 $a \operatorname {mod} b$ 表示 $a$ 除以 $b$ 的余数。这是指若 $r = a \operatorname {mod} b$，则 $a = kb + r$，且 $k$ 为整数并且 $0 \le r < b$。