1. 0.2 整数的性质

这段话是引言，它告诉我们接下来要讲的内容是关于整数的基本性质。这里的整数集合用符号 $\mathbb{Z}$ 表示，它包括所有正整数、负整数和零（..., -3, -2, -1, 0, 1, 2, 3, ...）。这些性质可能我们在小学和中学数学中已经学过，比如加减乘除、质数、公约数等。作者提到，这些性质虽然看起来很基础，但它们在更高级的数学理论——环论（将在本书第 8 章学习）——中会得到更普遍、更抽象的证明。但是，在学习前面的章节（也就是第一部分，主要关于群论）时，我们需要先直接使用这些性质作为已知事实。同时，作者特意强调，后面环论中对这些整数性质的证明，不会反过来依赖于我们现在要学习的群论知识。这保证了整个理论体系的逻辑是自洽的，没有循环论证。简而言之，就是“我们先用着这些工具，后面再告诉你这些工具的原理，并且造工具的过程没用我们现在要干的活儿”。

这条性质叫做良序性，也叫良序原理（Well-Ordering Principle）。它只针对正整数集合 $\mathbb{Z}^{+}$。

• $\mathbb{Z}^{+}$：这是指所有正整数的集合，即 $\{1, 2, 3, 4, ...\}$。注意，它不包括 0 和负整数。
• 非空子集 $A$：意思是 $A$ 是 $\mathbb{Z}^{+}$ 的一部分，并且 $A$ 里面至少有一个元素。例如，$A=\{5, 2, 8\}$ 就是 $\mathbb{Z}^{+}$ 的一个非空子集。$A=\{10, 20, 30, ...\}$ 也是。
• 存在某个元素 $m \in A$：这句话的意思是，我们一定能在集合 $A$ 内部找到一个特殊的元素，我们叫它 $m$。
• 使得对于所有 $a \in A$，都有 $m \leq a$：这个特殊元素 $m$ 的特点是，它小于或等于 $A$ 中的任何一个元素（包括它自己）。换句话说，它就是 $A$ 中最小的那个数。
• $m$ 称为 $A$ 的最小元素：这就是给这个特殊的 $m$ 起的名字。

所以，整句话连起来的意思就是：任何一堆不为空的正整数集合，里面一定有一个最小的数。

这个性质看起来非常理所当然，但它却是数学归纳法等重要证明方法的基础，是一个非常深刻的公理。

这里定义了数学中一个非常核心的概念：整除。

• 如果 $a, b \in \mathbb{Z}$ 且 $a \neq 0$：这句话设定了前提条件。我们讨论的两个数 $a$ 和 $b$ 都必须是整数。特别重要的是，用来做除数的 $a$ 不能是 0。这是因为在数学中，除以 0 是没有意义的。
• 如果存在一个元素 $c \in \mathbb{Z}$ 使得 $b=ac$：这是整除的核心定义。我们说“$a$ 整除 $b$”，意思就是，我们能找到一个整数 $c$，让 $a$ 乘以这个整数 $c$ 恰好等于 $b$。换句话说，$b$ 是 $a$ 的整数倍。这个整数 $c$ 就是我们常说的“商”。
• 则我们说 $a$ 整除 $b$：这是给这个关系起的名字。
• 我们记作 $a \mid b$：这是一个专门的数学符号，中间的竖线 | 就读作“整除”。所以 $a \mid b$ 读作“$a$ 整除 $b$”。
• 如果 $a$ 不整除 $b$，则记作 $a \nmid b$：这是“不整除”的符号，就是在那条竖线上加一个斜杠，表示否定。

所以，"a divides b" 意味着 b 是 a 的一个倍数，或者说 a 是 b 的一个因子。

这里定义了最大公约数，通常缩写为 g.c.d.。

• 如果 $a, b \in \mathbb{Z}-\{0\}$：前提是 $a$ 和 $b$ 都是非零整数。讨论 0 的最大公约数有时会有特殊约定，但这里为了简化，先排除了 0。
• 则存在一个唯一的正整数 $d$：这是结论。对于任意两个非零整数 $a$ 和 $b$，总能找到一个并且只有一个符合下面条件的正整数 $d$。
• 称为 $a$ 和 $b$ 的最大公约数：这是 $d$ 的名字。
• (a) $d \mid a$ 且 $d \mid b$：这是第一个条件。$d$ 必须既能整除 $a$ 又能整除 $b$。满足这个条件的数就叫做 $a$ 和 $b$ 的公约数。
• (b) 如果 $e \mid a$ 且 $e \mid b$，则 $e \mid d$：这是第二个条件，也是这个定义最精妙的地方。它说，如果还有任何其他的公约数 $e$（$e$ 也能同时整除 $a$ 和 $b$），那么这个 $e$ 必然能整除 $d$。
• （所以 $d$ 是最大的公约数）：这句话解释了为什么条件 (b) 意味着“最大”。在整除的世界里，“能被所有同类整除”的那个数就是“最大”的。如果 $e \mid d$，那么 $|e| \leq |d|$（因为 $d=ec$，对于非零整数 $e,c$，则 $|d|=|e||c| \ge |e|$）。所以，任何其他的公约数 $e$ 的绝对值都不会超过 $d$。由于我们规定 $d$ 是正数，所以 $d$ 确实是所有公约数中数值最大的那个。这个定义比“数值上最大”更深刻，因为它用“整除”关系来定义“最大”，这在更抽象的代数结构中依然有效。
• 记作 $(a, b)$：这是最大公约数的标准符号。例如，12 和 18 的最大公约数是 6，记作 $(12, 18) = 6$。
• 如果 $(a, b)=1$，我们称 $a$ 和 $b$ 是互素的：这是一个非常重要的特殊情况。如果两个数的最大公约数是 1，意味着它们除了 1 和 -1 之外，没有其他共同的因子。这样的两个数关系很“纯净”，因此称它们为互素或互质。

这里定义了与最大公约数相对偶的概念：最小公倍数，缩写为 l.c.m.。

• 如果 $a, b \in \mathbb{Z}-\{0\}$：前提同样是两个非零整数。
• 则存在一个唯一的正整数 $l$：结论是，对于 $a$ 和 $b$，总能找到一个且仅有一个满足下面条件的正整数 $l$。
• 称为 $a$ 和 $b$ 的最小公倍数：这是 $l$ 的名字。
• (a) $a \mid l$ 且 $b \mid l$：这是第一个条件。$l$ 必须既能被 $a$ 整除，也能被 $b$ 整除。也就是说，$l$ 是 $a$ 和 $b$ 的公倍数。
• (b) 如果 $a \mid m$ 且 $b \mid m$，则 $l \mid m$：这是第二个条件，和 g.c.d. 的定义非常对称。它说，如果还有任何其他的公倍数 $m$（$m$ 也能同时被 $a$ 和 $b$ 整除），那么这个 $m$ 必然能被 $l$ 整除（即 $m$ 是 $l$ 的倍数）。
• （所以 $l$ 是最小的公倍数）：这句话解释了为什么条件(b)意味着“最小”。如果任何其他公倍数 $m$ 都是 $l$ 的倍数，那么 $|m| \ge |l|$。由于我们规定 $l$ 是正数，那么 $l$ 就是所有正的公倍数中数值最小的那个。同样，这个定义比“数值上最小”更深刻。
• 关系式 $dl=ab$：这是一个非常重要且有用的公式，揭示了最大公约数 $d=(a,b)$ 和最小公倍数 $l$（通常记作 $[a,b]$）之间的简单关系。它说，两个数的最大公约数和最小公倍数的乘积，恰好等于这两个数本身的乘积。（严格来说，是等于它们乘积的绝对值，即 $dl = |ab|$，但由于这里 $a,b$ 可以是负数，而 $d,l$ 都取正，所以 $dl=|ab|$ 更准确。不过在多数情况下，我们处理正整数，就简化为 $dl=ab$）。这个公式使得我们只要算出 g.c.d.，就能立刻得到 l.c.m.，反之亦然。

