代數與數論/初等數論

整除性

定義 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$。

▶