一、回顾：整数加法群的子群
上节课的主要结果：整数加法群 $(\mathbb{Z}, +)$ 的任意子群 $H$，都存在某个自然数 $d$，使得
\[H = d\mathbb{Z} = \{dz \mid z \in \mathbb{Z}\}\]即 $H$ 恰好是 $d$ 的所有整数倍组成的集合。反过来，给定任意整数 $d$，其所有整数倍 $d\mathbb{Z}$ 也构成 $(\mathbb{Z}, +)$ 的子群。
证明方法是利用带余除法。下面利用这个结论来建立最大公因数的基本性质。
二、整除
2.1 整除的定义
设 $a, b \in \mathbb{Z}$。若存在整数 $q$ 使得 $b = qa$，则称 $a$ 整除 $b$（或 $b$ 是 $a$ 的倍数，$a$ 是 $b$ 的因数），记作 $a \mid b$。
用整除的语言，子群可以写成：
\[d\mathbb{Z} = \{b \in \mathbb{Z} \mid d \mid b\}\]2.2 整除的基本性质
- 自反性：$a \mid a$（因为 $a = 1 \cdot a$）
- 反对称性（差正负号）：若 $a \mid b$ 且 $b \mid a$，则 $b = \pm a$
- 传递性：若 $a \mid b$ 且 $b \mid c$，则 $a \mid c$
- 线性性：若 $a \mid b$ 且 $a \mid c$，则 $a \mid (b \pm c)$
整除关系差不多是一个偏序关系——它满足自反性、传递性，第2条某种意义上可以看成反对称性（差一个正负号）。
2.3 关于零的整除
从定义出发：
- 任何整数 $a$ 都是 $0$ 的因数（因为 $0 = 0 \cdot a$），包括 $0$ 本身
- 若 $a = 0$ 且 $b \ne 0$，则 $a$ 不能整除 $b$（因为 $0 \cdot q = 0 \ne b$）
三、最大公因数
3.1 公因数与最大公因数的定义
设 $a, b \in \mathbb{Z}$。自然数 $d \in \mathbb{N}$ 称为 $a$ 和 $b$ 的最大公因数，若满足：
- $d \mid a$ 且 $d \mid b$（$d$ 是公因数）
- 对任意 $c \in \mathbb{Z}$，若 $c \mid a$ 且 $c \mid b$，则 $c \mid d$（$d$ 是最大的公因数）
这里”最大”是从整除关系来刻画的：所有公因数都是 $d$ 的因数。也可以定义为所有公因数中数值最大的，两种定义等价，但整除关系的定义更标准、更便于推广。
记号：$d = \gcd(a, b)$。有些书写作 $(a, b)$，但容易与有序对混淆。
3.2 最大公因数的存在性与线性表示
定理. 设 $a, b \in \mathbb{Z}$，则存在 $d \in \mathbb{N}$ 及整数 $u, v$，使得
\[d = ua + vb, \quad d \mid a, \quad d \mid b, \quad d \ge 0\]且 $d$ 是 $a$ 和 $b$ 的最大公因数。
证明. 考虑集合
\[H = \{xa + yb \mid x, y \in \mathbb{Z}\}\]断言：$H$ 是 $(\mathbb{Z}, +)$ 的子群，且 $a, b \in H$。
- $a \in H$：因为 $a = 1 \cdot a + 0 \cdot b$
- $b \in H$：因为 $b = 0 \cdot a + 1 \cdot b$
- $H$ 对加法封闭：$(x_1 a + y_1 b) + (x_2 a + y_2 b) = (x_1 + x_2)a + (y_1 + y_2)b \in H$
- $H$ 对取相反数封闭：$-(xa + yb) = (-x)a + (-y)b \in H$
由上节课的结论，存在自然数 $d$ 使得 $H = d\mathbb{Z}$。
由此：
- 因为 $a, b \in H = d\mathbb{Z}$，所以 $d \mid a$ 且 $d \mid b$（$d$ 是公因数）
- 因为 $d \in H$，由 $H$ 的定义，存在整数 $u, v$ 使得 $d = ua + vb$（$d$ 可以写成线性组合）
验证 $d$ 是最大公因数：设 $c$ 是 $a$ 和 $b$ 的任意公因数（即 $c \mid a$ 且 $c \mid b$），则 $c \mid ua$ 且 $c \mid vb$，从而 $c \mid (ua + vb) = d$。
因此 $d$ 满足最大公因数的全部条件。$\blacksquare$
关于 $u, v$ 的具体求法：可以通过辗转相除法（扩展欧几里得算法）来找到，这里关注存在性。
3.3 最大公因数的唯一性
推论. 设 $a, b \in \mathbb{Z}$，则 $\gcd(a, b)$ 存在且唯一，并且可以写成 $a$ 和 $b$ 的整系数线性组合。
唯一性的证明：设 $d_1, d_2$ 都是 $a, b$ 的最大公因数。由定义，$d_1 \mid d_2$ 且 $d_2 \mid d_1$（因为它们互为对方的公因数），故 $d_2 = \pm d_1$。又 $d_1, d_2 \ge 0$，所以 $d_1 = d_2$。$\blacksquare$
存在性的证明：由上述定理，存在 $d \ge 0$ 及整数 $u, v$ 使得 $d = ua + vb$，$d \mid a$，$d \mid b$，且 $d$ 是最大公因数。$\blacksquare$
代数中常见的模式：存在性通常需要构造，唯一性通常从定义出发。
四、互素
4.1 互素的定义
设 $a, b \in \mathbb{Z}$。若 $\gcd(a, b) = 1$，则称 $a$ 和 $b$ 互素（互质）。
直观含义：$a$ 和 $b$ 除了 $\pm 1$ 之外没有其他公因数。
例：$2$ 和 $3$ 互素。
4.2 互素的等价条件
推论. $a$ 和 $b$ 互素的充分必要条件是：存在整数 $u, v$ 使得
\[ua + vb = 1\]证明：
- ($\Rightarrow$) 若 $\gcd(a, b) = 1$，由最大公因数可以写成线性组合，存在 $u, v$ 使得 $ua + vb = 1$。
- ($\Leftarrow$) 若存在 $u, v$ 使得 $ua + vb = 1$，则 $a, b$ 的任意公因数 $c$ 整除 $ua + vb = 1$，故 $c \mid 1$，即 $c = \pm 1$。因此 $\gcd(a, b) = 1$。$\blacksquare$
五、整除与互素的重要推论
5.1 互素条件下的整除
推论. 设 $a, b, c \in \mathbb{Z}$。若 $a \mid bc$ 且 $\gcd(a, b) = 1$，则 $a \mid c$。
证明. 由 $\gcd(a, b) = 1$，存在整数 $u, v$ 使得 $ua + vb = 1$。两边乘以 $c$：
\[c = uac + vbc\]- $a \mid uac$（因为含因子 $a$）
- $a \mid vbc$（因为 $a \mid bc$ 是条件）
故 $a \mid (uac + vbc) = c$。$\blacksquare$
互素条件不可省略。反例：$a = 4$，$b = 2$，$c = 2$，则 $4 \mid 4$ 成立且 $4 \nmid 2$，而 $\gcd(4, 2) = 2 \ne 1$。
5.2 除以最大公因数后互素
推论. 设 $a, b \in \mathbb{Z}$，$a, b$ 不全为零，$d = \gcd(a, b)$。则
\[\gcd\!\left(\frac{a}{d},\ \frac{b}{d}\right) = 1\]证明. 由 $d = ua + vb$，两边除以 $d$：
\[1 = u \cdot \frac{a}{d} + v \cdot \frac{b}{d}\]因为 $d \mid a$ 且 $d \mid b$，所以 $\frac{a}{d}$ 和 $\frac{b}{d}$ 都是整数。由互素的等价条件，$\gcd!\left(\frac{a}{d}, \frac{b}{d}\right) = 1$。$\blacksquare$
直观理解：把两个数的最大公因数部分全部除掉后，剩下的部分不再有公共因子。
5.3 一般情形下的整除
推论. 设 $a, b, c \in \mathbb{Z}$，$a, b$ 不全为零。若 $a \mid bc$，则
\[\frac{a}{\gcd(a, b)} \;\bigg|\; c\]证明. 令 $d = \gcd(a, b)$。由推论 5.2，$\gcd!\left(\frac{a}{d}, \frac{b}{d}\right) = 1$。
由 $a \mid bc$，同时除以 $d$（整除关系在同除公因数后保持），得 $\frac{a}{d} \mid \frac{b}{d} \cdot c$。
由推论 5.1（$\frac{a}{d}$ 与 $\frac{b}{d}$ 互素），得 $\frac{a}{d} \mid c$。$\blacksquare$
当 $\gcd(a, b) = 1$ 时，此结论退化为推论 5.1。这个结论比条件 $a \mid bc$ 更强。
六、同余
6.1 同余的定义
设 $a, b, c \in \mathbb{Z}$。若 $c \mid (b - a)$，则称 $a$ 和 $b$ 模 $c$ 同余，记作
\[a \equiv b \pmod{c}\]这个记号由高斯 (Gauss) 在其著作《算术研究》(Disquisitiones Arithmeticae) 中提出，至今仍是数论和代数中最基本的记号之一。记号的好处在于：它更像等式，当 $a, b$ 的表达式较长时，写在等号两边比用整除符号更方便；而且在推导中模数经常变化，这种写法更清晰。
6.2 同余的基本性质
设 $m \in \mathbb{Z}$（通常取正整数），$a, b, c, d \in \mathbb{Z}$。
- 等价条件：$a \equiv b \pmod{m} \iff$ 存在整数 $q$ 使得 $b = qm + a$
- 自反性：$a \equiv a \pmod{m}$
- 对称性：$a \equiv b \pmod{m} \implies b \equiv a \pmod{m}$
- 传递性：$a \equiv b \pmod{m}$，$b \equiv c \pmod{m} \implies a \equiv c \pmod{m}$
- 与运算相容：若 $a \equiv b \pmod{m}$，$c \equiv d \pmod{m}$，则
- $a + c \equiv b + d \pmod{m}$
- $ac \equiv bd \pmod{m}$
性质2-4说明：给定 $m$，同余是一个等价关系。性质5说明同余与加法、乘法相容（后面从群和环的角度有更广泛的理解）。
6.3 性质1的证明
$a \equiv b \pmod{m}$ 即 $m \mid (b - a)$，由整除定义，存在整数 $q$ 使得 $b - a = qm$，即 $b = qm + a$。
形式上类似带余除法 $b = qm + r$，其中 $a$ 扮演余数的角色。
6.4 乘法相容性的证明
方法一（利用性质1）：
由条件，存在整数 $p, q$ 使得 $b = qm + a$，$d = pm + c$。则
\[bd = (qm + a)(pm + c) = pqm^2 + cqm + apm + ac\] \[= (pqm + cq + ap) \cdot m + ac\]故 $bd \equiv ac \pmod{m}$。$\blacksquare$
方法二（添项法）：
\[bd - ac = bd - bc + bc - ac = b(d - c) + (b - a)c\]由 $m \mid (b - a)$ 和 $m \mid (d - c)$，得 $m \mid b(d - c)$ 且 $m \mid (b - a)c$，故 $m \mid (bd - ac)$。$\blacksquare$
添项法（加一项减一项）是非常常见的技巧：凑出公因子以便使用分配律。
七、同余与余数
7.1 取余运算
设 $m$ 为正整数，$b \in \mathbb{Z}$。对 $b$ 做带余除法：
\[b = qm + r, \quad 0 \le r \le m - 1\]其中 $q$ 为商，$r$ 为余数。记
\[b \mathbin{\%} m := r\]这与程序语言中的取模运算一致。
7.2 同余即同余数
命题. 设 $m$ 为正整数。
- 若 $f, g \in {0, 1, \ldots, m-1}$ 且 $f \equiv g \pmod{m}$，则 $f = g$
- $a \equiv b \pmod{m} \iff a \mathbin{\%} m = b \mathbin{\%} m$
性质1的证明：由 $f \equiv g \pmod{m}$，存在整数 $q$ 使得 $g - f = qm$。因为 $f, g \in {0, \ldots, m-1}$，所以
\[|g - f| \le m - 1 < m\]| 而 $ | g - f | = | q | \cdot m$，故 $ | q | < 1$，即 $q = 0$，从而 $f = g$。$\blacksquare$ |
性质2的证明：设 $a = q_1 m + r_1$，$b = q_2 m + r_2$，其中 $r_1 = a \mathbin{\%} m$，$r_2 = b \mathbin{\%} m$，$r_1, r_2 \in {0, \ldots, m-1}$。
$a \equiv b \pmod{m}$ 当且仅当 $a \equiv r_1 \pmod{m}$、$b \equiv r_2 \pmod{m}$（由等价关系的传递性和对称性），当且仅当 $r_1 \equiv r_2 \pmod{m}$，由性质1当且仅当 $r_1 = r_2$。$\blacksquare$
这就是”同余”名称的由来——两个数模 $m$ 同余，等价于它们除以 $m$ 的余数相同。
八、模 $n$ 加法群（有限循环群）
8.1 定义
设 $n$ 为正整数。在集合 ${0, 1, 2, \ldots, n-1}$ 上定义运算 $\oplus$：
\[i \oplus j := (i + j) \mathbin{\%} n\]即先做通常的整数加法，再对 $n$ 取余数。
等价地，$i \oplus j$ 是 ${0, \ldots, n-1}$ 中满足 $i \oplus j \equiv i + j \pmod{n}$ 的唯一元素。
更具体地：
\[i \oplus j = \begin{cases} i + j, & \text{若 } i + j \le n - 1 \\ i + j - n, & \text{若 } i + j \ge n \end{cases}\]因为 $i, j \in {0, \ldots, n-1}$，所以 $i + j \in {0, \ldots, 2n-2}$，至多减一个 $n$ 即可回到 ${0, \ldots, n-1}$。
严格来说，运算 $\oplus$ 依赖于 $n$，应记为 $\oplus_n$，但在 $n$ 确定时省略下标。
8.2 群结构
命题. $({0, 1, \ldots, n-1},\ \oplus)$ 构成一个群，并且是 $n$ 阶循环群，由 $1$ 生成。
- 阶（元素个数）为 $n$
- 由 $1$ 生成：$\underbrace{1 \oplus 1 \oplus \cdots \oplus 1}_{k} = k \mathbin{\%} n$，当 $k$ 遍历所有整数时，恰好生成 ${0, 1, \ldots, n-1}$
验证群公理（结合律、零元、逆元）在下一讲展开。
书上用同余类来定义 $\mathbb{Z}_n$（即把所有模 $n$ 同余的整数归为一个等价类，再定义等价类之间的加法）。两种做法本质相同，但这里的构造更具体直观；书上的做法更一般化，后面讲陪集和正规子群后会回到那种视角。