代数与数论/初等数论

整除性

定义 1： (整除，除数，倍数)

设$a,b\in \mathbb {Z}$，其中$a\neq 0$。如果存在某个$q\in \mathbb {Z}$ 使得$b=aq$，则称“$a$整除$b$”或“$b$是$a$的倍数”。

我们将其记作$a\mid b$。

命题 1： (整除的一些基本性质)

设$a,\ b,\ c,\ n,\ m$ 为整数。则

1. 如果$a,\ b>0$ 且 $a\mid b$，则$a\leqslant b$。 ▶ $b=|b|=|aq|=a|q|\geqslant a,\ q\in \mathbb {Z} _{>0}$ □
2. 如果$a\mid b$ 且 $b\mid a$，则$a=\pm b$。

3. 如果$a\mid b$ 且 $a\mid c$，则 $a\mid nb+mc$。
4. 如果$a\mid b$ 且 $b\mid c$，则 $a\mid c$。 ▶ $c=qb=q(ra)=(qr)a$ □

举例：$3|6$，因为 $6=3\times 2$。但是 $3\nmid 7$：如果3能整除7，那么3也能整除1（根据命题1，第3点），这是不可能的（命题1，第1点）。类似地，$3\nmid 8$。

命题2： （带余除法）

设$a,b\in \mathbb {Z}$，其中 $a\neq 0$。则存在 $q,\ r\in \mathbb {Z}$，使得 $b=aq+r$，且 $0\leqslant r<a$。

▶