初等数论笔记

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

对任意 $𝑎,𝑏\in \mathbb{Z}$，若 $𝑏\ne 0$，则存在唯一的 $𝑞,𝑟\in \mathbb{Z}$ 使得

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

注记 2 (除数不为零)

• 要求除数 $𝑏$ 不为零是我们一直习惯的做法，事实上如果考虑 $𝑏=0$，那么该定理是显然不成立的，也就更不存在「一个数除以 0 的商和余数」的说法了。

  • 被除数 $𝑎$ 为零是没问题的。
• 除了这里广义上的除法（带余除法）要求除数不为零以外，狭义上的除法同样要求除数不为零，具体的原因见 B 站刘思齐《抽象代数》第一讲。
• 我们约定记号 ${\mathbb{Z}}^{\ast }≔\mathbb{Z}\backslash \left\{0\right\}$ 表示非零整数集。

证明 3 (非正式)

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

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

定义 4 (整除)

设 $𝑎,𝑏\in \mathbb{Z}$：

• 若 $𝑏\ne 0$ 且 $𝑎$ 除以 $𝑏$ 的余数为 $0$（即存在 $𝑞\in \mathbb{Z}$ 使得 $𝑎=𝑏𝑞$），则称「$𝑏$ 整除 $𝑎$」，或说「$𝑎$ 被 $𝑏$ 整除」，记作 $𝑏\mid 𝑎$。此时 $𝑏$ 叫做 $𝑎$ 的因数，$𝑎$ 叫做 $𝑏$ 的倍数。
• 若 $𝑏\ne 0$ 且 $𝑎$ 除以 $𝑏$ 的余数不为 $0$（即不存在 $𝑞\in \mathbb{Z}$ 使得 $𝑎=𝑏𝑞$），则称「$𝑏$ 不能整除 $𝑎$」，或说「$𝑎$ 不能被 $𝑏$ 整除」，记作 $𝑏\nmid 𝑎$。

注记 5

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

• 对于任意非零整数 $𝑎$，它的因数包括 $\pm 1$ 和 $\pm 𝑎$。这是因为 $𝑎=1\cdot 𝑎$ 以及 $𝑎=\left(-1\right)\left(-𝑎\right)$。这四个因数称为 $𝑎$ 的「平凡因数」。

  • 对于任意整数 $𝑎$，它的因数都包含 $\pm 1$。

定义 6 (奇数偶数)

对于任意 $𝑥\in \mathbb{Z}$：

• 若 $2\mid 𝑥$，即存在 $𝑞\in \mathbb{Z}$ 使得 $𝑥=2𝑞$，则称 $𝑥$ 为偶数；
• 否则（即 $2\nmid 𝑥$）称 $𝑥$ 为奇数。

注记 7

若 $𝑥\in \mathbb{Z}$ 为奇数，即 $2\nmid 𝑥$，那么考虑 $𝑥$ 除以 $2$ 的带余除法：

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

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

例 8

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

证明 9

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

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

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

• 自反性：对任意 $𝑎\in {\mathbb{Z}}^{\ast }$ 有 $𝑎\mid 𝑎$；
• 拟反对称性：对任意 $𝑎,𝑏\in \mathbb{Z}$ 有 $𝑎\mid 𝑏\wedge 𝑏\mid 𝑎⟹𝑎=\pm 𝑏$；
• 传递性：对任意 $𝑎,𝑏,𝑐\in \mathbb{Z}$ 有 $𝑎\mid 𝑏\wedge 𝑏\mid 𝑐⟹𝑎\mid 𝑐$。

注记 11

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

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

证明 12

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

命题 13 (整除与正负号)

对于 $𝑎,𝑏\in \mathbb{Z}$，有

证明 14

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

例 15

命题 16

考虑 $𝑥,{𝑦}_1,{𝑦}_2\in \mathbb{Z}$，设 $𝑥\mid {𝑦}_1$ 且 $𝑥\mid {𝑦}_2$，则对于任意 ${𝑎}_1,{𝑎}_2\in \mathbb{Z}$ 有 $𝑥\mid \left({𝑎}_1{𝑦}_1+{𝑎}_2{𝑦}_2\right)$。

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

例 17

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

证明 18

由于 $𝑥\mid {𝑦}_1$ 并且 $𝑥\mid {𝑦}_2$，所以按定义存在 ${𝑞}_1,{𝑞}_2\in \mathbb{Z}$ 使得

那么

所以按定义有 $𝑥\mid \left({𝑎}_1{𝑦}_1+{𝑎}_2{𝑦}_2\right)$。

注记 19

显然这个命题可以推广为

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

命题 20

考虑 $𝑥,𝑦,𝑎\in \mathbb{Z}$，设 $𝑎\ne 0$，则有 $𝑥\mid 𝑦⟺𝑎𝑥\mid 𝑎𝑦$。

证明 21

对于 $𝑥,𝑦\in \mathbb{Z}$，$𝑥\mid 𝑦$ 等价于存在 $𝑞\in \mathbb{Z}$ 使得 $𝑦=𝑞𝑥$，那么由于 $𝑎\ne 0$，所以这等价于 $𝑎𝑦=𝑞\left(𝑎𝑥\right)$，所以这等价于 $𝑎𝑥\mid 𝑎𝑦$。

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

考虑 $𝑥,𝑦\in \mathbb{Z}$，若 $𝑦\ne 0$，那么 $𝑥\mid 𝑦⟹\left|𝑥\right|\le |𝑦|$。

注记 23

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

证明 24

由于 $𝑥\mid 𝑦$，那么 $𝑥\ne 0$ 并且存在 $𝑞\in \mathbb{Z}$ 使得 $𝑦=𝑞𝑥$，那么就有 $|𝑦|=\left|𝑞\right|\cdot |𝑥|$。又因为 $𝑦\ne 0$，所以 $|𝑞|\ne 0$，那么 $|𝑞|\ge 1$，所以 $|𝑥|\le |𝑦|$。

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

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

• $𝑑$ 是 $𝑥,𝑦$ 的公因数：$𝑑\mid 𝑥$ 并且 $𝑑\mid 𝑦$；
• $𝑑$ 是最大的公因数：若 $𝑐\in \mathbb{Z}$ 满足 $𝑐\mid 𝑥$ 并且 $𝑐\mid 𝑦$，那么 $𝑐\le 𝑑$。

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

注记 26

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

证明 27

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

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

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

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

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

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

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

命题 29

1. 对任意 $𝑎\in {\mathbb{Z}}^{\ast }$，$gcd\left(𝑎,0\right)=|𝑎|$；
2. 对任意 $𝑥,𝑦\in \mathbb{Z}$，若它们不全为零，那么 $gcd\left(𝑥,𝑦\right)=gcd\left(|𝑥|,|𝑦|\right)$。

证明 30

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

定义 31 (素数)

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

注记 32

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

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

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

1. $𝑝$ 是素数；
2. 对任意 $𝑎,𝑏\in \mathbb{Z}$，有 $𝑝\mid 𝑎𝑏⟺\left(𝑝\mid 𝑎\right)\vee \left(𝑝\mid 𝑏\right)$。

注记 35

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