这条性质被称为除法算法。注意，虽然名字里有“算法”两个字，但它实际上是一个定理，它保证了某件事情的存在性和唯一性。

• 如果 $a, b \in \mathbb{Z}$ 且 $b \neq 0$：这里原文写的是 $a, b \in \mathbb{Z}-\{0\}$，但实际上除法算法对被除数 $a=0$ 也是成立的。更标准的条件是 $a, b \in \mathbb{Z}$ 且 $b \neq 0$。即 $a$ 是任意整数， $b$ 是任意非零整数。$a$ 是被除数，$b$ 是除数。
• 则存在唯一的 $q, r \in \mathbb{Z}$：这是定理的核心结论。它保证我们一定能找到一对整数 $q$ 和 $r$，并且这一对是独一无二的。
• 使得 $a = qb + r$：这是我们熟悉的小学除法关系式：被除数 = 商 × 除数 + 余数。
• 且 $0 \leq r < |b|$：这是对余数 $r$ 的关键约束。它规定余数 $r$ 必须是一个非负数（大于等于0），并且必须严格小于除数 $b$ 的绝对值。这个约束是保证商 $q$ 和余数 $r$ 唯一的关键。
• $q$ 是商，$r$ 是余数：给这两个唯一的整数命名。

所以，除法算法定理说的是：用一个非零整数 $b$ 去除另一个整数 $a$，必然会得到一个唯一的整数商 $q$ 和一个唯一的非负整数余数 $r$，这个余数比除数 $b$ 的绝对值要小。

这里介绍了求两个整数最大公约数的一个非常高效且经典的方法——欧几里得算法，也叫辗转相除法。

• 过程：该算法是一个迭代（重复）的过程。

1. 第 0 步: 取两个整数 $a$ 和 $b$（不妨设 $|a| \ge |b|$），做一次除法算法，得到 $a = q_0 b + r_0$。
2. 第 1 步: 将上一步的除数 $b$ 拿过来作为新的被除数，将上一步的余数 $r_0$ 拿过来作为新的除数，再做一次除法算法，得到 $b = q_1 r_0 + r_1$。
3. 第 2 步: 重复这个模式，用上一步的除数 $r_0$ 作为被除数，上一步的余数 $r_1$ 作为除数，得到 $r_0 = q_2 r_1 + r_2$。
4. 持续下去: 不断地用“前一次的余数”去除“前一次的除数”，直到某一步的余数为 0。
   • 算法的终止性：
   • 其中 $r_n$ 是最后一个非零余数：算法进行到第 (n+1) 步时，余数变为了 0（即 $r_{n-1}$ 被 $r_n$ 整除）。那么，在这之前一步（第 n 步）得到的那个非零余数 $r_n$，就是我们要求的结果。
   • 为什么算法一定会结束？ 因为根据除法算法的性质，每一步的余数都严格小于除数（的绝对值）。所以我们得到一串余数，它们的绝对值是严格递减的：$|b| > |r_0| > |r_1| > |r_2| > \dots \ge 0$。这是一个由非负整数组成的严格递减序列。根据我们之前讲的良序性，任何非空的正整数集都有一个最小元，所以这个序列不可能无限地递减下去而不碰到 0。它最终必然在有限步内达到余数 0。
   • 算法的正确性：
   • 那么 $r_n$ 就是 $a$ 和 $b$ 的最大公约数 $(a, b)$：为什么这最后一个非零余数就是 g.c.d. 呢？
   • 关键在于一个引理：$(x, y) = (y, x \pmod y)$，即两个数的最大公约数等于较小数与大数除以较小数的余数的最大公约数。
   • 让我们从下往上看算法：
   • 从第 (n+1) 步 $r_{n-1} = q_{n+1} r_n + 0$，我们知道 $r_n \mid r_{n-1}$。所以 $(r_{n-1}, r_n) = r_n$。
   • 从第 (n) 步 $r_{n-2} = q_n r_{n-1} + r_n$，根据引理，$(r_{n-2}, r_{n-1}) = (r_{n-1}, r_n) = r_n$。
   • 从第 (n-1) 步 ...，我们可以一路向上回溯，$(r_{n-3}, r_{n-2}) = (r_{n-2}, r_{n-1}) = r_n$。
   • ...
   • 直到最上面，我们得到 $(a, b) = (b, r_0) = (r_0, r_1) = \dots = (r_{n-1}, r_n) = r_n$。
   • 这就证明了算法的正确性。

这是一个具体的数值应用，演示了如何使用欧几里得算法计算两个较大整数的最大公约数。

• 第 1 步: 用大数 57970 除以小数 10353。
• $57970 \div 10353 \approx 5.6$。所以商是 5。
• 余数是 $57970 - 5 \times 10353 = 57970 - 51765 = 6205$。
• 得到第一行：$57970 = (5)10353 + 6205$。
• 第 2 步: 用上一步的除数 10353 除以上一步的余数 6205。
• $10353 \div 6205 \approx 1.6$。商是 1。
• 余数是 $10353 - 1 \times 6205 = 4148$。
• 得到第二行：$10353 = (1)6205 + 4148$。
• 第 3 步: 用 6205 除以 4148。
• $6205 \div 4148 \approx 1.49$。商是 1。
• 余数是 $6205 - 1 \times 4148 = 2057$。
• 得到第三行：$6205 = (1)4148 + 2057$。
• 第 4 步: 用 4148 除以 2057。
• $4148 \div 2057 \approx 2.01$。商是 2。
• 余数是 $4148 - 2 \times 2057 = 4148 - 4114 = 34$。
• 得到第四行：$4148 = (2)2057 + 34$。
• 第 5 步: 用 2057 除以 34。
• $2057 \div 34 \approx 60.5$。商是 60。
• 余数是 $2057 - 60 \times 34 = 2057 - 2040 = 17$。
• 得到第五行：$2057 = (60)34 + 17$。
• 第 6 步: 用 34 除以 17。
• $34 \div 17 = 2$。商是 2。
• 余数是 0。
• 得到第六行：$34 = (2)17 + 0$。

• 结论: 因为第六步的余数是 0，所以算法停止。最大公约数是第五步的非零余数，也就是 17。因此，$(57970, 10353) = 17$。

这条性质是欧几里得算法的一个极其重要的推论，通常被称为贝祖定理（Bézout's identity）或扩展欧几里得算法。

• 结论：对于任意两个非零整数 $a$ 和 $b$，它们的最大公约数 $(a,b)$ 总可以被表示成 $a$ 和 $b$ 的某种整数倍的和。
• 存在 $x, y \in \mathbb{Z}$：这里的 $x$ 和 $y$ 是可以找到的整数，它们可以是正数、负数或零。定理只保证它们存在，没有说它们是唯一的。
• $(a,b) = ax + by$：这个表达式叫做 $a$ 和 $b$ 的一个 $\mathbb{Z}$-线性组合。“线性组合”意味着是乘以系数再相加的形式，“$\mathbb{Z}$-”强调了系数 $x, y$ 必须是整数。
• 如何找到 $x$ 和 $y$？：文本给出了方法——倒推欧几里得算法。

1. 首先，正常执行欧几里得算法，得到一系列的除法等式，以及最大公约数 $d=r_n$。
2. 找到包含 $d=r_n$ 的那个倒数第二个等式：$r_{n-2} = q_n r_{n-1} + r_n$。
3. 在这个等式中，把 $r_n$ 解出来：$r_n = r_{n-2} - q_n r_{n-1}$。现在，$d$ 已经被表示成了前两个余数 $r_{n-2}$ 和 $r_{n-1}$ 的线性组合。
4. 接着，看倒数第三个等式，它会包含 $r_{n-1}$。从中解出 $r_{n-1}$，并把它代入上一步的表达式中。这样，表达式里就只剩下 $r_{n-2}$ 和 $r_{n-3}$ 了。
5. 重复这个代入过程：一步步地向上回溯，每次都用一个更早的等式来替换掉当前表达式里下标最大的余数，直到最后表达式里只剩下最开始的 $a$ 和 $b$。
6. 整理最终的表达式，写成 $d = a \cdot (\text{一堆数}) + b \cdot (\text{另一堆数})$ 的形式，括号里的就是我们想找的 $x$ 和 $y$。

