5行间公式索引
1.
$$
a \sim b \text { 当且仅当 } n \mid(b-a) .
$$
解释: 定义了整数 $a$ 和 $b$ 之间“模 $n$ 相关”的关系，即它们的差能被 $n$ 整除。
2. $$
\begin{aligned}
\bar{a} & =\{a+k n \mid k \in \mathbb{Z}\} \\
& =\{a, a \pm n, a \pm 2 n, a \pm 3 n, \ldots\} .
\end{aligned}
$$
**解释**: 定义了整数 $a$ 的剩余类（或同余类）$\bar{a}$，它是一个包含了所有与 $a$ 相差 $n$ 的整数倍的数的无限集合。
3. $$ \overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}
$$
解释: 列出了模 $n$ 的所有 $n$ 个不同的剩余类，它们构成了集合 $\mathbb{Z}/n\mathbb{Z}$。
4.
$$
\bar{a}+\bar{b}=\overline{a+b} \quad \text { 和 } \quad \bar{a} \cdot \bar{b}=\overline{a b} .
$$
解释: 定义了剩余类之间的加法和乘法运算，其核心思想是利用代表元在整数环中进行运算，然后取结果所在的类。
5.
$$
\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{11}
$$
解释: 示例，列出了模12的所有12个剩余类。
6.
$$
a_{1} \equiv b_{1} \quad(\bmod n) \quad \text { 且 } \quad a_{2} \equiv b_{2} \quad(\bmod n)
$$
解释: 定理3的前提条件，假设两组代表元分别对应同一个类。
7.
$$
a_{1}+a_{2} \equiv b_{1}+b_{2} \quad(\bmod n) \quad \text { 且 } \quad a_{1} a_{2} \equiv b_{1} b_{2} \quad(\bmod n) .
$$
解释: 定理3的结论，证明了同余关系在整数加法和乘法下是保持的，从而保证了类运算的良定义性。
8.
$$
(\mathbb{Z} / n \mathbb{Z})^{\times}=\{\bar{a} \in \mathbb{Z} / n \mathbb{Z} \mid \text { 存在 } \bar{c} \in \mathbb{Z} / n \mathbb{Z} \text { 使得 } \bar{a} \cdot \bar{c}=\overline{1}\} .
$$
解释: 定义了模 $n$ 的乘法群（或单位群）$(\mathbb{Z}/n\mathbb{Z})^\times$，它由 $\mathbb{Z}/n\mathbb{Z}$ 中所有存在乘法逆元的元素构成。
9. $$
\begin{aligned}
60 & =(3) 17+9 \\
17 & =(1) 9+8 \\
9 & =(1) 8+1
\end{aligned}
$$
**解释**: 示例，展示了使用欧几里得算法计算 $\gcd(60, 17)$ 的过程。
## 5. 习题详解
### 5.1 习题 1
[原文]
1. 明确写出 $\mathbb{Z} / 18 \mathbb{Z}$ 中剩余类的所有元素。
[逐步解释]
这个习题要求我们具体地描述构成集合 $\mathbb{Z}/18\mathbb{Z}$ 的18个剩余类。一个剩余类是一个包含了所有模18同余的整数的无限集合。我们将为每一个剩余类（从 $\bar{0}$到 $\overline{17}$）展示其定义并列举其中的一些成员。
* $\bar{0}$: 这是所有能被18整除的整数的集合。
$\bar{0} = \{18k \mid k \in \mathbb{Z}\} = \{\ldots, -36, -18, 0, 18, 36, \ldots\}$
* $\bar{1}$: 这是所有除以18余1的整数的集合。
$\bar{1} = \{18k+1 \mid k \in \mathbb{Z}\} = \{\ldots, -35, -17, 1, 19, 37, \ldots\}$
* $\bar{2}$: 这是所有除以18余2的整数的集合。
$\bar{2} = \{18k+2 \mid k \in \mathbb{Z}\} = \{\ldots, -34, -16, 2, 20, 38, \ldots\}$
* $\bar{3}$: 这是所有除以18余3的整数的集合。
$\bar{3} = \{18k+3 \mid k \in \mathbb{Z}\} = \{\ldots, -33, -15, 3, 21, 39, \ldots\}$
* $\bar{4}$: 这是所有除以18余4的整数的集合。
$\bar{4} = \{18k+4 \mid k \in \mathbb{Z}\} = \{\ldots, -32, -14, 4, 22, 40, \ldots\}$
* $\bar{5}$: 这是所有除以18余5的整数的集合。
$\bar{5} = \{18k+5 \mid k \in \mathbb{Z}\} = \{\ldots, -31, -13, 5, 23, 41, \ldots\}$
* $\bar{6}$: 这是所有除以18余6的整数的集合。
$\bar{6} = \{18k+6 \mid k \in \mathbb{Z}\} = \{\ldots, -30, -12, 6, 24, 42, \ldots\}$
* $\bar{7}$: 这是所有除以18余7的整数的集合。
$\bar{7} = \{18k+7 \mid k \in \mathbb{Z}\} = \{\ldots, -29, -11, 7, 25, 43, \ldots\}$
* $\bar{8}$: 这是所有除以18余8的整数的集合。
$\bar{8} = \{18k+8 \mid k \in \mathbb{Z}\} = \{\ldots, -28, -10, 8, 26, 44, \ldots\}$
* $\bar{9}$: 这是所有除以18余9的整数的集合。
$\bar{9} = \{18k+9 \mid k \in \mathbb{Z}\} = \{\ldots, -27, -9, 9, 27, 45, \ldots\}$
* $\overline{10}$: 这是所有除以18余10的整数的集合。
$\overline{10} = \{18k+10 \mid k \in \mathbb{Z}\} = \{\ldots, -26, -8, 10, 28, 46, \ldots\}$
* $\overline{11}$: 这是所有除以18余11的整数的集合。
$\overline{11} = \{18k+11 \mid k \in \mathbb{Z}\} = \{\ldots, -25, -7, 11, 29, 47, \ldots\}$
* $\overline{12}$: 这是所有除以18余12的整数的集合。
$\overline{12} = \{18k+12 \mid k \in \mathbb{Z}\} = \{\ldots, -24, -6, 12, 30, 48, \ldots\}$
* $\overline{13}$: 这是所有除以18余13的整数的集合。
$\overline{13} = \{18k+13 \mid k \in \mathbb{Z}\} = \{\ldots, -23, -5, 13, 31, 49, \ldots\}$
* $\overline{14}$: 这是所有除以18余14的整数的集合。
$\overline{14} = \{18k+14 \mid k \in \mathbb{Z}\} = \{\ldots, -22, -4, 14, 32, 50, \ldots\}$
* $\overline{15}$: 这是所有除以18余15的整数的集合。
$\overline{15} = \{18k+15 \mid k \in \mathbb{Z}\} = \{\ldots, -21, -3, 15, 33, 51, \ldots\}$
* $\overline{16}$: 这是所有除以18余16的整数的集合。
$\overline{16} = \{18k+16 \mid k \in \mathbb{Z}\} = \{\ldots, -20, -2, 16, 34, 52, \ldots\}$
* $\overline{17}$: 这是所有除以18余17的整数的集合。
$\overline{17} = \{18k+17 \mid k \in \mathbb{Z}\} = \{\ldots, -19, -1, 17, 35, 53, \ldots\}$
[总结]
这个习题通过具体列举的方式，帮助我们巩固对“剩余类”作为元素是无限集合这一事实的理解，并直观地看到了 $\mathbb{Z}/18\mathbb{Z}$ 是如何将所有整数划分成18个不相交的组的。
### 5.2 习题 2
[原文]
2. 证明 $\mathbb{Z} / n \mathbb{Z}$ 中不同的等价类恰好是 $\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}$（使用除法算法）。
[逐步解释]
这个习题要求我们使用**带余除法（Division Algorithm）** 这个基本工具，来严格证明模 $n$ 的剩余类集合 $\mathbb{Z}/n\mathbb{Z}$ 恰好由 $\overline{0}, \overline{1}, \ldots, \overline{n-1}$ 这 $n$ 个不同的类构成。证明需要包含两个方面：
1. **完备性 (Completeness)**: 任何一个整数都属于这 $n$ 个类中的某一个。
2. **互异性 (Distinctness)**: 这 $n$ 个类是两两不同的。
**证明完备性**:
* 令 $a$ 为任意一个整数。
* 根据带余除法定理，当 $a$ 除以正整数 $n$ 时，存在唯一的整数商 $q$ 和唯一的整数余数 $r$ 使得：
$a = qn + r$, 并且 $0 \le r < n$。
* $0 \le r < n$ 意味着 $r$ 只能是 $0, 1, 2, \ldots, n-1$ 中的某一个。
* 从等式 $a = qn + r$ 移项得到 $a - r = qn$。
* 根据整除的定义，这意味着 $n \mid (a-r)$。
* 再根据同余的定义，这意味着 $a \equiv r \pmod{n}$。
* 根据剩余类的定义，如果两个数同余，它们就属于同一个剩余类。因此 $\bar{a} = \bar{r}$。
* 因为 $r$ 是 $\{0, 1, \ldots, n-1\}$ 中的一员，所以 $\bar{r}$ 就是 $\{\overline{0}, \overline{1}, \ldots, \overline{n-1}\}$ 中的一员。
* 这就证明了任何一个整数 $a$ 的剩余类 $\bar{a}$ 必定是这 $n$ 个类中的一个。
**证明互异性**:
* 我们要证明集合 $\{\overline{0}, \overline{1}, \ldots, \overline{n-1}\}$ 中的元素都是不同的。
* 我们采用反证法。假设它们不全是不同的，即存在两个不相等的代表元 $i$ 和 $j$，但它们代表的是同一个类。
* 设 $i, j \in \{0, 1, \ldots, n-1\}$ 且 $i \neq j$，并假设 $\bar{i} = \bar{j}$。
* 为了不失一般性，我们可以假设 $j > i$。
* $\bar{i} = \bar{j}$ 意味着 $i \equiv j \pmod{n}$。
* 根据同余定义，这意味着 $n \mid (j-i)$。
* 但是，根据 $i$ 和 $j$ 的取值范围：
* $0 \le i < n$
* $0 \le j < n$
* 并且我们假设了 $j > i$。
* 我们可以推断出它们差的范围：
* $j-i > 0$。
* 因为 $j \le n-1$ 且 $i \ge 0$，所以 $j-i \le (n-1) - 0 = n-1$。
* 所以我们得到 $0 < j-i \le n-1$。
* 现在我们有一个结论：$j-i$ 是一个在 1 到 $n-1$ 之间的整数。但是我们之前从 $\bar{i}=\bar{j}$ 推导出 $n \mid (j-i)$，即 $j-i$ 必须是 $n$ 的倍数。
* 在 1 到 $n-1$ 的范围内，不存在 $n$ 的倍数。
* 这个矛盾说明我们最初的假设“存在 $i \neq j$ 使得 $\bar{i}=\bar{j}$”是错误的。
* 因此，$\overline{0}, \overline{1}, \ldots, \overline{n-1}$ 这 $n$ 个剩余类必须是两两不同的。
**结论**:
结合完备性和互异性，我们证明了 $\mathbb{Z}/n\mathbb{Z}$ 恰好由 $n$ 个不同的等价类构成，它们可以由 $\overline{0}, \overline{1}, \ldots, \overline{n-1}$ 作为代表。
[总结]
本题的证明是构建模算术理论的基石之一。它通过带余除法，清晰地揭示了为什么无限的整数集 $\mathbb{Z}$ 在“模 $n$”这一等价关系下，能够被精确地、不重不漏地划分为 $n$ 个组。
### 5.3 习题 3
[原文]
3. 证明如果 $a=a_{k} 10^{k}+a_{k-1} 10^{k-1}+\cdots+a_{1} 10+a_{0}$ 是任意正整数，那么 $a \equiv a_{k}+a_{k-1}+\cdots+a_{1}+a_{0}(\bmod 9)$（请注意，这是常见的算术规则，即除以 9 后的余数与十进制数字之和模 9 相同——特别是当且仅当数字之和可被 9 整除时，一个整数才可被 9 整除）[请注意 $10 \equiv 1(\bmod 9)$]。
[逐步解释]
这个习题要求证明一个广为人知的整除规则：“一个数能被9整除，当且仅当它的各位数字之和能被9整除”。我们将证明一个更强的结论：任何一个正整数 $a$ 模9的余数，和它的各位数字之和模9的余数是相同的。
**证明**:
1. **核心观察**: 证明的关键在于提示中给出的事实：$10 \equiv 1 \pmod{9}$。这是因为 $10-1=9$，显然能被9整除。
2. **同余性质的应用**: 我们需要用到同余的两个基本性质：
* 若 $x \equiv y \pmod{n}$，则 $x^k \equiv y^k \pmod{n}$ 对于任意正整数 $k$ 成立。
* 若 $x_i \equiv y_i \pmod{n}$ 且 $c_i$ 是整数，则 $\sum c_i x_i \equiv \sum c_i y_i \pmod{n}$。
3. **推导10的幂**:
* 因为 $10 \equiv 1 \pmod{9}$，所以：
* $10^2 \equiv 1^2 \equiv 1 \pmod{9}$
* $10^3 \equiv 1^3 \equiv 1 \pmod{9}$
* ...
* 对于任意非负整数 $k$，都有 $10^k \equiv 1 \pmod{9}$。
4. **对整数 $a$ 进行分析**:
* 一个正整数 $a$ 可以用它的十进制展开式表示：
$a = a_{k} 10^{k}+a_{k-1} 10^{k-1}+\cdots+a_{1} 10+a_{0}$
其中 $a_i$ 是 $a$ 的各位数字，$a_i \in \{0, 1, \ldots, 9\}$。
* 我们现在要对这个等式的两边同时取模9。
$a \pmod{9} \equiv (a_{k} 10^{k}+a_{k-1} 10^{k-1}+\cdots+a_{1} 10+a_{0}) \pmod{9}$
* 根据同余的加法性质，这等于：
$a \pmod{9} \equiv (a_{k} 10^{k}) + (a_{k-1} 10^{k-1}) + \cdots + (a_{1} 10) + a_{0} \pmod{9}$
5. **替换10的幂**:
* 根据同余的乘法性质和我们在步骤3的结论 ($10^k \equiv 1 \pmod{9}$)，我们可以将表达式中的每一项进行替换：
* $a_k 10^k \equiv a_k \cdot 1 \pmod{9}$
* $a_{k-1} 10^{k-1} \equiv a_{k-1} \cdot 1 \pmod{9}$
* ...
* $a_1 10 \equiv a_1 \cdot 1 \pmod{9}$
* $a_0$ 本身不变。
* 将这些同余式代入步骤4的表达式中：
$a \pmod{9} \equiv (a_k \cdot 1) + (a_{k-1} \cdot 1) + \cdots + (a_1 \cdot 1) + a_0 \pmod{9}$
6. **结论**:
* 化简后得到：
$a \equiv a_{k}+a_{k-1}+\cdots+a_{1}+a_{0} \pmod{9}$
* 这就证明了原数 $a$ 与它的各位数字之和在模9的意义下是同余的。
[具体数值示例]
* **示例1**: $a = 12345$
* 各位数字之和: $1+2+3+4+5=15$。
* 根据我们的证明，$12345 \equiv 15 \pmod{9}$。
* $15 \div 9 = 1$ 余 $6$。所以 $15 \equiv 6 \pmod{9}$。
* 因此，$12345 \equiv 6 \pmod{9}$。
* 我们来验证一下：$12345 \div 9$。
$12345 = 9000 + 3345 = 9000 + 2700 + 645 = 9000 + 2700 + 630 + 15 = 9 \cdot (1000+300+70) + 15$。
$12345 = 9 \cdot 1370 + 9 \cdot 1 + 6 = 9 \cdot 1371 + 6$。
确实，12345除以9的余数是6。结论正确。
[总结]
这个习题是模算术性质的一个经典应用。通过利用 $10 \equiv 1 \pmod 9$ 这一简单事实，并结合同余关系对加法和乘法的保持性，我们能够将一个关于大数 $a$ 的模9问题，转化为一个关于其各位数字之和（一个远小于 $a$ 的数）的模9问题，极大地简化了判断和计算。
### 5.4 习题 4
[原文]
4. 计算 $37^{100}$ 除以 29 后的余数。
[逐步解释]
这个问题要求我们计算 $37^{100} \pmod{29}$。直接计算 $37^{100}$ 是不现实的，所以必须使用模算术的性质来简化计算。主要使用的方法是“反复平方模幂算法”(Modular Exponentiation by Repeated Squaring)。
**步骤 1: 对底数进行约化**
* 首先，我们可以简化底数37。
* $37 = 1 \cdot 29 + 8$。
* 所以，$37 \equiv 8 \pmod{29}$。
* 原问题等价于计算 $8^{100} \pmod{29}$。
**步骤 2: 反复平方**
* 我们不直接计算 $8^{100}$，而是计算一系列8的 $2^k$ 次幂，并且每一步都进行模29约化。
* $8^1 \equiv 8 \pmod{29}$
* $8^2 = 64 = 2 \cdot 29 + 6 \implies 8^2 \equiv 6 \pmod{29}$
* $8^4 = (8^2)^2 \equiv 6^2 = 36 = 1 \cdot 29 + 7 \implies 8^4 \equiv 7 \pmod{29}$
* $8^8 = (8^4)^2 \equiv 7^2 = 49 = 1 \cdot 29 + 20 \implies 8^8 \equiv 20 \pmod{29}$
* *计算技巧*: $20 \equiv -9 \pmod{29}$，使用负数有时能让后续计算更简单。
* $8^{16} = (8^8)^2 \equiv 20^2 = 400$。
* $400 \div 29$: $400 = 10 \cdot 29 + 110 = 13 \cdot 29 + 23$。
* $400 = 13 \cdot 29 + 23 \implies 8^{16} \equiv 23 \pmod{29}$
* *计算技巧*: $23 \equiv -6 \pmod{29}$。
* $8^{32} = (8^{16})^2 \equiv (-6)^2 = 36 \equiv 7 \pmod{29}$
* $8^{64} = (8^{32})^2 \equiv 7^2 = 49 \equiv 20 \pmod{29}$
**步骤 3: 组合结果**
* 现在我们需要将指数100表示成2的幂的和（二进制展开）。
* $100 = 64 + 36 = 64 + 32 + 4$。
* 所以，$8^{100} = 8^{64+32+4} = 8^{64} \cdot 8^{32} \cdot 8^4$。
* 现在应用模算术的乘法性质：
$8^{100} \equiv (8^{64} \pmod{29}) \cdot (8^{32} \pmod{29}) \cdot (8^4 \pmod{29}) \pmod{29}$
* 代入我们在步骤2中计算出的结果：
$8^{100} \equiv 20 \cdot 7 \cdot 7 \pmod{29}$
* 逐步计算：
* $20 \cdot 7 = 140$。
* $140 \div 29$: $140 = 4 \cdot 29 + 24$。
* 所以，$140 \equiv 24 \pmod{29}$。
* 现在计算 $24 \cdot 7 \pmod{29}$。
* $24 \cdot 7 = 168$。
* $168 \div 29$: $168 = 5 \cdot 29 + 23$。
* 所以，$168 \equiv 23 \pmod{29}$。
**结论**:
$37^{100}$ 除以 29 后的余数是 23。
[总结]
本题展示了模幂运算的强大能力。通过“底数约化” -> “反复平方” -> “指数二进制分解并组合结果”这一标准流程，我们可以高效地计算出天文数字般的幂次取模后的结果，而无需处理任何非常大的中间数值。
### 5.5 习题 5
[原文]
5. 计算 $9^{1500}$ 的最后两位数字。
[逐步解释]
这个问题等价于计算 $9^{1500} \pmod{100}$。
**步骤 1: 寻找循环节 (或使用反复平方)**
* 我们将通过计算9的连续幂次模100，来寻找一个循环模式，或者一个能极大简化计算的中间结果。
* $9^1 \equiv 9 \pmod{100}$
* $9^2 = 81 \equiv 81 \pmod{100}$
* $9^3 = 9^2 \cdot 9 \equiv 81 \cdot 9 = 729 \equiv 29 \pmod{100}$
* $9^4 = (9^2)^2 \equiv 81^2 = 6561 \equiv 61 \pmod{100}$
* $9^5 = 9^4 \cdot 9 \equiv 61 \cdot 9 = 549 \equiv 49 \pmod{100}$
* ... 这个过程看起来有点慢，我们尝试跳跃得更快一些。
* $9^8 = (9^4)^2 \equiv 61^2 = 3721 \equiv 21 \pmod{100}$
* $9^{10} = 9^8 \cdot 9^2 \equiv 21 \cdot 81 = 1701 \equiv 1 \pmod{100}$
**步骤 2: 利用发现的规律**
* 我们发现了一个非常有用的事实：$9^{10} \equiv 1 \pmod{100}$。
* 这意味着9的幂模100的序列，以10为周期进行循环。$\bar{1}$ 是乘法单位元，一旦幂次的结果达到 $\bar{1}$，后续的计算就会变得非常简单。
**步骤 3: 对指数进行运算**
* 我们想计算 $9^{1500}$。
* 我们可以将指数1500表示成与10相关的形式：$1500 = 10 \cdot 150$。
* 所以，$9^{1500} = 9^{10 \cdot 150} = (9^{10})^{150}$。
* 现在应用模算术性质：
$9^{1500} \equiv (9^{10})^{150} \pmod{100}$
* 代入我们在步骤2的发现：
$9^{1500} \equiv 1^{150} \pmod{100}$
* $1$的任何次幂都是1。
$9^{1500} \equiv 1 \pmod{100}$
**结论**:
$9^{1500}$ 模 100 的结果是 1。因此，$9^{1500}$ 的最后两位数字是 01。
[总结]
本题再次展示了模幂运算的技巧。与上一题相比，本题的关键在于通过计算发现了一个小的幂次（10次）就能让结果回到单位元 $\bar{1}$。一旦找到这个“捷径”，计算就变得异常简单。这个“最小的使 $a^k \equiv 1 \pmod n$ 成立的正指数 $k$”在群论中被称为元素 $\bar{a}$ 的**阶 (Order)**。
### 5.6 习题 6, 7, 8 (一组相关的证明)
#### 5.6.1 习题 6
[原文]
6. 证明 $\mathbb{Z} / 4 \mathbb{Z}$ 中元素的平方只有 $\overline{0}$ 和 $\overline{1}$。
[逐步解释]
这个问题要求我们考察 $\mathbb{Z}/4\mathbb{Z}$ 中所有元素的平方运算的结果。$\mathbb{Z}/4\mathbb{Z} = \{\bar{0}, \bar{1}, \bar{2}, \bar{3}\}$。我们只需对这四个元素一一进行平方运算即可。
**证明 (通过穷举法)**:
* **计算 $\bar{0}^2$**:
$\bar{0}^2 = \bar{0} \cdot \bar{0} = \overline{0 \cdot 0} = \bar{0}$
* **计算 $\bar{1}^2$**:
$\bar{1}^2 = \bar{1} \cdot \bar{1} = \overline{1 \cdot 1} = \bar{1}$
* **计算 $\bar{2}^2$**:
$\bar{2}^2 = \bar{2} \cdot \bar{2} = \overline{2 \cdot 2} = \bar{4}$。因为 $4 \equiv 0 \pmod 4$，所以 $\bar{4} = \bar{0}$。
* **计算 $\bar{3}^2$**:
$\bar{3}^2 = \bar{3} \cdot \bar{3} = \overline{3 \cdot 3} = \bar{9}$。因为 $9 = 2 \cdot 4 + 1$，所以 $9 \equiv 1 \pmod 4$，即 $\bar{9} = \bar{1}$。
* *另解*: $\bar{3} \equiv \overline{-1} \pmod 4$。所以 $\bar{3}^2 \equiv (\overline{-1})^2 = \overline{(-1) \cdot (-1)} = \bar{1}$。
**结论**:
经过计算，$\mathbb{Z}/4\mathbb{Z}$ 中所有元素的平方的结果只可能是 $\bar{0}$ 或 $\bar{1}$。
[总结]
这是一个基础性的结论，通过简单的穷举计算，揭示了在模4的世界里，平方数的可能性被极大地限制了。这个结论将作为后续习题的重要引理。
#### 5.6.2 习题 7
[原文]
7. 证明对于任意整数 $a$ 和 $b$，$a^{2}+b^{2}$ 除以 4 后绝不会留下余数 3。
[逐步解释]
这个问题要求证明方程 $x^2+y^2 \equiv 3 \pmod 4$ 没有整数解。
**证明**:
1. **转化问题**: “一个数除以4的余数”，就是这个数模4的结果。所以问题是证明 $a^2+b^2 \not\equiv 3 \pmod 4$。
2. **应用习题6的结论**:
* 根据习题6，我们知道任何整数的平方模4的结果只可能是0或1。
* 所以，$a^2 \pmod 4$ 的可能取值是 $\{0, 1\}$。
* 同样，$b^2 \pmod 4$ 的可能取值是 $\{0, 1\}$。
3. **分析和的可能性**:
* 我们现在要计算 $(a^2+b^2) \pmod 4$ 的所有可能性。这等价于计算 $(a^2 \pmod 4) + (b^2 \pmod 4) \pmod 4$。
* 我们有以下几种组合：
* **Case 1**: $a^2 \equiv 0 \pmod 4$ and $b^2 \equiv 0 \pmod 4$。
$a^2+b^2 \equiv 0+0 \equiv 0 \pmod 4$。
* **Case 2**: $a^2 \equiv 0 \pmod 4$ and $b^2 \equiv 1 \pmod 4$。
$a^2+b^2 \equiv 0+1 \equiv 1 \pmod 4$。
* **Case 3**: $a^2 \equiv 1 \pmod 4$ and $b^2 \equiv 0 \pmod 4$。
$a^2+b^2 \equiv 1+0 \equiv 1 \pmod 4$。
* **Case 4**: $a^2 \equiv 1 \pmod 4$ and $b^2 \equiv 1 \pmod 4$。
$a^2+b^2 \equiv 1+1 \equiv 2 \pmod 4$。
4. **结论**:
* 综上所述，两个平方数之和模4的余数只可能是 0, 1, 或 2。
* 这个结果集合 $\{0, 1, 2\}$ 中不包含 3。
* 因此，对于任意整数 $a$ 和 $b$，$a^2+b^2$ 除以4后绝不会留下余数3。证毕。
[总结]
本题是模算术用于证明“不存在性”的一个绝佳例子。通过将问题转换到模4的世界，可能的情况从无限多种（任意整数a, b）减少到极其有限的几种组合，使得我们可以通过简单的穷举来证明某个结果是永远不可能出现的。
#### 5.6.3 习题 8
[原文]
8. 证明方程 $a^{2}+b^{2}=3 c^{2}$ 在非零整数 $a, b$ 和 $c$ 中没有解。
[逐步解释]
这个问题要求证明一个丢番图方程没有非零整数解。我们将综合使用模算术和一种称为**无穷递降法 (method of infinite descent)** 的反证法技巧。
**证明**:
1. **基本假设 (反证法)**:
* 假设方程 $a^2+b^2=3c^2$ 存在一组非零整数解 $(a,b,c)$。
* **预处理**: 如果 $a,b,c$ 有一个大于1的公因子 $d$，即 $a=da', b=db', c=dc'$，那么代入方程有 $(da')^2+(db')^2 = 3(dc')^2$，即 $d^2(a'^2+b'^2)=3d^2c'^2$，可以约掉 $d^2$ 得到 $a'^2+b'^2=3c'^2$。这意味着 $(a',b',c')$ 也是一组解。我们可以不断地约去公因子，直到得到一组解 $(a_0, b_0, c_0)$，其中 $a_0, b_0, c_0$ 两两互质（或至少 $\gcd(a_0,b_0,c_0)=1$）。我们接下来就对这组“最小”的解进行分析。
2. **模4分析**:
* 我们对方程 $a_0^2+b_0^2=3c_0^2$ 两边同时取模4。
$a_0^2+b_0^2 \equiv 3c_0^2 \pmod 4$
* 根据习题6和习题7的分析，我们知道：
* 左边 $a_0^2+b_0^2 \pmod 4$ 的可能值是 $\{0, 1, 2\}$。
* 右边 $c_0^2 \pmod 4$ 的可能值是 $\{0, 1\}$，所以 $3c_0^2 \pmod 4$ 的可能值是 $3 \cdot 0 \equiv 0 \pmod 4$ 或 $3 \cdot 1 \equiv 3 \pmod 4$。
* 为了让等式成立，两边的值必须相等。唯一共同的值是0。
$a_0^2+b_0^2 \equiv 0 \pmod 4$ 并且 $3c_0^2 \equiv 0 \pmod 4$
3. **推导解的性质**:
* 从 $3c_0^2 \equiv 0 \pmod 4$ 出发：因为3和4互质，所以这必然要求 $c_0^2 \equiv 0 \pmod 4$。根据习题6的分析，这意味着 $c_0$ 必须是一个偶数。
* 从 $a_0^2+b_0^2 \equiv 0 \pmod 4$ 出发：根据习题7的分析，两个平方数之和为0，只有一种可能：$a_0^2 \equiv 0 \pmod 4$ 并且 $b_0^2 \equiv 0 \pmod 4$。这意味着 $a_0$ 和 $b_0$ 也都必须是偶数。
4. **无穷递降**:
* 我们得出了一个结论：如果存在解 $(a_0, b_0, c_0)$，那么 $a_0, b_0, c_0$ 都必须是偶数。
* 这与我们在步骤1做的预处理——假设 $\gcd(a_0,b_0,c_0)=1$——相矛盾！因为如果它们都是偶数，它们至少有公因子2。
* 这个矛盾已经足以完成证明。
* **无穷递降的表述**: 或者，我们可以不预设互质。我们只知道，如果 $(a,b,c)$ 是一组非零整数解，那么它们必全是偶数。设 $a=2a_1, b=2b_1, c=2c_1$。代入原方程：
$(2a_1)^2 + (2b_1)^2 = 3(2c_1)^2$
$4a_1^2 + 4b_1^2 = 3(4c_1^2)$
$a_1^2 + b_1^2 = 3c_1^2$
* 这表明 $(a_1,b_1,c_1)$ 也是方程的一组整数解。因为 $a,b,c$ 非零，所以 $a_1,b_1,c_1$ 也非零。并且 $|a_1|<|a|, |b_1|<|b|, |c_1|<|c|$。
* 我们可以对 $(a_1,b_1,c_1)$ 重复同样的推理，发现它们也必须是偶数，从而得到更小的一组解 $(a_2,b_2,c_2)$。
* 这个过程可以无限地进行下去，产生一个无穷递减的正整数序列 $|a| > |a_1| > |a_2| > \ldots > 0$。这是不可能的，因为正整数不能无限递减。
* 这个矛盾说明我们最初的假设“存在非零整数解”是错误的。
**结论**:
方程 $a^{2}+b^{2}=3 c^{2}$ 在非零整数中没有解。
[总结]
这个习题是数论中一个非常漂亮的证明。它首先使用模算术（模4）作为“探测器”，迅速地发现了任何可能解所必须具备的结构（必须都是偶数）。然后利用这个结构，通过无穷递降法，构造出一个逻辑上的矛盾，从而证明解根本不存在。
### 5.7 习题 9
[原文]
9. 证明任何奇数的平方除以 8 后总是留下余数 1。
[逐步解释]
这个问题要求证明：如果 $a$ 是一个奇数，那么 $a^2 \equiv 1 \pmod 8$。
**证明方法一：代数表示法**
1. 任何一个奇数 $a$ 都可以表示为 $a = 2k+1$ 的形式，其中 $k$ 是一个整数。
2. 我们来计算它的平方：
$a^2 = (2k+1)^2 = (2k)^2 + 2(2k)(1) + 1^2 = 4k^2 + 4k + 1$
3. 我们从前两项中提取公因子 $4k$：
$a^2 = 4k(k+1) + 1$
4. 现在关键是分析 $k(k+1)$ 这一项。$k$ 和 $k+1$ 是两个连续的整数。
5. 在任何两个连续整数中，必然有一个是偶数。
* 如果 $k$ 是偶数，则 $k(k+1)$ 是偶数。
* 如果 $k$ 是奇数，则 $k+1$ 是偶数，所以 $k(k+1)$ 也是偶数。
6. 因此，$k(k+1)$ 总是可以表示为 $2m$ 的形式，其中 $m$ 是一个整数。
7. 将 $k(k+1) = 2m$ 代入步骤3的表达式中：
$a^2 = 4(2m) + 1 = 8m + 1$
8. 根据同余的定义，$a^2 = 8m+1$ 意味着 $a^2-1 = 8m$，即 $8 \mid (a^2-1)$。
9. 这正是 $a^2 \equiv 1 \pmod 8$ 的定义。证毕。
**证明方法二：模8穷举法**
1. 我们想在模8的世界里证明这个结论。
2. 在 $\mathbb{Z}/8\mathbb{Z}$ 中，代表奇数的类是 $\bar{1}, \bar{3}, \bar{5}, \bar{7}$。
3. 我们只需检查这四个类的平方即可：
* $\bar{1}^2 = \overline{1 \cdot 1} = \bar{1}$
* $\bar{3}^2 = \overline{3 \cdot 3} = \bar{9} = \overline{1 \cdot 8 + 1} = \bar{1}$
* $\bar{5}^2 = \overline{5 \cdot 5} = \overline{25} = \overline{3 \cdot 8 + 1} = \bar{1}$
* $\bar{7}^2 = \overline{7 \cdot 7} = \overline{49} = \overline{6 \cdot 8 + 1} = \bar{1}$
4. 所有代表奇数的类的平方结果都是 $\bar{1}$。
5. 因此，任何奇数的平方模8都同余于1。
[总结]
本题揭示了平方数在模8下的一个重要性质。两种证明方法从不同角度说明了问题：代数法更具一般性，揭示了其背后的结构性原因（连续整数必有一偶）；而穷举法则更直观，直接在模8的世界里验证了结论。
### 5.8 习题 10-14 (一组关于 $(\mathbb{Z}/n\mathbb{Z})^\times$ 的证明)
#### 5.8.1 习题 10
[原文]
10. 证明 $(\mathbb{Z} / n \mathbb{Z})^{\times}$ 的元素个数是 $\varphi(n)$，其中 $\varphi$ 表示欧拉 $\varphi$ 函数。
[逐步解释]
这个问题要求我们将代数对象 $(\mathbb{Z}/n\mathbb{Z})^\times$ 的大小（即其基数，cardinality）与数论函数 $\varphi(n)$ 联系起来。
**证明**:
1. **回顾定义**:
* **$(\mathbb{Z}/n\mathbb{Z})^\times$**: 根据命题4，这个集合是 $\mathbb{Z}/n\mathbb{Z}$ 中所有满足其代表元与 $n$ 互质的类的集合。
$(\mathbb{Z}/n\mathbb{Z})^\times = \{\bar{a} \in \mathbb{Z}/n\mathbb{Z} \mid \gcd(a,n)=1 \}$
* **欧拉 $\varphi$ 函数 (Euler's totient function)**: $\varphi(n)$ 的定义是：在从1到$n$的整数中，与$n$互质的数的个数。
$\varphi(n) = |\{ a \in \mathbb{Z} \mid 1 \le a \le n, \gcd(a,n)=1 \}|$ (其中 $|S|$ 表示集合 $S$ 的元素个数)。
2. **建立一一对应关系 (Bijection)**:
* 我们要证明 $|(\mathbb{Z}/n\mathbb{Z})^\times| = \varphi(n)$。
* 考虑两个集合：
* $A = (\mathbb{Z}/n\mathbb{Z})^\times = \{\bar{a} \in \mathbb{Z}/n\mathbb{Z} \mid \gcd(a,n)=1 \}$
* $B = \{ a \in \mathbb{Z} \mid 1 \le a \le n, \gcd(a,n)=1 \}$
* 根据 $\varphi(n)$ 的定义，我们有 $|B| = \varphi(n)$。
* 我们再来分析集合 $A$。$\mathbb{Z}/n\mathbb{Z}$ 的元素可以由 $\{\overline{0}, \overline{1}, \ldots, \overline{n-1}\}$ 来唯一代表。所以，要找 $A$ 中的元素，我们只需要检查 $\bar{a}$ (其中 $a \in \{0, 1, \ldots, n-1\}$) 哪个满足 $\gcd(a,n)=1$。
* $\gcd(0,n)=n$，当 $n>1$ 时不为1，所以 $\bar{0}$ 不在 $A$ 中。
* $\gcd(n,n)=n$，所以当用 $1, \ldots, n$ 作为代表时，代表 $n$ 的类 $\bar{n}=\bar{0}$ 也不在 $A$ 中。
* 因此，集合 $A$ 可以被精确地描述为：
$A = \{\bar{a} \mid a \in \{1, 2, \ldots, n-1\}, \gcd(a,n)=1\}$
（如果 $n$ 是合数，有些 $a$ 也不在里面；如果 $n$ 是素数，则 $1, \ldots, n-1$ 都在里面）。
* 现在我们看集合 $A$ 的代表元 $\{a \mid \bar{a} \in A\}$ 和集合 $B$。
* $A$ 的标准代表元集合是 $\{a \mid 1 \le a < n, \gcd(a,n)=1\}$。
* $B$ 是 $\{a \mid 1 \le a \le n, \gcd(a,n)=1\}$。
* 这两个集合几乎一样，唯一的区别是 $B$ 可能包含 $n$。但只有当 $n=1$ 时, $\gcd(1,1)=1$, $n$ 才会在 $B$ 中。
* 当 $n>1$ 时，$\gcd(n,n)=n \neq 1$，所以 $n$ 不在 $B$ 中。此时 $B = \{a \in \mathbb{Z} \mid 1 \le a < n, \gcd(a,n)=1\}$。
* 在这种情况下，集合 $B$ 和构成 $(\mathbb{Z}/n\mathbb{Z})^\times$ 的标准代表元集合是完全相同的。
* 因为 $(\mathbb{Z}/n\mathbb{Z})^\times$ 中的每一个元素都由一个唯一的标准代表元 $a \in \{1, \ldots, n-1\}$ 来标识，所以 $(\mathbb{Z}/n\mathbb{Z})^\times$ 的元素个数就等于其标准代表元的个数。
* $|(\mathbb{Z}/n\mathbb{Z})^\times| = |\{a \mid 1 \le a < n, \gcd(a,n)=1\}| = |B| = \varphi(n)$。
**结论**:
$(\mathbb{Z}/n\mathbb{Z})^\times$ 的元素个数，根据其定义（由与n互质的数的类构成）和欧拉函数的定义（与n互质的数的个数），两者是完全一致的。
[总结]
本题在代数结构 $(\mathbb{Z}/n\mathbb{Z})^\times$ 和数论函数 $\varphi(n)$ 之间建立了一座直接的桥梁，告诉我们这个重要的代数群的大小，可以通过一个纯数论的函数来计算。这是两个数学分支交叉的一个基本而重要的例子。
#### 5.8.2 习题 11
[原文]
11. 证明如果 $\bar{a}, \bar{b} \in(\mathbb{Z} / n \mathbb{Z})^{\times}$，那么 $\bar{a} \cdot \bar{b} \in(\mathbb{Z} / n \mathbb{Z})^{\times}$。
[逐步解释]
这个问题要求证明 $(\mathbb{Z}/n\mathbb{Z})^\times$ 这个集合在乘法运算下是**封闭 (closed)** 的。这是证明一个代数结构是**群 (Group)** 的第一步（群公理之一）。
**证明方法一：使用逆元的定义**
1. **前提**:
* $\bar{a} \in (\mathbb{Z}/n\mathbb{Z})^\times$ 意味着存在一个元素 $\bar{a}^{-1}$ 使得 $\bar{a} \cdot \bar{a}^{-1} = \bar{1}$。
* $\bar{b} \in (\mathbb{Z}/n\mathbb{Z})^\times$ 意味着存在一个元素 $\bar{b}^{-1}$ 使得 $\bar{b} \cdot \bar{b}^{-1} = \bar{1}$。
2. **目标**:
* 我们要证明 $\bar{a} \cdot \bar{b}$ 也是可逆的，即我们要为它找到一个乘法逆元。
3. **构造逆元**:
* 让我们猜测一下 $\bar{a}\bar{b}$ 的逆元可能是什么。受到矩阵求逆 $(AB)^{-1}=B^{-1}A^{-1}$ 的启发，我们尝试一下 $\bar{b}^{-1}\bar{a}^{-1}$。
* 计算 $(\bar{a}\bar{b}) \cdot (\bar{b}^{-1}\bar{a}^{-1})$:
$(\bar{a}\bar{b}) \cdot (\bar{b}^{-1}\bar{a}^{-1}) = \bar{a} \cdot (\bar{b} \cdot \bar{b}^{-1}) \cdot \bar{a}^{-1}$ (乘法结合律)
$= \bar{a} \cdot (\bar{1}) \cdot \bar{a}^{-1}$ (根据 $\bar{b}^{-1}$ 的定义)
$= \bar{a} \cdot \bar{a}^{-1}$ ($\bar{1}$ 是乘法单位元)
$= \bar{1}$ (根据 $\bar{a}^{-1}$ 的定义)
4. **结论**:
* 我们成功地为元素 $\bar{a}\bar{b}$ 找到了一个乘法逆元，即 $\bar{b}^{-1}\bar{a}^{-1}$。
* 根据可逆元的定义，既然 $\bar{a}\bar{b}$ 有逆元，那么它就属于 $(\mathbb{Z}/n\mathbb{Z})^\times$。证毕。
**证明方法二：使用命题4（互质性）**
1. **前提**:
* $\bar{a} \in (\mathbb{Z}/n\mathbb{Z})^\times$ 根据命题4，等价于 $\gcd(a,n)=1$。
* $\bar{b} \in (\mathbb{Z}/n\mathbb{Z})^\times$ 根据命题4，等价于 $\gcd(b,n)=1$。
2. **目标**:
* 我们要证明 $\bar{a}\bar{b} \in (\mathbb{Z}/n\mathbb{Z})^\times$，根据命题4，这等价于证明 $\gcd(ab, n)=1$。
3. **应用数论性质**:
* 这是一个基础的数论事实：如果一个整数 $n$ 与整数 $a$ 和 $b$ 都互质，那么 $n$ 也与它们的乘积 $ab$ 互质。
* **简要证明这个事实**: 假设 $\gcd(ab, n) = d > 1$。那么存在一个素数 $p$ 整除 $d$。所以 $p \mid ab$ 且 $p \mid n$。根据欧几里得引理，如果一个素数 $p$ 整除乘积 $ab$，那么它至少整除 $a$ 或 $b$ 中的一个。
* 如果 $p \mid a$，那么 $p$ 就是 $a$ 和 $n$ 的一个公因子。这导致 $\gcd(a,n) \ge p > 1$，与前提 $\gcd(a,n)=1$ 矛盾。
* 如果 $p \mid b$，那么 $p$ 就是 $b$ 和 $n$ 的一个公因子。这导致 $\gcd(b,n) \ge p > 1$，与前提 $\gcd(b,n)=1$ 矛盾。
* 因为所有情况都导出矛盾，所以我们的假设 $\gcd(ab,n)>1$ 是错误的。因此必须有 $\gcd(ab,n)=1$。
4. **结论**:
* 既然 $\gcd(ab,n)=1$，根据命题4，元素 $\overline{ab} = \bar{a}\bar{b}$ 就在 $(\mathbb{Z}/n\mathbb{Z})^\times$ 中。证毕。
[总结]
本题证明了可逆元集合 $(\mathbb{Z}/n\mathbb{Z})^\times$ 对于乘法运算是封闭的。这个性质是该集合能够构成一个独立的、自洽的代数系统（一个**群**）的先决条件。两种证明方法分别从代数（构造逆元）和数论（利用互质性）的角度阐明了这一点。
#### 5.8.3 习题 12 & 13 & 14
这三个习题共同构成了对核心结论**命题4**的完整证明。我们将它们合并解释。
**命题4**: $(\mathbb{Z} / n \mathbb{Z})^{\times}=\{\bar{a} \in \mathbb{Z} / n \mathbb{Z} \mid(a, n)=1\}$。
这是一个集合相等性的命题，需要从两个方向证明：
1. **($\subseteq$) (习题12的思路)**: 证明如果 $\bar{a}$ 是可逆元，那么 $\gcd(a,n)=1$。
2. **($\supseteq$) (习题13的思路)**: 证明如果 $\gcd(a,n)=1$，那么 $\bar{a}$ 是可逆元。
---
**习题 13: ( $\supseteq$ 方向, "if $\gcd(a,n)=1$, then $\bar{a}$ is a unit")**
[原文]
13. 令 $n \in \mathbb{Z}, n>1$，且令 $a \in \mathbb{Z}$ 满足 $1 \leq a \leq n$。证明如果 $a$ 和 $n$ 互质，则存在一个整数 $c$ 使得 $a c \equiv 1(\bmod n) \lambda$ [使用两个整数的最大公约数是这些整数的 $\mathbb{Z}$-线性组合这一事实]。
[逐步解释]
1. **前提**: $a$ 和 $n$ 互质，即 $\gcd(a,n)=1$。
2. **使用的工具 (贝祖定理)**: 题目明确提示，我们要使用“最大公约数可以表示为两数的线性组合”这一事实。即，对于整数 $a, n$，存在整数 $x, y$ 使得 $ax+ny = \gcd(a,n)$。
3. **应用工具**: 将我们的前提代入贝祖定理，得到：存在整数 $x, y$ 使得 $ax+ny=1$。
4. **模n变换**: 我们观察这个等式在模$n$的世界里是什么样的。对等式两边取模$n$：
$(ax+ny) \equiv 1 \pmod n$
5. 由于 $ny$ 是 $n$ 的整数倍，所以 $ny \equiv 0 \pmod n$。
6. 方程简化为：$ax \equiv 1 \pmod n$。
7. **结论**: 我们已经找到了一个整数 $c$（就是这里的 $x$），使得 $ac \equiv 1 \pmod n$。根据乘法逆元的定义，这意味着 $\bar{a}$ 在 $\mathbb{Z}/n\mathbb{Z}$ 中是可逆的（其逆元是 $\bar{x}$）。证毕。
---
**习题 12: ( $\subseteq$ 方向, "if $\bar{a}$ is a unit, then $\gcd(a,n)=1$")**
这个方向通常通过证明其**逆否命题**来完成，这正是习题12的表述。
**逆否命题**: 如果 $\gcd(a,n) \neq 1$，那么 $\bar{a}$ 不是可逆元。
[原文]
12. 令 $n \in \mathbb{Z}, n>1$，且令 $a \in \mathbb{Z}$ 满足 $1 \leq a \leq n$。证明如果 $a$ 和 $n$ 不互质，则存在一个整数 $b$ 满足 $1 \leq b<n$ 使得 $a b \equiv 0(\bmod n)$，并推断出不存在整数 $c$ 使得 $a c \equiv 1(\bmod n)$。
[逐步解释]
1. **前提**: $a$ 和 $n$ 不互质。即 $\gcd(a,n) = d > 1$。
2. **构造特殊的整数 $b$**:
* 题目让我们找一个 $b$ 使得 $ab \equiv 0 \pmod n$。
* 让我们定义 $b = n/d$。
* 因为 $d>1$，所以 $b = n/d < n$。因为 $d \le n$，所以 $b=n/d \ge 1$。因此 $1 \le b < n$ 成立。
3. **计算 $ab$**:
* $ab = a \cdot (n/d) = (a/d) \cdot n$。
* 因为 $d=\gcd(a,n)$，所以 $d$ 是 $a$ 的一个因子，即 $a/d$ 是一个整数。
* 所以，乘积 $ab$ 是 $n$ 的一个整数倍。
4. **得出同余式**:
* $ab = (\text{integer}) \cdot n$ 意味着 $ab \equiv 0 \pmod n$。
* 在剩余类的语言中，这表示 $\bar{a} \cdot \bar{b} = \bar{0}$。
* 因为 $b \neq 0$ (由于 $b \ge 1$)，所以 $\bar{b} \neq \bar{0}$。
* 我们称这样的 $\bar{a}$ 为**零因子 (zero divisor)**，因为它与一个非零元素相乘得到了零。
5. **推断出 $\bar{a}$ 不可逆 (反证法)**:
* 现在我们来证明这个零因子 $\bar{a}$ 不可能是可逆元。
* 假设 $\bar{a}$ 是可逆的，那么存在一个逆元 $\bar{c}$ 使得 $\bar{a}\bar{c} = \bar{c}\bar{a} = \bar{1}$。
* 我们取刚刚得到的等式 $\bar{a}\bar{b} = \bar{0}$。
* 用 $\bar{c}$ 乘等式两边：
$\bar{c} \cdot (\bar{a}\bar{b}) = \bar{c} \cdot \bar{0}$
* **分析左边**:
$\bar{c} \cdot (\bar{a}\bar{b}) = (\bar{c}\bar{a})\bar{b}$ (结合律)
$= (\bar{1})\bar{b}$ (根据 $\bar{c}$ 是逆元的定义)
$= \bar{b}$
* **分析右边**:
$\bar{c} \cdot \bar{0} = \overline{c \cdot 0} = \bar{0}$
* **得出矛盾**:
所以，我们得到 $\bar{b} = \bar{0}$。但这与我们之前确定的 $1 \le b < n$ (即 $\bar{b}$ 不是 $\bar{0}$) 相矛盾。
* 这个矛盾说明我们的假设“$\bar{a}$ 是可逆的”是错误的。
---
**习题 14: 总结与验证**
[原文]
14. 从前两个习题得出结论，$(\mathbb{Z} / n \mathbb{Z})^{\times}$ 是 $\mathbb{Z} / n \mathbb{Z}$ 中满足 $(a, n)=1$ 的元素 $\bar{a}$ 的集合，从而证明命题 4。在 $n=12$ 的情况下直接验证这一点。
[逐步解释]
1. **总结证明**:
* 习题13证明了：如果 $\gcd(a,n)=1$，那么 $\bar{a} \in (\mathbb{Z}/n\mathbb{Z})^\times$。这可以写成集合的包含关系：$\{\bar{a} \mid \gcd(a,n)=1\} \subseteq (\mathbb{Z}/n\mathbb{Z})^\times$。
* 习题12证明了：如果 $\gcd(a,n) \neq 1$，那么 $\bar{a} \notin (\mathbb{Z}/n\mathbb{Z})^\times$。这等价于说，如果一个元素在 $(\mathbb{Z}/n\mathbb{Z})^\times$ 中，那么它的代表元必须满足 $\gcd(a,n)=1$。这可以写成：$(\mathbb{Z}/n\mathbb{Z})^\times \subseteq \{\bar{a} \mid \gcd(a,n)=1\}$。
* 两个方向的包含关系都成立，因此两个集合是相等的。命题4得证。
2. **验证 $n=12$**:
* 我们要验证 $(\mathbb{Z}/12\mathbb{Z})^\times = \{\bar{a} \mid \gcd(a,12)=1\}$。
* **计算右边集合**: 在 $\{1, \ldots, 12\}$ 中，与12互质的数有哪些？
* $\gcd(1,12)=1$
* $\gcd(2,12)=2$
* $\gcd(3,12)=3$
* $\gcd(4,12)=4$
* $\gcd(5,12)=1$
* $\gcd(6,12)=6$
* $\gcd(7,12)=1$
* $\gcd(8,12)=4$
* $\gcd(9,12)=3$
* $\gcd(10,12)=2$
* $\gcd(11,12)=1$
* $\gcd(12,12)=12$
* 所以与12互质的数是 $1, 5, 7, 11$。右边集合是 $\{\bar{1}, \bar{5}, \bar{7}, \overline{11}\}$。
* **计算左边集合 (直接找逆元)**:
* $\bar{1}$: $\bar{1} \cdot \bar{1} = \bar{1}$。可逆。
* $\bar{2}$: 是零因子，因为 $\bar{2}\cdot\bar{6}=\overline{12}=\bar{0}$。不可逆。
* $\bar{3}$: 是零因子，因为 $\bar{3}\cdot\bar{4}=\overline{12}=\bar{0}$。不可逆。
* $\bar{4}$: 是零因子，因为 $\bar{4}\cdot\bar{3}=\overline{12}=\bar{0}$。不可逆。
* $\bar{5}$: $\bar{5}\cdot\bar{5}=\overline{25}=\bar{1}$。可逆。
* $\bar{6}$: 是零因子，因为 $\bar{6}\cdot\bar{2}=\overline{12}=\bar{0}$。不可逆。
* $\bar{7}$: $\bar{7}\cdot\bar{7}=\overline{49}=\bar{1}$。可逆。
* $\bar{8}$: 是零因子，$\bar{8}\cdot\bar{3}=\overline{24}=\bar{0}$。不可逆。
* $\bar{9}$: 是零因子，$\bar{9}\cdot\bar{4}=\overline{36}=\bar{0}$。不可逆。
* $\overline{10}$: 是零因子，$\overline{10}\cdot\bar{6}=\overline{60}=\bar{0}$。不可逆。
* $\overline{11}$: $\overline{11}\cdot\overline{11}=\overline{121}=\bar{1}$。可逆。
* 左边集合是 $\{\bar{1}, \bar{5}, \bar{7}, \overline{11}\}$。
* 两边集合相等，验证通过。
### 5.9 习题 15
[原文]
15. 对于以下每对整数 $a$ 和 $n$，证明 $a$ 与 $n$ 互质，并确定 $\bar{a}$ 在 $\mathbb{Z} / n \mathbb{Z}$ 中的乘法逆元。
(a) $a=13, n=20$。
(b) $a=69, n=89$。
(c) $a=1891, n=3797$。
(d) $a=6003722857, n=77695236973$。
[逐步解释]
这个习题要求我们对几组具体的数字应用扩展欧几里得算法来求模逆元。
**(a) $a=13, n=20$**
1. **欧几里得算法**:
$20 = 1 \cdot 13 + 7$
$13 = 1 \cdot 7 + 6$
$7 = 1 \cdot 6 + 1$
最后一个非零余数是1，所以 $\gcd(13, 20)=1$，$a, n$ 互质。
2. **反向代入**:
$1 = 7 - 1 \cdot 6$
$1 = 7 - 1 \cdot (13 - 1 \cdot 7) = 7 - 13 + 7 = 2 \cdot 7 - 13$
$1 = 2 \cdot (20 - 1 \cdot 13) - 13 = 2 \cdot 20 - 2 \cdot 13 - 13 = 2 \cdot 20 - 3 \cdot 13$
3. **结论**:
我们得到 $(-3) \cdot 13 + 2 \cdot 20 = 1$。
这意味着 $-3 \cdot 13 \equiv 1 \pmod{20}$。
$\overline{13}$ 的逆元是 $\overline{-3}$。
约化到正数: $\overline{-3} = \overline{-3+20} = \overline{17}$。
**逆元是 $\overline{17}$**。
**(b) $a=69, n=89$**
1. **欧几里得算法**:
$89 = 1 \cdot 69 + 20$
$69 = 3 \cdot 20 + 9$
$20 = 2 \cdot 9 + 2$
$9 = 4 \cdot 2 + 1$
$\gcd(69, 89)=1$，$a, n$ 互质。
2. **反向代入**:
$1 = 9 - 4 \cdot 2$
$1 = 9 - 4 \cdot (20 - 2 \cdot 9) = 9 - 4 \cdot 20 + 8 \cdot 9 = 9 \cdot 9 - 4 \cdot 20$
$1 = 9 \cdot (69 - 3 \cdot 20) - 4 \cdot 20 = 9 \cdot 69 - 27 \cdot 20 - 4 \cdot 20 = 9 \cdot 69 - 31 \cdot 20$
$1 = 9 \cdot 69 - 31 \cdot (89 - 1 \cdot 69) = 9 \cdot 69 - 31 \cdot 89 + 31 \cdot 69 = 40 \cdot 69 - 31 \cdot 89$
3. **结论**:
我们得到 $40 \cdot 69 - 31 \cdot 89 = 1$。
这意味着 $40 \cdot 69 \equiv 1 \pmod{89}$。
**逆元是 $\overline{40}$**。
**(c) $a=1891, n=3797$**
1. **欧几里得算法**:
$3797 = 2 \cdot 1891 + 15$
$1891 = 126 \cdot 15 + 1$
$\gcd(1891, 3797)=1$，$a, n$ 互质。
2. **反向代入**:
$1 = 1891 - 126 \cdot 15$
$1 = 1891 - 126 \cdot (3797 - 2 \cdot 1891) = 1891 - 126 \cdot 3797 + 252 \cdot 1891$
$1 = (1+252) \cdot 1891 - 126 \cdot 3797 = 253 \cdot 1891 - 126 \cdot 3797$
3. **结论**:
我们得到 $253 \cdot 1891 - 126 \cdot 3797 = 1$。
这意味着 $253 \cdot 1891 \equiv 1 \pmod{3797}$。
**逆元是 $\overline{253}$**。
**(d) $a=6003722857, n=77695236973$**
1. **欧几里得算法**:
$77695236973 = 12 \cdot 6003722857 + 5650562689$
$6003722857 = 1 \cdot 5650562689 + 353160168$
$5650562689 = 16 \cdot 353160168 + 1$
$\gcd(a, n)=1$，$a, n$ 互质。
2. **反向代入**:
$1 = 5650562689 - 16 \cdot 353160168$
$1 = 5650562689 - 16 \cdot (6003722857 - 1 \cdot 5650562689) = 17 \cdot 5650562689 - 16 \cdot 6003722857$
$1 = 17 \cdot (77695236973 - 12 \cdot 6003722857) - 16 \cdot 6003722857$
$1 = 17 \cdot 77695236973 - 204 \cdot 6003722857 - 16 \cdot 6003722857$
$1 = 17 \cdot 77695236973 - 220 \cdot 6003722857$
3. **结论**:
我们得到 $(-220) \cdot 6003722857 + 17 \cdot 77695236973 = 1$。
这意味着 $-220 \cdot a \equiv 1 \pmod n$。
逆元是 $\overline{-220}$。
约化到正数: $\overline{-220} = \overline{-220 + 77695236973} = \overline{77695236753}$。
**逆元是 $\overline{77695236753}$**。
### 5.10 习题 16
[原文]
16. 编写一个计算机程序，用于对任意给定输入 $n$ 进行模 $n$ 的加法和乘法运算。这些运算的输出应为两个整数之和与积的最小剩余。此外，还要包含一个功能，即如果 $(a, n)=1$，可以根据请求打印一个在 1 到 $n-1$ 之间的整数 $c$ 使得 $\bar{a} \cdot \bar{c}=\overline{1}$。（你的程序当然不应简单地引用许多系统中内置的“mod”函数）。
[逐步解释]
这个习题要求我们将本章的算术理论转化为实际的代码。程序需要实现三个核心功能：模加法、模乘法和模逆元计算。
**功能1 & 2: 模加法和模乘法**
* **输入**: 整数 $a$, $b$ 和模数 $n$。
* **操作**:
* 加法: 计算 $s = a+b$。
* 乘法: 计算 $p = a \cdot b$。
* **输出**: 计算结果的最小非负剩余。
* **伪代码/实现思路**:
* 内置的 `%` 运算符在很多语言（如C++, Java）中对于负数的操作是“取余”而不是“取模”，结果的符号与被除数相同。例如 `(-7) % 5` 结果是 `-2` 而不是 `3`。我们需要一个健壮的 `mod` 函数。
```
function robust_mod(value, modulus):
// C-style % operator can yield negative result
result = value % modulus
if result < 0:
result = result + modulus
return result
function modular_add(a, b, n):
// It's better to mod a and b first to prevent overflow if they are large
val_a = robust_mod(a, n)
val_b = robust_mod(b, n)
sum_val = val_a + val_b
return robust_mod(sum_val, n)
function modular_multiply(a, b, n):
val_a = robust_mod(a, n)
val_b = robust_mod(b, n)
// For very large n, a*b might overflow standard integer types.
// In that case, one needs to use algorithms for modular multiplication
// for large numbers. For standard int sizes, this is fine.
prod_val = val_a * val_b
return robust_mod(prod_val, n)
```
**功能3: 模逆元计算**
* **输入**: 整数 $a$ 和模数 $n$。
* **操作**: 使用扩展欧几里得算法计算 $a$ 模 $n$ 的逆元。
* **输出**: 如果逆元存在，输出一个在 $1$到 $n-1$ 之间的整数 $c$。如果不存在，报告错误。
* **伪代码/实现思路**:
* 我们需要一个实现扩展欧几里得算法的函数。这个函数通常返回一个包含最大公约数以及贝祖等式系数 $(x, y)$ 的元组。
```
// Returns a tuple (gcd, x, y) such that ax + by = gcd(a, b)
function extended_euclidean_algorithm(a, b):
if a == 0:
return (b, 0, 1)
else:
(gcd, x, y) = extended_euclidean_algorithm(b % a, a)
// From b%a*x + a*y = gcd
// (b - floor(b/a)*a)*x + a*y = gcd
// b*x - floor(b/a)*a*x + a*y = gcd
// a*(y - floor(b/a)*x) + b*x = gcd
return (gcd, y - (b // a) * x, x)
function modular_inverse(a, n):
(gcd, x, y) = extended_euclidean_algorithm(a, n)
if gcd != 1:
// Inverse does not exist
return "Error: Inverse does not exist."
else:
// x is the inverse of a mod n.
// We need to return the smallest positive representative.
return robust_mod(x, n)
```
[总结]
这个编程练习是将抽象代数理论付诸实践的绝佳方式。它要求程序员不仅要理解算法的步骤，还要处理好编程语言中与数学定义不完全一致的细节（如 `%` 运算符的行为），并设计出健壮、正确的函数接口。这是从理论数学家到应用数学家或密码学工程师转变所必需的技能。
# 行间公式索引
1. $$ a \sim b \text { 当且仅当 } n \mid(b-a) .
$$
解释: 定义了整数 $a$ 和 $b$ 之间“模 $n$ 相关”的关系，即它们的差能被 $n$ 整除。
2. $$
\begin{aligned}
\bar{a} & =\{a+k n \mid k \in \mathbb{Z}\} \\
& =\{a, a \pm n, a \pm 2 n, a \pm 3 n, \ldots\} .
\end{aligned}
$$
**解释**: 定义了整数 $a$ 的剩余类（或同余类）$\bar{a}$，它是一个包含了所有与 $a$ 相差 $n$ 的整数倍的数的无限集合。
3. $$ \overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}
$$
解释: 列出了模 $n$ 的所有 $n$ 个不同的剩余类，它们构成了集合 $\mathbb{Z}/n\mathbb{Z}$。
4.
$$
\bar{a}+\bar{b}=\overline{a+b} \quad \text { 和 } \quad \bar{a} \cdot \bar{b}=\overline{a b} .
$$
解释: 定义了剩余类之间的加法和乘法运算，其核心思想是利用代表元在整数环中进行运算，然后取结果所在的类。
5.
$$
\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{11}
$$
解释: 示例，列出了模12的所有12个剩余类。
6.
$$
a_{1} \equiv b_{1} \quad(\bmod n) \quad \text { 且 } \quad a_{2} \equiv b_{2} \quad(\bmod n)
$$
解释: 定理3的前提条件，假设两组代表元分别对应同一个类。
7.
$$
a_{1}+a_{2} \equiv b_{1}+b_{2} \quad(\bmod n) \quad \text { 且 } \quad a_{1} a_{2} \equiv b_{1} b_{2} \quad(\bmod n) .
$$
解释: 定理3的结论，证明了同余关系在整数加法和乘法下是保持的，从而保证了类运算的良定义性。
8.
$$
(\mathbb{Z} / n \mathbb{Z})^{\times}=\{\bar{a} \in \mathbb{Z} / n \mathbb{Z} \mid \text { 存在 } \bar{c} \in \mathbb{Z} / n \mathbb{Z} \text { 使得 } \bar{a} \cdot \bar{c}=\overline{1}\} .
$$
解释: 定义了模 $n$ 的乘法群（或单位群）$(\mathbb{Z}/n\mathbb{Z})^\times$，它由 $\mathbb{Z}/n\mathbb{Z}$ 中所有存在乘法逆元的元素构成。
9. $$
\begin{aligned}
60 & =(3) 17+9 \\
17 & =(1) 9+8 \\
9 & =(1) 8+1
\end{aligned}
$$
**解释**: 示例，展示了使用欧几里得算法计算 $\gcd(60, 17)$ 的过程。
$$