整数的可除性

带余除法

整数集对加法、减法、乘法都封闭，但对除法却不封闭，为了谈论整数的除法（这样的好处我们后面会看到），我们引入「带余除法」。

定理-定义 1 (带余除法)

对任意 $𝑎, 𝑏 \in ℤ$ ，若 $𝑏 \neq 0$ ，则存在唯一的 $𝑞, 𝑟 \in ℤ$ 使得

𝑎 = 𝑏 𝑞 + 𝑟, 其中 0 \leq 𝑟 < | 𝑏 | .

这样的 $𝑞$ 称为 $𝑎$ 除以 $𝑏$ 的「商」（quotient）， $𝑟$ 称为 $𝑎$ 除以 $𝑏$ 的「余数」（remainder）。

定理-定义 1: 带余除法

注记 2 (除数不为零)

要求除数 $𝑏$ 不为零是我们一直习惯的做法，事实上如果考虑 $𝑏 = 0$ ，那么该定理是显然不成立的，也就更不存在「一个数除以 0 的商和余数」的说法了。
- 被除数 $𝑎$ 为零是没问题的。
除了这里广义上的除法（带余除法）要求除数不为零以外，狭义上的除法同样要求除数不为零，具体的原因见 B 站刘思齐《抽象代数》第一讲。
我们约定记号 $ℤ^{*} ≔ ℤ \ {0}$ 表示非零整数集。

注记 2: 除数不为零

证明 3 (非正式)

带余除法我们从小学就在用了，我没记错的话，当时的写法是类似这样的：

13 \div 3 = 4 \dots \dots 1 .

所以这其实是我们很熟悉的内容，只不过现在我们把它严谨地表达出来而已。然而，作为数论最基础的定理，其严谨证明依赖公理集合论，所以这里我们选择相信并接受就行了。

证明 3: 非正式

整除

下面考虑一种特殊的带余除法——整除，即余数为零的除法。

定义 4 (整除)

设 $𝑎, 𝑏 \in ℤ$ ：

若 $𝑏 \neq 0$ 且 $𝑎$ 除以 $𝑏$ 的余数为 $0$ （即存在 $𝑞 \in ℤ$ 使得 $𝑎 = 𝑏 𝑞$ ），则称「 $𝑏$ 整除 $𝑎$ 」，或说「 $𝑎$ 被 $𝑏$ 整除」，记作 $𝑏 ∣ 𝑎$ 。此时 $𝑏$ 叫做 $𝑎$ 的因数， $𝑎$ 叫做 $𝑏$ 的倍数。
若 $𝑏 \neq 0$ 且 $𝑎$ 除以 $𝑏$ 的余数不为 $0$ （即不存在 $𝑞 \in ℤ$ 使得 $𝑎 = 𝑏 𝑞$ ），则称「 $𝑏$ 不能整除 $𝑎$ 」，或说「 $𝑎$ 不能被 $𝑏$ 整除」，记作 $𝑏 ∤ 𝑎$ 。

定义 4: 整除

注记 5

若 $𝑎 = 𝑏 𝑞$ ，那么由交换律， $𝑏$ 和 $𝑞$ 都是 $𝑎$ 的因数。
但凡是谈论带余除法就需要除数非零这个前提，所以只要我们写出 $𝑏 ∣ 𝑎$ 或者 $𝑏 ∤ 𝑎$ 那么就代表 $𝑎, 𝑏 \in ℤ$ 且满足 $𝑏 \neq 0$ （不过我们在做证明的时候通常不会显式地写出这一点）。换言之， $∣$ 和 $∤$ 作为整数集上的两个二元关系，它们作为集合，天然排除形如 $⟨ 0, 𝑥 ⟩$ 的元素。
所有非零整数都是 $0$ 的因数，因为对于任意 $𝑥 \in ℤ^{*}$ ，都有 $0 = 𝑥 \cdot 0$ 。
对于任意非零整数 $𝑎$ ，它的因数包括 $\pm 1$ 和 $\pm 𝑎$ 。这是因为 $𝑎 = 1 \cdot 𝑎$ 以及 $𝑎 = (- 1) (- 𝑎)$ 。这四个因数称为 $𝑎$ 的「平凡因数」。
- 对于任意整数 $𝑎$ ，它的因数都包含 $\pm 1$ 。

定义 6 (奇数偶数)

对于任意 $𝑥 \in ℤ$ ：

若 $2 ∣ 𝑥$ ，即存在 $𝑞 \in ℤ$ 使得 $𝑥 = 2 𝑞$ ，则称 $𝑥$ 为偶数；
否则（即 $2 ∤ 𝑥$ ）称 $𝑥$ 为奇数。