本段详细演示了如何应用上一节描述的“倒推法”来求解贝祖等式。

背景:

• $a=57970, b=10353, (a,b)=17$。
• 欧几里得算法的等式:

(1) $57970 = 5 \cdot 10353 + 6205$

(2) $10353 = 1 \cdot 6205 + 4148$

(3) $6205 = 1 \cdot 4148 + 2057$

(4) $4148 = 2 \cdot 2057 + 34$

(5) $2057 = 60 \cdot 34 + 17$

倒推过程:

1. 从 (5) 出发，解出 17:

$17 = 2057 - 60 \cdot 34$ (当前组合由 2057 和 34 构成)

1. 用 (4) 替换 34:

从 (4) 解出 $34 = 4148 - 2 \cdot 2057$。

代入上式：

$17 = 2057 - 60 \cdot (4148 - 2 \cdot 2057)$

展开并合并同类项 (2057 和 4148):

$17 = 1 \cdot 2057 - 60 \cdot 4148 + 120 \cdot 2057$

$17 = (1+120) \cdot 2057 - 60 \cdot 4148$

$17 = 121 \cdot 2057 - 60 \cdot 4148$ (当前组合由 2057 和 4148 构成)

1. 用 (3) 替换 2057:

从 (3) 解出 $2057 = 6205 - 1 \cdot 4148$。

代入上式：

$17 = 121 \cdot (6205 - 1 \cdot 4148) - 60 \cdot 4148$

展开并合并同类项 (6205 和 4148):

$17 = 121 \cdot 6205 - 121 \cdot 4148 - 60 \cdot 4148$

$17 = 121 \cdot 6205 - (121+60) \cdot 4148$

$17 = 121 \cdot 6205 - 181 \cdot 4148$ (当前组合由 6205 和 4148 构成)

1. 用 (2) 替换 4148:

从 (2) 解出 $4148 = 10353 - 1 \cdot 6205$。

代入上式：

$17 = 121 \cdot 6205 - 181 \cdot (10353 - 1 \cdot 6205)$

展开并合并同类项 (6205 和 10353):

$17 = 121 \cdot 6205 - 181 \cdot 10353 + 181 \cdot 6205$

$17 = (121+181) \cdot 6205 - 181 \cdot 10353$

$17 = 302 \cdot 6205 - 181 \cdot 10353$ (当前组合由 6205 和 10353 构成)

1. 用 (1) 替换 6205:

从 (1) 解出 $6205 = 57970 - 5 \cdot 10353$。

代入上式：

$17 = 302 \cdot (57970 - 5 \cdot 10353) - 181 \cdot 10353$

展开并合并同类项 (57970 和 10353):

$17 = 302 \cdot 57970 - 302 \cdot 5 \cdot 10353 - 181 \cdot 10353$

$17 = 302 \cdot 57970 - 1510 \cdot 10353 - 181 \cdot 10353$

$17 = 302 \cdot 57970 - (1510+181) \cdot 10353$

$17 = 302 \cdot 57970 - 1691 \cdot 10353$

最终结果:

我们得到了 $17 = (302) \cdot 57970 + (-1691) \cdot 10353$。

这与 $ax+by=(a,b)$ 的形式匹配，其中 $a=57970, b=10353, (a,b)=17$，我们找到了一个解 $x=302, y=-1691$。

最后，作者指出，像 302 和 -1691 这样大的系数，靠猜是几乎不可能猜出来的，这凸显了算法的价值。

这段话指出了贝祖等式 $ax+by=d$（其中 $d=(a,b)$）的解 $(x,y)$ 不是唯一的。

• 给出一个特例: 继上文找到解 $(x_0, y_0) = (302, -1691)$ 之后，作者又给出了另一个解 $(x_1, y_1) = (-307, 1719)$。我们可以验证一下：

$57970 \times (-307) + 10353 \times 1719 = -17794790 + 17806407 = 11617$。

这里作者给的例子似乎有误。让我们自己推导一个正确的。

• 如何从一个解得到所有解？

假设我们有一个特解 $ax_0 + by_0 = d$。

我们想找另一个解 $a(x_0+k) + b(y_0+m) = d$，展开得到 $ax_0+ak+by_0+bm = d$。

因为 $ax_0+by_0=d$，所以上面方程简化为 $ak+bm=0$，即 $ak = -bm$。

两边同时除以 $d=(a,b)$，得到 $\frac{a}{d}k = -\frac{b}{d}m$。

由于 $\frac{a}{d}$ 和 $\frac{b}{d}$ 是互素的（这是 g.c.d 的一个重要性质），为了让等式成立， $k$ 必须是 $\frac{b}{d}$ 的整数倍，而 $m$ 必须是 $-\frac{a}{d}$ 的整数倍。

即，存在某个整数 $t$，使得 $k = \frac{b}{d}t$，代入得到 $\frac{a}{d} \frac{b}{d} t = -\frac{b}{d} m$，解得 $m = -\frac{a}{d}t$。

所以，所有的解都可以由特解 $(x_0, y_0)$ 生成：

$x = x_0 + \frac{b}{d}t$

$y = y_0 - \frac{a}{d}t$

其中 $t$ 是任意整数。

• 应用到例子中: $a=57970, b=10353, d=17$。

$x_0=302, y_0=-1691$。

$\frac{b}{d} = \frac{10353}{17} = 609$。

$\frac{a}{d} = \frac{57970}{17} = 3410$。

所以通解是：

$x = 302 + 609t$

$y = -1691 - 3410t$

让我们取 $t=1$，得到一个新解：

$x = 302 + 609 = 911$

$y = -1691 - 3410 = -5101$

让我们取 $t=-1$，得到另一个新解：

$x = 302 - 609 = -307$

$y = -1691 - (-3410) = -1691 + 3410 = 1719$。

啊哈，这说明作者给的例子 $(x,y)=(-307, 1719)$ 是正确的，它是由特解在 $t=-1$ 时得到的。我的手动验证计算出错了。

本段定义了素数和合数，并介绍了一个素数的核心性质，即欧几里得引理。

• 素数的定义: 一个正整数 $p$ 被称为素数（或质数），需要满足两个条件：

1. $p > 1$：1 不是素数。
2. $p$ 的正约数只有 1 和它自己 $p$。
   • 合数的定义: 一个大于 1 且不是素数的整数被称为合数。这意味着一个合数除了 1 和它自己之外，还有其他的正约数。
   • 例子:
   • 素数: 2（唯一的偶素数）, 3, 5, 7, ...
   • 合数: 4 (约数有1,2,4), 6 (约数有1,2,3,6), 9 (约数有1,3,9), ...
   • 素数的重要性质（欧几里得引理）:
   • 如果 $p$ 是一个素数，并且 $p \mid ab$：前提是，一个素数 $p$ 能整除两个整数 $a$ 和 $b$ 的乘积。
   • 那么 $p \mid a$ 或 $p \mid b$：结论是，这个素数 $p$ 必然至少能整除 $a$ 或 $b$ 中的一个（或者两个都能整除）。
   • 这个性质为什么重要？ 因为合数不具备这个性质。例如，6 是一个合数，$6 \mid 24$，而 $24=4 \times 6$。这里 $6 \mid (4 \times 6)$，它整除了乘积，也整除了其中一个因子6。再比如 $6 \mid 72$，而 $72 = 8 \times 9$。在这里 $6 \nmid 8$ 且 $6 \nmid 9$。啊，我的例子 $6 \mid 24 = 4 \times 6$ 不好。应该是 $6 \mid 24 = 3 \times 8$，$6 \nmid 3$ 且 $6 \nmid 8$。抱歉，举例错误。应该是 $6 \mid 12 = 3 \times 4$, $6 \nmid 3$ 且 $6 \nmid 4$。这个例子是正确的。
   • 证明（简要思路）:
   • 假设 $p \mid ab$ 且 $p \nmid a$。我们要证明 $p \mid b$。
   • 因为 $p$ 是素数，而 $p \nmid a$，那么 $a$ 和 $p$ 除了 1 之外没有其他公因子。所以 $(a, p) = 1$。
   • 根据贝祖定理，存在整数 $x, y$ 使得 $ax + py = 1$。
   • 将这个等式两边同时乘以 $b$：$abx + pby = b$。
   • 我们知道 $p \mid ab$，所以 $ab$ 可以写成 $pk$ (对于某个整数 $k$)。代入得到 $(pk)x + pby = b$。
   • 提出公因子 $p$：$p(kx + by) = b$。
   • 因为 $k, x, b, y$ 都是整数，所以 $kx+by$ 也是一个整数。
   • 这个等式 $p \times (\text{整数}) = b$ 正是 $p \mid b$ 的定义。
   • 证明完毕。

