整除性

整除与带余除法是初等数论的起点，因数、素数、同余等概念都建立在整除之上。

定义

设 $a,b$ 为整数且 $a\neq 0$。若存在整数 $q$ 使得 $b = aq$，则称 $a$ 整除 $b$，记作 $a\mid b$；此时 $a$ 称为 $b$ 的因数（约数），$b$ 称为 $a$ 的倍数。若不存在这样的整数 $q$，则称 $a$ 不整除 $b$，记作 $a\nmid b$。

任何非零整数 $a$ 都有因数 $\pm 1$ 与 $\pm a$；$0$ 是任何非零整数的倍数。

带余除法

对任意整数 $a$ 与正整数 $b$，存在唯一的一对整数 $q,r$，使得

$$a = bq + r, \qquad 0 \le r < b$$

其中 $q$ 称为商，$r$ 称为余数。带余除法是辗转相除法与同余理论的基础。

性质

设 $a,b,c$ 均为整数，$a\neq 0$：

• $a\mid b$ 且 $a\mid c \Rightarrow a\mid (b\pm c)$
• $a\mid b \Rightarrow a\mid bc$（对任意整数 $c$）
• $a\mid b$ 且 $b\mid c \Rightarrow a\mid c$（传递性）
• $a\mid b$ 且 $b\mid a \Rightarrow a = \pm b$
• 若 $b\neq 0$ 且 $a\mid b$，则 $|a|\le |b|$

示例

• $3\mid 12$，因为 $12 = 3\cdot 4$；$4\nmid 17$
• $17 = 3\cdot 5 + 2$：商 $q = 5$，余数 $r = 2$
• 偶数是 $2$ 的倍数：$2\mid n \iff n = 2k\ (k\in\mathbb{Z})$