定义 6: 奇数偶数

注记 7

若 $𝑥 \in ℤ$ 为奇数，即 $2 ∤ 𝑥$ ，那么考虑 $𝑥$ 除以 $2$ 的带余除法：

𝑥 = 2 𝑞_{0} + 𝑟_{0},

其中 $𝑞_{0}$ 是商， $𝑟_{0}$ 是余数。根据带余除法的定义有 $0 \leq 𝑟_{0} < 2$ ，由于 $2 ∤ 𝑥$ ，所以 $𝑟_{0} \neq 0$ ，所以 $𝑟_{0} = 1$ 。

所以， $𝑥 \in ℤ$ 是奇数等价于存在 $𝑞 \in ℤ$ 使得 $𝑥 = 2 𝑞 + 1$ 。

例 8

设 $𝑛$ 为整数，证明 $𝑛^{2}$ 除以 $4$ 的余数为 $0$ 或 $1$ 。

证明 9

若 $𝑛$ 为奇数，则存在 $𝑘 \in ℤ$ 使得 $𝑛 = 2 𝑘 + 1$ ，此时 $𝑛^{2} = {(2 𝑘 + 1)}^{2} = 4 (𝑘^{2} + 𝑘) + 1$ ，按带余除法的定义，则 $𝑛^{2}$ 除以 4 的余数为 1。
若 $𝑛$ 为偶数，则存在 $𝑞 \in ℤ$ 使得 $𝑛 = 2 𝑞$ ，此时 $𝑛^{2} = 4 𝑞^{2}$ ，按带余除法的定义，则 $𝑛^{2}$ 除以 4 的余数为 0。

定理 10 (整除作为关系的性质)

整数集上的整除关系具有如下性质：

自反性：对任意 $𝑎 \in ℤ^{*}$ 有 $𝑎 ∣ 𝑎$ ；
拟反对称性：对任意 $𝑎, 𝑏 \in ℤ$ 有 $𝑎 ∣ 𝑏 \land 𝑏 ∣ 𝑎 ⟹ 𝑎 = \pm 𝑏$ ；
传递性：对任意 $𝑎, 𝑏, 𝑐 \in ℤ$ 有 $𝑎 ∣ 𝑏 \land 𝑏 ∣ 𝑐 ⟹ 𝑎 ∣ 𝑐$ 。

定理 10: 整除作为关系的性质

注记 11

这个定理考察的是整除作为整数集上的一个关系的性质，可以看到，整除关系似乎是一个偏序关系，但注意其中的「拟反对称性」与「反对称性」是不同的，如果要满足反对称性的话，需要满足：对任意 $𝑎, 𝑏 \in ℤ$ 有 $𝑎 ∣ 𝑏 \land 𝑏 ∣ 𝑎 ⟹ 𝑎 = 𝑏$ 。此外，自反性也不是严格满足的，在 $𝑎 = 0$ 时没有自反性。所以整数集上的整除关系并不是偏序关系，但如果考虑正整数集上的整除关系，那就是偏序关系了。

这样看来，如果我们只考虑正整数集上的整除关系，这似乎会是更简洁的理论，但我们后面会看到，我们希望我们的集合是一个对减法封闭的集合，也就是希望它是一个环，这样会带给我们很多很好的性质，所以在此处牺牲一点整除关系的简洁性是值得的。

证明 12

自反性：对任意 $𝑎 \in ℤ^{*}$ ，由于 $𝑎 = 1 \cdot 𝑎$ ，所以 $𝑎 ∣ 𝑎$ 。
拟反对称性：任意 $𝑎, 𝑏 \in ℤ$ ，若 $𝑎 ∣ 𝑏$ 并且 $𝑏 ∣ 𝑎$ ，那么存在 $𝑝, 𝑞 \in ℤ$ 使得 $𝑎 = 𝑏 𝑝$ 以及 $𝑏 = 𝑎 𝑞$ ，将后者代入前者得到 $𝑎 = 𝑎 𝑞 𝑝$ ，由于 $𝑎 ∣ 𝑏$ 要求 $𝑎 \neq 0$ ，所以 $𝑝 𝑞 = 1$ ，那么 $𝑝 = 1 \land 𝑞 = 1$ 或者 $𝑝 = - 1 \land 𝑞 = - 1$ ，所以 $𝑎 = 𝑏$ 或者 $𝑎 = - 𝑏$ ，即 $𝑎 = \pm 𝑏$ ；
传递性：对任意 $𝑎, 𝑏, 𝑐 \in ℤ$ ，若 $𝑎 ∣ 𝑏 \land 𝑏 ∣ 𝑐$ ，那么存在 $𝑝, 𝑞 \in ℤ$ 使得 $𝑎 = 𝑏 𝑝$ 以及 $𝑏 = 𝑐 𝑞$ ，将后者代入前者得到 $𝑎 = 𝑐 (𝑞 𝑝)$ ，按整除的定义有 $𝑎 ∣ 𝑐$ 。