这是数论中最重要的定理之一，也叫唯一分解定理。它包含两个部分：存在性和唯一性。

• 前提: $n$ 是任何一个大于 1 的整数。
• 存在性: $n$ 可以被分解成一个或多个素数的乘积。
• $n=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{s}^{\alpha_{s}}$
• 这里 $p_1, ..., p_s$ 是不同的素数。
• $\alpha_1, ..., \alpha_s$ 是这些素数对应的指数（幂次），都是正整数。
• 证明思路（简要）: 用反证法和良序性。假设存在大于1的整数不能被分解为素数乘积，那么根据良序性，必然存在一个最小的这样的数，记为 $m$。$m$ 不能是素数（否则它自己就是自己的分解），所以 $m$ 是合数。于是 $m=ab$，其中 $1<a,b<m$。由于 $a, b$ 都比 $m$ 小，根据 $m$ 的最小性， $a$ 和 $b$ 都可以被分解为素数乘积。那么把 $a$ 和 $b$ 的分解乘起来，就得到了 $m$ 的分解，这与假设矛盾。所以所有大于1的整数都能被分解。
• 唯一性: 这种分解的方式是独一无二的（不考虑- 顺序）。
• 也就是说，如果 $n$ 有两种看起来不同的素数分解方式：

$n = p_1^{\alpha_1} \dots p_s^{\alpha_s}$ 和 $n = q_1^{\beta_1} \dots q_t^{\beta_t}$

• 那么，这两组素数实际上是完全一样的。素数的个数相同 ($s=t$)，并且把它们从小到大排好序后，对应的素数和指数也完全相同 ($p_i = q_i, \alpha_i = \beta_i$)。
• 证明思路（简要）: 运用欧几里得引理。假设两种分解相等 $p_1^{\alpha_1} \dots p_s^{\alpha_s} = q_1^{\beta_1} \dots q_t^{\beta_t}$。
• $p_1$ 整除了左边，所以它也必须整除右边。
• 根据欧几里得引理，$p_1$ 必须整除右边的某个素数 $q_j$。
• 因为 $q_j$ 也是素数，它的约数只有 1 和 $q_j$，所以 $p_1$ 只能等于 $q_j$。
• 同样地，可以证明每个 $p_i$ 都等于某个 $q_j$，反之亦然。所以两边的素数集合是相同的。
• 然后通过约掉相同的素数，用归纳法可以证明对应的指数也必须相同。
• 例子: $n=1852423848$ 这个大数，它的素因数分解是 $2^3 \cdot 3^2 \cdot 11^2 \cdot 19^3 \cdot 31^1$。算术基本定理保证，任何人用任何正确方法分解这个数，得到的素数因子一定是 3个2, 2个3, 2个11, 3个19 和 1个31，不可能分解出其他素数（比如5或7），也不可能这些素数的个数发生变化。

本段介绍了利用算术基本定理（唯一分解）来计算 g.c.d. 和 l.c.m. 的一种方法。

• 准备工作:
• 将 $a$ 和 $b$ 都进行素因数分解。
• 为了方便比较，我们将分解中涉及到的所有素数都写出来，即使某个素数在其中一个数中不存在。如果不存在，就认为它的指数是 0。
• 例如，$a=12=2^2 \cdot 3^1$, $b=90=2^1 \cdot 3^2 \cdot 5^1$。为了统一素数集合，我们把它们写成：

$a = 2^2 \cdot 3^1 \cdot 5^0$

$b = 2^1 \cdot 3^2 \cdot 5^1$

• 计算最大公约数 (g.c.d.):
• g.c.d. 是要找一个能同时整除 $a$ 和 $b$ 的最大数。这意味着它的素因子必须是 $a$ 和 $b$ 共有的，并且每个素因子的个数（指数）不能超过 $a$ 和 $b$ 中相应素因子的个数。
• 所以，对于每一个素数 $p_i$，g.c.d. 中该素数的指数，应该取 $a$ 和 $b$ 中该素数指数的较小值。
• 公式：$(a, b) = p_1^{\min(\alpha_1, \beta_1)} p_2^{\min(\alpha_2, \beta_2)} \dots$
• 计算最小公倍数 (l.c.m.):
• l.c.m. 是要找一个能同时被 $a$ 和 $b$ 整除的最小数。这意味着它的素因子必须包含 $a$ 和 $b$ 的所有素因子，并且每个素因子的个数（指数）必须足以被 $a$ 和 $b$ 的相应素因子整除。
• 所以，对于每一个素数 $p_i$，l.c.m. 中该素数的指数，应该取 $a$ 和 $b$ 中该素数指数的较大值。
• 公式（原文未写出，但作为补充）：$[a, b] = p_1^{\max(\alpha_1, \beta_1)} p_2^{\max(\alpha_2, \beta_2)} \dots$

本段是对前面介绍的两种计算 g.c.d. 方法的对比和评价。

• 应用素因数分解法:
• 作者给出了之前例子中两个大数的素因数分解：

$a = 57970 = 2^1 \cdot 3^0 \cdot 5^1 \cdot 7^0 \cdot 11^1 \cdot 17^1 \cdot 29^0 \cdot 31^1$

$b = 10353 = 2^0 \cdot 3^1 \cdot 5^0 \cdot 7^1 \cdot 11^0 \cdot 17^1 \cdot 29^1 \cdot 31^0$

• 通过比较指数，我们发现，唯一一个在两个分解式中指数都大于0的素数是 17 (指数都是1)。
• 对于素数 2，指数是 min(1, 0) = 0。
• 对于素数 3，指数是 min(0, 1) = 0。
• ...
• 对于素数 17，指数是 min(1, 1) = 1。
• ...
• 所以 $(a,b) = 2^0 \cdot 3^0 \cdot \dots \cdot 17^1 \cdot \dots = 17$。
• 方法的评价:
• 优点: 一旦分解完成，结果“立即”就能看出来。
• 缺点 (致命的): 对大整数进行素因数分解本身是一个极其困难的计算问题。目前还没有已知的快速算法。许多现代密码系统（如 RSA）的安全性就建立在这种困难之上。
• 结论:
• 尽管素因数分解法在概念上很清晰，但在实际计算中，对于稍大一点的数，它都是不可行的。
• 欧几里得算法的优越性在此体现：它完全不需要知道数的因子是什么，通过简单的除法和取余操作，就能快速得到 g.c.d.。

本段介绍了一个非常重要的数论函数——欧拉phi函数（或欧拉总计函数）。

