整除

定义 1　整除

　　 假设对于整数 $a$ 与非 $0$ 整数 $b$，存在第 $3$ 个整数 $c$ 使得

就称 $a$ 能被 $b$ 整除（divisible）。记作 $b|a$，称 $b$ 是 $a$ 的一个因子（divisor）。

推论 1　整除的性质

　　 对于整数 $a$ 与非零整数 $b$，显然有：

• $1|a$；
• $b|0$，$b|b$。

定理 1　整除的传递性

　　 若 $b|a$，$c|b$，则 $c|a$。

定理 2　

　　 若 $b|a$，则对于非零整数 $c\ne 0$ 有 $(bc)|(ac)$。

定理 3　

　　 若 $c|a$ 并且 $c|b$，则对于任意整数 $m$ 与 $n$ 都有 $c|(ma+nb)$。

定义 2　

　　 符号 $a\mathrm{mod}b$ 表示 $a$ 除以 $b$ 的余数。这是指若 $r=a\mathrm{mod}b$，则 $a=kb+r$，且 $k$ 为整数并且 $0\le r<b$。