命题 13 (整除与正负号)

对于 $𝑎, 𝑏 \in ℤ$ ，有

𝑏 ∣ 𝑎 ⟺ (- 𝑏) ∣ 𝑎 ⟺ 𝑏 ∣ (- 𝑎) ⟺ (- 𝑏) ∣ (- 𝑎) .

命题 13: 整除与正负号

证明 14

显然。按整除的定义即可验证。

例 15

3 ∣ 12 ⟺ (- 3) ∣ 12 ⟺ 3 ∣ (- 12) ⟺ (- 3) ∣ (- 12) .

下面我们给出两个命题，它可以帮助我们基于一些简单的整除式得出更复杂的整除式。

命题 16

考虑 $𝑥, 𝑦_{1}, 𝑦_{2} \in ℤ$ ，设 $𝑥 ∣ 𝑦_{1}$ 且 $𝑥 ∣ 𝑦_{2}$ ，则对于任意 $𝑎_{1}, 𝑎_{2} \in ℤ$ 有 $𝑥 ∣ (𝑎_{1} 𝑦_{1} + 𝑎_{2} 𝑦_{2})$ 。

换言之，若 $𝑥$ 能整除 $𝑦_{1}$ 和 $𝑦_{2}$ ，那么 $𝑥$ 也能整除 $𝑦_{1}$ 和 $𝑦_{2}$ 的线性组合。

例 17

我们知道 $3 ∣ 9$ 和 $3 ∣ 6$ ，那么就有 $3 ∣ (4 \cdot 9 + 2 \cdot 6)$ 和 $3 ∣ (5 \cdot 9 - 2 \cdot 6)$ ，即 $3 ∣ 48$ 以及 $3 ∣ 33$ 。

证明 18

由于 $𝑥 ∣ 𝑦_{1}$ 并且 $𝑥 ∣ 𝑦_{2}$ ，所以按定义存在 $𝑞_{1}, 𝑞_{2} \in ℤ$ 使得

𝑦_{1} = 𝑞_{1} 𝑥, 𝑦_{2} = 𝑞_{2} 𝑥,

那么

𝑎_{1} 𝑦_{1} + 𝑎_{2} 𝑦_{2} = 𝑎_{1} 𝑞_{1} 𝑥 + 𝑎_{2} 𝑞_{2} 𝑥 = (𝑎_{1} 𝑞_{1} + 𝑎_{2} 𝑞_{2}) 𝑥,

所以按定义有 $𝑥 ∣ (𝑎_{1} 𝑦_{1} + 𝑎_{2} 𝑦_{2})$ 。

注记 19

显然这个命题可以推广为

𝑥 ∣ 𝑦_{1}, \dots, 𝑥 ∣ 𝑦_{𝑛} ⟹ 𝑥 ∣ (𝑎_{1} 𝑦_{1} + \dots + 𝑎_{𝑛} 𝑦_{𝑛}),

不过意义不大，这个推广是显然的，我们只需要多次应用上面的命题即可。

命题 20

考虑 $𝑥, 𝑦, 𝑎 \in ℤ$ ，设 $𝑎 \neq 0$ ，则有 $𝑥 ∣ 𝑦 ⟺ 𝑎 𝑥 ∣ 𝑎 𝑦$ 。

证明 21

对于 $𝑥, 𝑦 \in ℤ$ ， $𝑥 ∣ 𝑦$ 等价于存在 $𝑞 \in ℤ$ 使得 $𝑦 = 𝑞 𝑥$ ，那么由于 $𝑎 \neq 0$ ，所以这等价于 $𝑎 𝑦 = 𝑞 (𝑎 𝑥)$ ，所以这等价于 $𝑎 𝑥 ∣ 𝑎 𝑦$ 。

命题 22 (非零整数不会小于它自己的因子)

考虑 $𝑥, 𝑦 \in ℤ$ ，若 $𝑦 \neq 0$ ，那么 $𝑥 ∣ 𝑦 ⟹ | 𝑥 | \leq | 𝑦 |$ 。

命题 22: 非零整数不会小于它自己的因子

注记 23

这个命题建立了整除关系与我们熟悉的整数集上的 $\leq$ 序关系之间的联系，符合我们的直觉：一个非零整数不会小于它自己的因子。

证明 24