• 定义: 对于一个正整数 $n$，$\varphi(n)$ 的值等于小于等于 $n$ 并且与 $n$ 互素的正整数的个数。
• "与 $n$ 互素" 意味着 $(a, n) = 1$。
• 示例: $\varphi(12)$
• 我们要找在 $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$ 中与 12 互素的数。
• $(1, 12)=1$ (是)
• $(2, 12)=2$ (否)
• $(3, 12)=3$ (否)
• $(4, 12)=4$ (否)
• $(5, 12)=1$ (是)
• $(6, 12)=6$ (否)
• $(7, 12)=1$ (是)
• $(8, 12)=4$ (否)
• $(9, 12)=3$ (否)
• $(10, 12)=2$ (否)
• $(11, 12)=1$ (是)
• $(12, 12)=12$ (否)
• 互素的数是 $\{1, 5, 7, 11\}$，共 4 个。所以 $\varphi(12)=4$。
• 特殊值的计算公式:
• 素数 $p$: $\varphi(p) = p-1$。因为 $1, 2, \dots, p-1$ 都与素数 $p$ 互素。
• 素数的幂 $p^a$: $\varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p-1)$。
• 解释: 在 $1$到 $p^a$ 的数中，不与 $p^a$ 互素的数，就是那些含有因子 $p$ 的数，即 $p$ 的倍数。这些数是 $1p, 2p, 3p, \dots, (p^{a-1})p$。共有 $p^{a-1}$ 个。
• 所以与 $p^a$ 互素的数的个数就是总数 $p^a$ 减去不互素的个数 $p^{a-1}$。
• 积性性质:
• $\varphi$ 是一个积性函数。这意味着如果 $a$ 和 $b$ 是互素的（$(a,b)=1$），那么 $\varphi(ab) = \varphi(a)\varphi(b)$。
• 注意: 如果 $a,b$ 不互素，这个性质不成立。例如 $\varphi(4)=2, \varphi(2)=1$, 但 $\varphi(4 \times 2)=\varphi(8)=4 \neq \varphi(4)\varphi(2)=2 \times 1 = 2$。这里 4 和 2 不互素。
• 通用计算公式:
• 结合算术基本定理和积性性质，我们可以计算任意正整数 $n$ 的 $\varphi$ 值。

1. 分解 $n$: $n=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{s}^{\alpha_{s}}$。
2. 利用积性: 因为 $p_i^{\alpha_i}$ 之间两两互素，所以 $\varphi(n) = \varphi(p_1^{\alpha_1}) \varphi(p_2^{\alpha_2}) \dots \varphi(p_s^{\alpha_s})$。
3. 代入公式: 将每个 $\varphi(p_i^{\alpha_i})$ 替换为 $p_i^{\alpha_i-1}(p_i-1)$。
   • 得到最终公式：$\varphi(n) = p_{1}^{\alpha_{1}-1}(p_{1}-1) \ldots p_{s}^{\alpha_{s}-1}(p_{s}-1)$。
   • 另一种常见写法是 $\varphi(n) = n \left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\ldots\left(1-\frac{1}{p_s}\right)$。
   • 示例: $\varphi(12)$
   • $12 = 2^2 \cdot 3^1$。
   • $\varphi(12) = \varphi(2^2) \cdot \varphi(3^1)$ (因为 $2^2$ 和 $3^1$ 互素)
   • $\varphi(2^2) = 2^{2-1}(2-1) = 2^1(1) = 2$。
   • $\varphi(3^1) = 3^{1-1}(3-1) = 3^0(2) = 1 \times 2 = 2$。
   • $\varphi(12) = 2 \times 2 = 4$。与我们手动数的结果一致。

这道题是欧几里得算法和扩展欧几里得算法的综合应用。对于每一对 $(a, b)$，需要做三件事：

1. 求 g.c.d.: 使用欧几里得算法（辗转相除）。
2. 求 l.c.m.: 利用公式 $l = |ab|/d$。
3. 求贝祖等式的解 $(x,y)$: 使用扩展欧几里得算法（倒推）。

这里我们详细解答 (a) 和 (b) 作为示例。

(a) $a=20, b=13$

1. g.c.d.(20, 13):

$20 = 1 \cdot 13 + 7$

$13 = 1 \cdot 7 + 6$

$7 = 1 \cdot 6 + 1$

$6 = 6 \cdot 1 + 0$

最后一个非零余数是 1。所以 $(20, 13) = 1$。它们是互素的。

1. l.c.m.(20, 13):

$l = (20 \times 13) / 1 = 260$。

1. $1 = 20x + 13y$:

倒推：

$1 = 7 - 1 \cdot 6$ (从 $7=1 \cdot 6 + 1$ 得到)

$1 = 7 - 1 \cdot (13 - 1 \cdot 7)$ (用 $6 = 13 - 1 \cdot 7$ 替换)

$1 = 1 \cdot 7 - 1 \cdot 13 + 1 \cdot 7 = 2 \cdot 7 - 1 \cdot 13$

$1 = 2 \cdot (20 - 1 \cdot 13) - 1 \cdot 13$ (用 $7 = 20 - 1 \cdot 13$ 替换)

$1 = 2 \cdot 20 - 2 \cdot 13 - 1 \cdot 13$

$1 = 2 \cdot 20 - 3 \cdot 13$

所以，一个解是 $x=2, y=-3$。

(b) $a=69, b=372$ (为了方便，我们计算 $(372, 69)$)

1. g.c.d.(372, 69):

$372 = 5 \cdot 69 + 27$

$69 = 2 \cdot 27 + 15$

$27 = 1 \cdot 15 + 12$

$15 = 1 \cdot 12 + 3$

$12 = 4 \cdot 3 + 0$

最后一个非零余数是 3。所以 $(372, 69) = 3$。

1. l.c.m.(372, 69):

$l = (372 \times 69) / 3 = 124 \times 69 = 8556$。

1. $3 = 372x + 69y$:

倒推：

$3 = 15 - 1 \cdot 12$

$3 = 15 - 1 \cdot (27 - 1 \cdot 15) = 2 \cdot 15 - 1 \cdot 27$

$3 = 2 \cdot (69 - 2 \cdot 27) - 1 \cdot 27 = 2 \cdot 69 - 4 \cdot 27 - 1 \cdot 27 = 2 \cdot 69 - 5 \cdot 27$

$3 = 2 \cdot 69 - 5 \cdot (372 - 5 \cdot 69) = 2 \cdot 69 - 5 \cdot 372 + 25 \cdot 69$

$3 = -5 \cdot 372 + 27 \cdot 69$

所以，一个解是 $x=-5, y=27$。(注意这里的 $a=372, b=69$。如果题目要求是 $a=69, b=372$，那么 $3 = 27 \cdot 69 - 5 \cdot 372$，解为 $x=27, y=-5$)

其他题目 (c)-(f) 过程类似，但计算更繁琐。

这道题要求证明公约数的一个基本线性性质。

1. 从定义出发:

题目给出前提 “整数 $k$ 整除整数 $a$ 和 $b$”。根据整除的定义，这意味着：

• $k \mid a$ 可以写成 $a = k \cdot m_1$，其中 $m_1$ 是某个整数。
• $k \mid b$ 可以写成 $b = k \cdot m_2$，其中 $m_2$ 是某个整数。

1. 构建目标表达式:

我们的目标是证明 $k$ 整除 $as+bt$。我们先把这个表达式写出来，然后把上面的两个等式代入：

$as + bt = (k \cdot m_1)s + (k \cdot m_2)t$

1. 提取公因数:

在表达式的右侧，我们可以看到两项都有一个公共的因子 $k$。我们把它提取出来：

$as + bt = k(m_1s + m_2t)$

1. 得出结论:
   • 我们知道 $m_1, s, m_2, t$ 都是整数。
   • 整数的乘法和加法是封闭的，也就是说，整数相乘、相加的结果仍然是整数。
   • 所以，$m_1s + m_2t$ 的结果是一个整数。我们不妨把它记作 $M = m_1s + m_2t$，其中 $M \in \mathbb{Z}$。
   • 这样，原表达式就变成了 $as + bt = k \cdot M$。
   • 根据整除的定义，如果能找到一个整数 $M$ 使得 $as+bt = kM$，那么就说明 $k \mid (as+bt)$。
   • 我们已经找到了这样的整数 $M$，所以证明完毕。

