整数集对加法、减法、乘法都封闭，但对除法却不封闭，为了谈论整数的除法，我们引入「带余除法」。

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

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

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

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

证明 (非正式). 带余除法我们从小学就在用了，我没记错的话，当时的写法是类似这样的：

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

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

1.2 注记 (除数不为零)

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

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

1.3 定义 (整除)

设 $𝑎, 𝑏 \in ℤ$ ：

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

1.4 注记

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

1.5 定义 (奇数偶数)

对于任意 $𝑥 \in ℤ$ ：

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

1.6 注记

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

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

其中 $𝑞_{0}$ 是商， $𝑟_{0}$ 是余数。根据带余除法的定义有 $0 \leq 𝑟_{0} < 2$ ，由于 $2 ∤ 𝑥$ ，所以 $𝑟_{0} \neq 0$ ，所以 $𝑟_{0} = 1$ 。所以 $𝑥 \in ℤ$ 是奇数等价于存在 $𝑞 \in ℤ$ 使得 $𝑥 = 2 𝑞 + 1$ 。

证明.

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

$□$

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

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

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

1.9 注记

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

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

证明.

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

$□$

1.10 命题 (整除与正负号)

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

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

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

1.12 命题

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

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

1.13 例

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

证明. 由于 $𝑥 ∣ 𝑦_{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})$ 。 $□$

1.14 注记

显然这个命题可以推广为

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

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

1.15 命题

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

证明. 对于

𝑥, 𝑦 \in ℤ

，

𝑥 ∣ 𝑦

等价于存在

𝑞 \in ℤ

使得

𝑦 = 𝑞 𝑥

，那么由于

𝑎 \neq 0

，所以这等价于

𝑎 𝑦 = 𝑞 (𝑎 𝑥)

，所以这等价于

𝑎 𝑥 ∣ 𝑎 𝑦

。

□

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

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

1.17 注记

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

证明. 由于

𝑥 ∣ 𝑦

，那么

𝑥 \neq 0

并且存在

𝑞 \in ℤ

使得

𝑦 = 𝑞 𝑥

，那么就有

| 𝑦 | = | 𝑞 | \cdot | 𝑥 |

。又因为

𝑦 \neq 0

，所以

| 𝑞 | \neq 0

，那么

| 𝑞 | \geq 1

，所以

| 𝑥 | \leq | 𝑦 |

。

□

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

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

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

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

1.19 注记

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

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

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

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

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

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

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

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

1.21 命题

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

证明.

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

$□$

1.22 定义 (素数)

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

1.23 注记

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

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

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

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