由于 $𝑥 ∣ 𝑦$ ，那么 $𝑥 \neq 0$ 并且存在 $𝑞 \in ℤ$ 使得 $𝑦 = 𝑞 𝑥$ ，那么就有 $| 𝑦 | = | 𝑞 | \cdot | 𝑥 |$ 。又因为 $𝑦 \neq 0$ ，所以 $| 𝑞 | \neq 0$ ，那么 $| 𝑞 | \geq 1$ ，所以 $| 𝑥 | \leq | 𝑦 |$ 。

最大公因数与最小公倍数

最大公因数

定理-定义 25 (最大公因数)

设 $𝑥, 𝑦 \in ℤ$ ，若 $𝑥, 𝑦$ 不全为零，则存在唯一的 $𝑑 \in ℤ$ 满足：

$𝑑$ 是 $𝑥, 𝑦$ 的公因数： $𝑑 ∣ 𝑥$ 并且 $𝑑 ∣ 𝑦$ ；
$𝑑$ 是最大的公因数：若 $𝑐 \in ℤ$ 满足 $𝑐 ∣ 𝑥$ 并且 $𝑐 ∣ 𝑦$ ，那么 $𝑐 \leq 𝑑$ 。

我们将这个 $𝑑$ 称为 $𝑥, 𝑦$ 的「最大公因数」，记为 $gcd (𝑥, 𝑦)$ 。

定理-定义 25: 最大公因数

注记 26

我们前面说过，所有非零整数都是 0 的因数，所以当 $𝑥, 𝑦$ 都为 0 的时候，所有非零整数都是它们的公因数，则自然不存在「最大公因数」。

证明 27

首先，公因数的存在性是显然的，1 就是 $𝑥, 𝑦$ 的公因子。下面考虑最大公因数的存在性和唯一性。

设 $𝑑$ 为 $𝑥, 𝑦$ 的公因数，由于 $𝑥, 𝑦$ 不都为零，由我们前面的命题我们知道「非零整数不会小于它自己的因子」，那么 $| 𝑑 | \leq max (| 𝑥 |, | 𝑦 |)$ 。

所以，我们证明了，一方面 $𝑥, 𝑦$ 的公因数是存在的，另一方面 $𝑥, 𝑦$ 的公因数的取值是有固定范围的，那么显然存在唯一的最大公因数。

注记 28 (关于最大公因数范围的命题)

从上面的证明中我们还可以得到一些小结论：

由于 1 是 $𝑥, 𝑦$ 的一个平凡的公因子，所以 $1 \leq gcd (𝑥, 𝑦)$ ；
证明中我们看到 $gcd (𝑥, 𝑦) \leq max (| 𝑥 |, | 𝑦 |)$ ；

总的来看，我们就有 $1 \leq gcd (𝑥, 𝑦) \leq max (| 𝑥 |, | 𝑦 |)$ 。

注记 28: 关于最大公因数范围的命题

下面我们给出关于最大公因数的两个小结论。

命题 29

对任意 $𝑎 \in ℤ^{*}$ ， $gcd (𝑎, 0) = | 𝑎 |$ ；
对任意 $𝑥, 𝑦 \in ℤ$ ，若它们不全为零，那么 $gcd (𝑥, 𝑦) = gcd (| 𝑥 |, | 𝑦 |)$ 。

证明 30

从上面的注记中我们知道 $1 \leq gcd (𝑥, 𝑦) \leq max (| 𝑥 |, | 𝑦 |)$ ，所以 $1 \leq gcd (𝑎, 0) \leq | 𝑎 |$ ，又因为 $| 𝑎 |$ 显然是 $𝑎$ 和 0 的公因数，所以 $gcd (𝑎, 0) = | 𝑎 |$ ；

辗转相除法

素数

定义 31 (素数)

设非零整数 $𝑝 \neq \pm 1$ 。如果 $𝑝$ 除了平凡因数（即 $\pm 1, \pm 𝑝$ ）以外没有其他因数，那么称 $𝑝$ 为素数。

定义 31: 素数

注记 32

一般初等数论的教课书都会这样定义素数，但这个定义看起来挺唐突的，好像并不是蕴含什么深刻的动机。我们下面展示另一种等价的定义。

定理 33 (素数作为一般素元)

设非零整数 $𝑝 \neq \pm 1$ ，则以下两个命题等价：

$𝑝$ 是素数；
对任意 $𝑎, 𝑏 \in ℤ$ ，有 $𝑝 ∣ 𝑎 𝑏 ⟺ (𝑝 ∣ 𝑎) \lor (𝑝 ∣ 𝑏)$ 。

定理 33: 素数作为一般素元

证明 34

注记 35

以上定理中的第二条等价定义才是「素性」的体现。如果考虑一般的环，