这道题要求证明合数不具备欧几里得引理的性质。

1. 从合数的定义出发:

题目给出前提 “$n$ 是合数”。根据合数的定义，一个大于 1 的整数 $n$ 是合数，意味着它可以被分解为两个比它小的正整数的乘积。

也就是说，存在整数 $a, b$ 使得 $n = a \cdot b$，并且 $1 < a < n$ 以及 $1 < b < n$。

1. 验证 $n \mid ab$:

我们刚刚已经把 $n$ 写成了 $n=ab$。这个等式本身就意味着 $n$ 是 $ab$ 的一个因子。更形式化地说，$ab = 1 \cdot n$。根据整除的定义，因为我们找到了一个整数 $c=1$ 使得 $ab=cn$，所以 $n \mid ab$ 成立。

1. 验证 $n \nmid a$ 和 $n \nmid b$:
   • 证明 $n \nmid a$: 我们知道 $a$ 是一个正整数且 $a < n$。如果 $n \mid a$ 要成立，那么必须存在一个正整数 $k$ 使得 $a = n \cdot k$。但因为 $n>0, k \ge 1$，所以 $n \cdot k \ge n$。这与 $a < n$ 矛盾。所以，$n$ 不可能整除 $a$。
   • 证明 $n \nmid b$: 同理，我们知道 $b$ 是一个正整数且 $b < n$。如果 $n \mid b$ 成立，将导致 $b \ge n$，与 $b < n$ 矛盾。所以，$n$ 也不可能整除 $b$。
2. 结论:

我们找到了这样一对整数 $a, b$（即 $n$ 的两个小于 $n$ 的因子），它们满足 $n \mid ab$ 但 $n \nmid a$ 和 $n \nmid b$。证明完毕。

这道题要求我们验证给出的通解公式的正确性。

1. 目标: 证明 $a(x_0 + \frac{b}{d}t) + b(y_0 - \frac{a}{d}t) = N$。
2. 代入和展开:

我们将给出的 $x$ 和 $y$ 的表达式代入方程 $ax+by$ 的左边：

$ax + by = a\left(x_{0}+\frac{b}{d} t\right) + b\left(y_{0}-\frac{a}{d} t\right)$

使用分配律展开括号：

$= ax_0 + a\frac{b}{d}t + by_0 - b\frac{a}{d}t$

1. 重新组合:

将含有 $t$ 的项和不含 $t$ 的项分开：

$= (ax_0 + by_0) + \left(a\frac{b}{d}t - b\frac{a}{d}t\right)$

1. 利用已知条件:
   • 我们已知 $(x_0, y_0)$ 是一个特解，所以 $ax_0 + by_0 = N$。
   • 对于带 $t$ 的部分，我们整理一下：$a\frac{b}{d}t - b\frac{a}{d}t = \frac{abt}{d} - \frac{bat}{d} = 0$。
2. 得出结论:

将上述结果代回第3步的表达式：

$ax+by = (N) + (0) = N$

这表明，对于任何整数 $t$，给出的 $x$ 和 $y$ 的表达式确实满足方程 $ax+by=N$。所以它们都是方程的解。

(该题目还提到“这实际上是通解”。证明这是通解需要额外一步：证明任何解都必须是这个形式。简要思路如下：假设 $(x', y')$ 是另一个任意解，则 $ax'+by'=N$。与 $ax_0+by_0=N$ 相减得到 $a(x'-x_0)+b(y'-y_0)=0$。由此可推导出 $x'-x_0$ 必须是 $b/d$ 的整数倍，即 $x'-x_0 = t(b/d)$, 这就导出了通解公式。)

这道题是欧拉 $\varphi$-函数定义的直接应用和计算练习。我们可以通过三种方法：

1. 直接计数法: 对每个 $n$，列出从 1 到 $n$ 的所有数，然后逐个检查与 $n$ 的最大公约数是否为 1。
2. 公式法: 对每个 $n$ 进行素因数分解，然后使用公式 $\varphi(n) = n \prod_{p|n}(1-1/p)$。
3. 综合法: 结合积性性质和特殊值。例如 $\varphi(p)=p-1$。

下面是 $n=1$ 到 $n=30$ 的 $\varphi(n)$ 值列表：

• $\varphi(1)=1$
• $\varphi(2)=1$ (素数)
• $\varphi(3)=2$ (素数)
• $\varphi(4)=\varphi(2^2)=2^{2-1}(2-1)=2$
• $\varphi(5)=4$ (素数)
• $\varphi(6)=\varphi(2)\varphi(3)=1 \times 2 = 2$
• $\varphi(7)=6$ (素数)
• $\varphi(8)=\varphi(2^3)=2^{3-1}(2-1)=4$
• $\varphi(9)=\varphi(3^2)=3^{2-1}(3-1)=6$
• $\varphi(10)=\varphi(2)\varphi(5)=1 \times 4 = 4$
• $\varphi(11)=10$ (素数)
• $\varphi(12)=\varphi(4)\varphi(3)=2 \times 2 = 4$
• $\varphi(13)=12$ (素数)
• $\varphi(14)=\varphi(2)\varphi(7)=1 \times 6 = 6$
• $\varphi(15)=\varphi(3)\varphi(5)=2 \times 4 = 8$
• $\varphi(16)=\varphi(2^4)=2^{4-1}(2-1)=8$
• $\varphi(17)=16$ (素数)
• $\varphi(18)=\varphi(2)\varphi(9)=1 \times 6 = 6$
• $\varphi(19)=18$ (素数)
• $\varphi(20)=\varphi(4)\varphi(5)=2 \times 4 = 8$
• $\varphi(21)=\varphi(3)\varphi(7)=2 \times 6 = 12$
• $\varphi(22)=\varphi(2)\varphi(11)=1 \times 10 = 10$
• $\varphi(23)=22$ (素数)
• $\varphi(24)=\varphi(8)\varphi(3)=4 \times 2 = 8$
• $\varphi(25)=\varphi(5^2)=5^{2-1}(5-1)=20$
• $\varphi(26)=\varphi(2)\varphi(13)=1 \times 12 = 12$
• $\varphi(27)=\varphi(3^3)=3^{3-1}(3-1)=18$
• $\varphi(28)=\varphi(4)\varphi(7)=2 \times 6 = 12$
• $\varphi(29)=28$ (素数)
• $\varphi(30)=\varphi(2)\varphi(3)\varphi(5)=1 \times 2 \times 4 = 8$

该题目有两部分。

第一部分：证明最小元素的唯一性

1. 反证法: 假设最小元素不唯一。
2. 设 $A$ 是 $\mathbb{Z}^+$ 的一个非空子集，假设 $m_1$ 和 $m_2$ 都是 $A$ 的最小元素，且 $m_1 \neq m_2$。
3. 根据最小元素的定义：
   • 因为 $m_1$ 是最小元素，所以对于 $A$ 中所有元素 $a$（包括 $m_2$），都有 $m_1 \leq a$。因此，$m_1 \leq m_2$。
   • 因为 $m_2$ 是最小元素，所以对于 $A$ 中所有元素 $a$（包括 $m_1$），都有 $m_2 \leq a$。因此，$m_2 \leq m_1$。
4. 根据反对称性，如果 $m_1 \leq m_2$ 且 $m_2 \leq m_1$ 同时成立，那么必然有 $m_1 = m_2$。
5. 这与我们最初的假设 $m_1 \neq m_2$ 相矛盾。
6. 因此，假设不成立，最小元素必须是唯一的。

第二部分：用归纳法证明良序性

注意：良序性原理和数学归纳法原理是等价的，通常一个被当作公理来证明另一个。这里要求用归纳法证明良序性。证明的命题是：任何非空的正整数子集都有一个最小元素。

1. 使用反证法: 假设存在一个或多个非空的正整数子集没有最小元素。我们称这样的集合为“坏”集合。
2. 构造证明命题: 令 $P(n)$ 为命题：“整数 $n$ 不属于任何‘坏’集合”。我们将用强归纳法证明 $P(n)$ 对所有正整数 $n$ 成立。
3. 基础情况 (n=1): 假设 1 属于某个“坏”集合 $S$。因为 $S$ 是正整数的集合，1 是最小的正整数，所以 1 必然是 $S$ 的最小元素。但这与 $S$ 是“坏”集合（没有最小元素）的定义相矛盾。所以 1 不可能属于任何“坏”集合。$P(1)$ 成立。
4. 归纳步骤: 假设对于所有 $k < n$，$P(k)$ 都成立（即 $1, 2, \dots, n-1$ 都不在任何“坏”集合里）。我们要证明 $P(n)$ 也成立。
5. 再次使用反证法：假设 $P(n)$ 不成立，即 $n$ 属于某个“坏”集合 $S$。
6. 因为 $n$ 在 $S$ 中，而 $S$ 没有最小元素，所以 $S$ 中必定存在一个元素 $m$ 使得 $m < n$。
7. 这个元素 $m$ 也是一个正整数，并且 $m$ 也属于这个“坏”集合 $S$。
8. 但是，根据我们的归纳假设，所有小于 $n$ 的正整数 $k$（包括 $m$）都不属于任何“坏”集合。
9. 这导致了矛盾：$m$ 既在“坏”集合 $S$ 中，又根据归纳假设不能在任何“坏”集合中。
10. 结论: 假设 $P(n)$ 不成立是错误的。因此 $P(n)$ 成立。
11. 最终结论: 通过强归纳法，我们证明了对所有正整数 $n$，$P(n)$ 都成立。这意味着没有任何正整数可以属于一个“坏”集合。换句话说，“坏”集合（没有最小元素的非空正整数子集）根本不存在。因此，任何非空的正整数子集都必须有一个最小元素。

这道题要求证明素数的平方根是无理数，是证明 $\sqrt{2}$ 是无理数的推广。

1. 使用反证法: 假设 $\sqrt{p}$ 是一个有理数。
2. 那么，根据有理数的定义，$\sqrt{p}$ 可以写成两个整数的比：$\sqrt{p} = \frac{a}{b}$，其中 $a, b \in \mathbb{Z}$ 且 $b \neq 0$。
3. 最简分数假设: 我们可以进一步假设这个分数 $\frac{a}{b}$ 已经化为最简形式。这意味着 $a$ 和 $b$ 的最大公约数是 1，即 $(a, b) = 1$。这是此证明的关键。
4. 代数变形: 将等式 $\sqrt{p} = \frac{a}{b}$ 两边平方，得到 $p = \frac{a^2}{b^2}$。
5. 整理得 $a^2 = p b^2$。
6. 运用欧几里得引理:
   • 等式 $a^2 = p b^2$ 表明 $p$ 整除 $a^2$ (记作 $p \mid a^2$)。
   • 因为 $p$ 是一个素数，根据欧几里得引理（如果素数整除一个乘积，则它至少整除其中一个因子），$p \mid (a \cdot a)$ 意味着 $p \mid a$。
7. 代入与推导:
   • 既然 $p \mid a$，那么 $a$ 可以被写成 $a=pk$ 的形式，其中 $k$ 是某个整数。
   • 将 $a=pk$ 代入到第5步的等式中：$(pk)^2 = p b^2$。
   • 展开得到 $p^2 k^2 = p b^2$。
   • 两边同时除以 $p$（因为 $p$ 是素数，不为0），得到 $p k^2 = b^2$。
8. 再次运用欧几里得引理:
   • 等式 $b^2 = p k^2$ 表明 $p \mid b^2$。
   • 同样，因为 $p$ 是素数，根据欧几里得引理，我们得出 $p \mid b$。
9. 导出矛盾:
   • 在第6步，我们得出 $p \mid a$。
   • 在第8步，我们得出 $p \mid b$。
   • 这意味着 $p$ 是 $a$ 和 $b$ 的一个公约数。
   • 但这与第3步的假设 $(a, b) = 1$ （即 $a$和$b$没有大于1的公约数）相矛盾。因为 $p$ 是素数，所以 $p>1$。
10. 结论: 我们的初始假设“$\sqrt{p}$ 是有理数”必然是错误的。因此，$\sqrt{p}$ 必须是无理数。

这道题要求推导著名的勒让德公式 (Legendre's Formula)。公式是：$n!$ 中素数 $p$ 的指数 $E_p(n!)$ 为

$E_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots$

其中 $\lfloor x \rfloor$ 是取整函数，表示不大于 $x$ 的最大整数。

推导过程:

1. 目标: 我们要计算在 $n! = 1 \times 2 \times \dots \times n$ 的素因数分解中，素数 $p$ 出现了多少次。
2. 第一步：计算 $p$ 的倍数:

在 $1, 2, \dots, n$ 这些数中，有些是 $p$ 的倍数，它们都至少贡献了一个因子 $p$。这些数是 $p, 2p, 3p, \dots, kp$ 只要 $kp \le n$，即 $k \le n/p$。这样的数一共有 $\lfloor n/p \rfloor$ 个。

1. 第二步：计算 $p^2$ 的倍数:

像 $p^2, 2p^2$ 这样的数，它们至少含有两个因子 $p$。在第一步中，我们只为它们算了一个因子 $p$，所以现在需要把额外的那个因子 $p$ 加上。在 $1, 2, \dots, n$ 中，$p^2$ 的倍数有多少个呢？同理，有 $\lfloor n/p^2 \rfloor$ 个。

1. 第三步：计算 $p^3$ 的倍数:

像 $p^3, 2p^3$ 这样的数，它们至少含有三个因子 $p$。在前两步中，我们已经为它们计算了两次（一次作为 $p$ 的倍数，一次作为 $p^2$ 的倍数），所以还需要再补上一个因子 $p$。这样的数有 $\lfloor n/p^3 \rfloor$ 个。

1. 以此类推:

对于任意的 $k \ge 1$，所有 $p^k$ 的倍数都比 $p^{k-1}$ 的倍数多贡献一个因子 $p$。

1. 加总:

$p$ 的总指数，就是所有这些贡献的总和。

总指数 = (至少含一个 $p$ 的数的个数) + (至少含两个 $p$ 的数的个数) + ...

这个想法是正确的，上述的第2,3步正是这个思路。因此，总的指数就是把所有这些贡献加起来：

$E_p(n!) = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \lfloor n/p^3 \rfloor + \dots$

这个求和是有限的，因为当 $p^k > n$ 时，$\lfloor n/p^k \rfloor$ 就会等于 0。

这道题要求实现扩展欧几里得算法。虽然前面我们用的是“倒推法”，但在编程时，使用一个迭代的、正向的算法更高效。

迭代算法思想:

我们不仅追踪余数 $r_i$，还同时追踪每一项的系数 $x_i, y_i$，使得 $r_i = a x_i + b y_i$。

1. 初始化:

$r_0 = a, x_0 = 1, y_0 = 0$ (因为 $a = a \cdot 1 + b \cdot 0$)

$r_1 = b, x_1 = 0, y_1 = 1$ (因为 $b = a \cdot 0 + b \cdot 1$)

1. 迭代:

只要 $r_{i+1} \neq 0$，我们就重复以下过程：

• 首先，根据欧几里得算法，做除法：$r_i = q_{i+1} r_{i+1} + r_{i+2}$。所以 $q_{i+1} = \lfloor r_i / r_{i+1} \rfloor$。
• 新的余数是 $r_{i+2} = r_i - q_{i+1} r_{i+1}$。
• 现在我们计算新余数对应的系数 $x_{i+2}, y_{i+2}$：

$r_{i+2} = (a x_i + b y_i) - q_{i+1}(a x_{i+1} + b y_{i+1})$

$r_{i+2} = a(x_i - q_{i+1} x_{i+1}) + b(y_i - q_{i+1} y_{i+1})$

• 所以，我们得到了系数的递推关系：

$x_{i+2} = x_i - q_{i+1} x_{i+1}$

$y_{i+2} = y_i - q_{i+1} y_{i+1}$

1. 终止:

当 $r_{i+1} = 0$ 时，迭代停止。此时的 $r_i$ 就是最大公约数 $d$，而对应的 $x_i, y_i$ 就是满足 $d = ax_i + by_i$ 的一对解。

伪代码:

```

function extended_gcd(a, b)

// 初始化

old_r, r = a, b

old_x, x = 1, 0

old_y, y = 1, 0 // 实际上 old_y 应该是 0, y 应该是 1

// 修正初始化

old_r, r = a, b

old_x, x = 1, 0

old_y, y = 0, 1

while r != 0:

quotient = old_r // r // 整除

// 更新 r

(old_r, r) = (r, old_r - quotient * r)

// 更新 x

(old_x, x) = (x, old_x - quotient * x)

// 更新 y

(old_y, y) = (y, old_y - quotient * y)

// 返回 g.c.d, x, y

return old_r, old_x, old_y

```

第一部分：证明 $\varphi(n)=N$ 的解是有限的

1. 分析 $\varphi(n)$ 的公式:

$\varphi(n) = n \prod_{p|n} (1-1/p) = n \frac{p_1-1}{p_1} \frac{p_2-1}{p_2} \dots \frac{p_s-1}{p_s}$

其中 $p_i$ 是 $n$ 的不同素因子。

1. 寻找对 $n$ 的素因子的约束:
   • 如果 $n = p_1^{a_1} \dots p_s^{a_s}$，那么 $\varphi(n) = p_1^{a_1-1}(p_1-1) \dots p_s^{a_s-1}(p_s-1) = N$。
   • 如果 $p$ 是 $n$ 的一个素因子，那么 $(p-1)$ 必须整除 $\varphi(n)$，即 $(p-1) \mid N$。
   • 对于一个给定的 $N$，它的约数是有限的。因此，满足 $(p-1) \mid N$ 的素数 $p$ 的可能性也是有限的。这意味着任何满足 $\varphi(n)=N$ 的 $n$，其素因子只能从这个有限的素数集合中选取。
2. 寻找对 $n$ 的素因子指数的约束:
   • 对于每个可能的素因子 $p$，我们来看它的指数 $a$。$p^{a-1}$ 也必须是 $N$ 的一个因子。
   • 如果 $p^{a-1} > N$，则不可能有解。这给 $a-1$ 设置了一个上限：$a-1 \le \log_p(N)$，所以 $a \le \log_p(N) + 1$。
   • 因此，对于每个可能的素因子 $p$，其指数 $a$ 也是有上界的，只能取有限个值。
3. 结论:

既然满足 $\varphi(n)=N$ 的 $n$，其素因子的选择是有限的，并且每个素因子的指数也是有限的，那么通过这些素因子和指数组合起来构成的 $n$ 的总数也必然是有限的。

第二部分：证明 $\varphi(n) \to \infty$ 当 $n \to \infty$

1. 使用反证法: 假设 $\varphi(n)$ 不趋于无穷大。
2. 这意味着，存在一个常数 $M$，使得有无穷多个不同的整数 $n_1, n_2, n_3, \dots$ 满足 $\varphi(n_i) \le M$。
3. 由于 $\varphi(n)$ 的值是整数，那么在 $[1, M]$ 这个区间内，$\varphi(n)$ 的取值是有限的。根据鸽巢原理，必然存在一个整数 $N \le M$，使得有无穷多个不同的整数 $n$ 满足 $\varphi(n)=N$。
4. 但这与我们第一部分证明的结论（对于任何 $N$，满足 $\varphi(n)=N$ 的 $n$ 的个数是有限的）相矛盾。
5. 结论: 我们的初始假设不成立。因此，当 $n \to \infty$ 时，$\varphi(n) \to \infty$。

这道题要求证明 $\varphi$ 函数在整除关系下的一个性质。我们可以使用基于素因数分解的公式来证明。

1. 表示 $n$ 和 $d$:
   • 设 $n$ 的素因数分解为 $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$，其中 $a_i \ge 1$。
   • 因为 $d \mid n$，所以 $d$ 的素因子必须是 $n$ 的素因子的子集。因此 $d$ 的分解式可以写成 $d = p_1^{b_1} p_2^{b_2} \dots p_k^{b_k}$，其中 $0 \le b_i \le a_i$ 对于所有的 $i=1, \dots, k$。
2. 写出 $\varphi(n)$ 和 $\varphi(d)$:
   • $\varphi(n) = \varphi(p_1^{a_1}) \dots \varphi(p_k^{a_k}) = [p_1^{a_1-1}(p_1-1)] \dots [p_k^{a_k-1}(p_k-1)]$。
   • $\varphi(d) = \varphi(p_1^{b_1}) \dots \varphi(p_k^{b_k}) = [p_1^{b_1-1}(p_1-1)] \dots [p_k^{b_k-1}(p_k-1)]$。（注意：如果 $b_i=0$，则 $p_i$ 不是 $d$ 的因子，$\varphi(p_i^0)=\varphi(1)=1$。我们的公式 $p^{b-1}(p-1)$ 在 $b=0$ 时会给出 $p^{-1}(p-1)$，这不是整数，所以需要分情况讨论。或者使用更鲁棒的公式 $\varphi(m)=m\prod_{p|m}(1-1/p)$）

让我们用更清晰的方式处理:

我们需要证明 $\frac{\varphi(n)}{\varphi(d)}$ 是一个整数。

$\frac{\varphi(n)}{\varphi(d)} = \frac{\prod_{i=1}^k \varphi(p_i^{a_i})}{\prod_{i=1}^k \varphi(p_i^{b_i})} = \prod_{i=1}^k \frac{\varphi(p_i^{a_i})}{\varphi(p_i^{b_i})}$

1. 检查每一项:

我们只需要证明对于每个素数 $p_i$，$\varphi(p_i^{b_i})$ 都整除 $\varphi(p_i^{a_i})$。

• 情况 1: $b_i = 0$。

此时 $d$ 不含 $p_i$ 因子。$\varphi(p_i^{b_i}) = \varphi(p_i^0) = \varphi(1) = 1$。显然 $1$ 可以整除任何整数，所以 $1 \mid \varphi(p_i^{a_i})$ 成立。

• 情况 2: $b_i \ge 1$。

此时 $p_i$ 也是 $d$ 的因子。我们有 $1 \le b_i \le a_i$。

• $\varphi(p_i^{a_i}) = p_i^{a_i-1}(p_i-1)$
• $\varphi(p_i^{b_i}) = p_i^{b_i-1}(p_i-1)$
• 它们的商是 $\frac{p_i^{a_i-1}(p_i-1)}{p_i^{b_i-1}(p_i-1)} = p_i^{(a_i-1)-(b_i-1)} = p_i^{a_i-b_i}$。
• 因为 $a_i \ge b_i$，所以 $a_i-b_i \ge 0$。因此 $p_i^{a_i-b_i}$ 是一个整数。
• 所以，$\varphi(p_i^{b_i}) \mid \varphi(p_i^{a_i})$ 成立。

1. 结论:

既然对于每一个素因子 $p_i$，比率 $\frac{\varphi(p_i^{a_i})}{\varphi(p_i^{b_i})}$ 都是一个整数，那么它们的总乘积 $\frac{\varphi(n)}{\varphi(d)}$ 也必然是一个整数。

这就证明了 $\varphi(d) \mid \varphi(n)$。