数论入门：从整数到密码

前言

数学是科学的皇后，数论是皇后的皇冠。 —— 卡尔·弗里德里希·高斯

在数学的宏伟殿堂中，数论占据着一个独特而神秘的位置。它研究的是人类最早认识、最简单也最深刻的数学对象——整数。从幼儿园开始，我们就学会了数数：1, 2, 3, 4, 5……然而，正是这些看似平凡的整数，凝结了人类数千年的智慧结晶，至今仍在不断催生着激动人心的数学发现。

本书是一本为零基础读者准备的数论入门读物。如果你拥有高中数学基础，对整数的性质和规律感到好奇，希望系统了解这门被誉为"纯数学灵魂"的学科，那么这本书就是为你而写的。

数论的历史剪影

数论的起源可以追溯到古希腊。毕达哥拉斯（约公元前570—前495年）及其学派对整数倾注了近乎宗教般的热情。他们相信"万物皆数"，发现了完全数、亲和数，以及著名的毕达哥拉斯三元组——即满足 a² + b² = c² 的正整数解。然而，正是这个看似简单的方程，在2300年后引出了费马大定理，耗费了人类最智慧的头脑350多年才最终被证明。

欧几里得（约公元前300年）在其不朽著作《几何原本》中，收录了数论的基础定理。他给出了素数无穷多个的优雅证明——这个证明至今仍是数学证明之美的典范。他还建立了辗转相除法（欧几里得算法），为计算最大公因数提供了至今仍无出其右的高效方法。

17世纪，法国数学家皮埃尔·德·费马以"业余数学家之王"的称号闻名于世。他在丢番图《算术》一书的页边留下了大量注释，其中最为人津津乐道的是他声称找到了 xⁿ + yⁿ = zⁿ（n > 2）无正整数解的"绝妙证明"，却因"页边太窄写不下"而未留下细节。这个"费马大定理"直到1994年才由安德鲁·怀尔斯在椭圆曲线和模形式的深刻理论基础上完成证明，成为20世纪数学的最高成就之一。

18至19世纪，数论迎来黄金时代。莱昂哈德·欧拉和卡尔·弗里德里希·高斯将数论系统化、严格化。欧拉证明了费马的许多猜想，引入了欧拉函数，并用分析方法研究素数的分布。高斯的《算术研究》（1801年）则奠定了现代数论的基础——他系统建立了同余理论，证明了二次互反律（他称之为"黄金定理"），并给出了六种不同的证明。

20世纪中叶以后，数论迎来了一个意想不到的转折：这门几千年来一直以"纯粹"和"无用"著称的学科，突然成了信息安全的基石。1977年，Rivest、Shamir和Adleman提出了RSA公钥密码体制，其安全性建立在大整数因数分解的困难性之上。从此，数论从象牙塔走向了日常生活的每一个角落——每当你访问一个HTTPS网站、使用网上银行或在手机上进行支付，幕后的密码协议都依赖于数论定理的保护。

本书的结构与读法

本书共分为10章，按照从基础到应用的逻辑顺序编排：

第1—4章 构建数论的核心基础：整除性、同余理论、同余方程和素数；
第5—7章 引入更高级的工具：数论函数、二次剩余和原根；
第8—9章 探讨不定方程和连分数这两个历史悠久的分支；
第10章 展示数论在现代密码学中的应用，将理论与现实紧密连接。

各章之间具有明显的递进关系，建议初学者按顺序阅读。如果时间有限，读者可以跳过部分标注"选读"的证明细节，但建议至少完成每章的例题计算。

预备知识

本书假设读者已掌握以下基础知识：

基本的代数运算和符号操作；
数学归纳法的原理和基本运用；
集合论的基本概念（属于、子集等）；
函数的基本概念。

除此之外，每一章都会从最基本的概念讲起，逐步深入。书中所有定理都给出了证明或证明概要，配有大量例题帮助理解，每章末尾还有练习题供读者自我检测。

致谢

感谢所有为数学知识传承付出努力的前辈。正如牛顿所说："如果说我比别人看得更远，那是因为我站在巨人的肩膀上。"愿这本小书能成为读者攀登数论之峰的坚实台阶。

现在，让我们开始这场穿越整数世界的奇妙旅程。

第 1 章整数的整除性

1.1 整除与带余除法

整除的定义与符号

我们从最基础的概念开始。设 a 和 b 是两个整数，且 b ≠ 0。如果存在一个整数 q，使得 a = bq，我们就说 b 整除 a，记作

b | a

读作"b 整除 a"。此时，b 称为 a 的因数（或约数），a 称为 b 的倍数。如果不存在这样的整数 q，我们就说 b 不能整除 a，记作 b ∤ a。

举几个例子：

3 | 12，因为 12 = 3 × 4；
7 | 49，因为 49 = 7 × 7；
5 ∤ 13，因为 13 ÷ 5 不是整数；
1 | n 对任何整数 n 都成立；
n | 0 对任何非零整数 n 都成立，因为 0 = n × 0。

整除关系具有以下基本性质：

性质 1（传递性）：若 a | b 且 b | c，则 a | c。证明：由条件，存在整数 m, n 使得 b = am, c = bn。于是 c = a(mn)，故 a | c。

性质 2（线性组合）：若 a | b 且 a | c，则对任意整数 x, y，有 a | (bx + cy)。证明：设 b = am, c = an，则 bx + cy = a(mx + ny)，故 a | (bx + cy)。

性质 3：若 a | b 且 b | a，则 a = ±b。证明：由条件，存在整数 m, n 使得 b = am, a = bn。于是 a = amn，若 a = 0 则 b = 0，结论成立。若 a ≠ 0，则 mn = 1。m, n 为整数，故 m = n = 1 或 m = n = -1，即 a = b 或 a = -b。

带余除法定理

当整除不成立时，我们仍然可以进行除法，只是会留下一个余数。带余除法（又称欧几里得除法）定理精确地刻画了这一过程。

定理 1.1（带余除法定理）：设 a, b 为整数，且 b > 0，则存在唯一的一对整数 q（商）和 r（余数），使得

a = bq + r， 0 ≤ r < b

证明：

存在性：考虑所有形如 a - bk 的整数，其中 k 为整数。取这些数中非负且最小的那个。令 S = {a - bk ≥ 0 | k ∈ Z}。因为当 k 足够小时 a - bk 可以任意大，当 k 足够大时 a - bk 为负，所以 S 非空且有下界。由最小数原理，S 中存在最小元 r = a - bq，且 r ≥ 0。若 r ≥ b，则 r - b = a - b(q + 1) ≥ 0 且比 r 更小，与 r 的最小性矛盾。故 0 ≤ r < b。

唯一性：假设存在两对解 (q₁, r₁) 和 (q₂, r₂) 满足条件。则

bq₁ + r₁ = bq₂ + r₂， 0 ≤ r₁, r₂ < b

于是 b(q₁ - q₂) = r₂ - r₁。左边是 b 的倍数，右边绝对值严格小于 b。唯一的可能是两边都为 0，所以 q₁ = q₂，r₁ = r₂。

例 1.1：求 a = 47 除以 b = 8 的商和余数。解：47 = 8 × 5 + 7，所以 q = 5，r = 7。□

例 1.2：求 a = -47 除以 b = 8 的商和余数。解：注意余数必须满足 0 ≤ r < 8。我们有 -47 = 8 × (-6) + 1，所以 q = -6，r = 1。验证：8 × (-6) = -48，-48 + 1 = -47。□

带余除法是整章的基础，下一节的辗转相除法就是对它反复运用的结果。

例 1.3：证明任意整数 n 的平方被 4 除的余数只能是 0 或 1。证明：将 n 除以 2，得 n = 2q 或 n = 2q + 1。

若 n = 2q，则 n² = 4q²，余数为 0；
若 n = 2q + 1，则 n² = 4q² + 4q + 1 = 4(q² + q) + 1，余数为 1。

这个简单的结论在后续素数讨论中会反复用到。□

1.2 最大公因数与辗转相除法

最大公因数的定义

设 a 和 b 是不全为零的整数。我们称整数 d 为 a 和 b 的一个公因数，如果 d | a 且 d | b。a 和 b 的所有公因数中最大的那个称为它们的最大公因数，记作

gcd(a, b) 或简记为 (a, b)

例如，gcd(12, 18) = 6，gcd(15, 28) = 1，gcd(0, 5) = 5。

如果 gcd(a, b) = 1，我们就说 a 和 b 互素（或互质）。互素是数论中最重要的概念之一。

思考：公因数的集合和最大公因数有什么关系？事实上，a 和 b 的每个公因数都整除 gcd(a, b)。这个性质在后面将非常有用。

辗转相除法（欧几里得算法）

辗转相除法是计算两个数的最大公因数的最古老且最有效的算法，其历史可以追溯到欧几里得的《几何原本》（约公元前300年）。这个算法的核心思想极其简洁：

引理 1.1：若 a = bq + r，则 gcd(a, b) = gcd(b, r)。

证明：设 d = gcd(a, b)，我们证明 d 也是 b 和 r 的最大公因数。首先，d | a 且 d | b，所以由整除的线性组合性质，d | (a - bq) = r，故 d 是 b 和 r 的公因数。其次，设 d' 是 b 和 r 的任一公因数，则 d' | b 且 d' | r，故 d' | (bq + r) = a。于是 d' 是 a 和 b 的公因数，从而 d' ≤ d = gcd(a, b)。因此 d 确实是 b 和 r 的最大公因数。

这个引理的意义在于：如果我们想计算 gcd(a, b)，可以先用带余除法 a = bq + r，然后转而计算更小的数 gcd(b, r)。由于余数 r 严格小于 b，反复这样做将使数值不断减小，最终到达一个可以一眼看出的情况。

辗转相除法的步骤：

为了计算 gcd(a, b)（其中 a ≥ b > 0），反复运用带余除法：

a = b × q₁ + r₁,    0 < r₁ < b
b = r₁ × q₂ + r₂,   0 < r₂ < r₁
r₁ = r₂ × q₃ + r₃,  0 < r₃ < r₂
...
rₖ₋₂ = rₖ₋₁ × qₖ + rₖ,  0 < rₖ < rₖ₋₁
rₖ₋₁ = rₖ × qₖ₊₁ + 0

由于余数序列 r₁ > r₂ > r₃ > ... 严格递减，这个过程必然在有限步内终止。当某一步余数为 0 时，最后一个非零余数 rₖ 就是 gcd(a, b)。

证明正确性：反复应用引理 1.1： gcd(a, b) = gcd(b, r₁) = gcd(r₁, r₂) = ... = gcd(rₖ₋₁, rₖ) = gcd(rₖ, 0) = rₖ。

例 1.4：计算 gcd(12345, 54321)。

解：我们逐行列出计算过程：

54321 = 12345 × 4 + 4941
12345 = 4941 × 2 + 2463
 4941 = 2463 × 2 + 15
 2463 = 15 × 164 + 3
   15 = 3 × 5 + 0

最后一个非零余数是 3，所以 gcd(12345, 54321) = 3。□

例 1.5：计算 gcd(89, 55)。这两个数恰好是斐波那契数列中相邻的两项。

89 = 55 × 1 + 34
55 = 34 × 1 + 21
34 = 21 × 1 + 13
21 = 13 × 1 + 8
13 = 8 × 1 + 5
 8 = 5 × 1 + 3
 5 = 3 × 1 + 2
 3 = 2 × 1 + 1
 2 = 1 × 2 + 0

gcd(89, 55) = 1，所以 89 和 55 互素。注意每一步的商都是 1（除了最后一步），这正是斐波那契数的特征，也是使辗转相除法步数最多的"最坏情况"。□

扩展欧几里得算法

辗转相除法不仅能计算最大公因数，还可以向后回代，找到整数 x 和 y 使得

ax + by = gcd(a, b)

这称为贝祖等式（Bézout's identity）。具体方法是将辗转相除过程中的每一步改写为余数的表达式，然后从最后一步向前代入。

例 1.6：对于 a = 89, b = 55，求 x, y 使得 89x + 55y = 1。

解：从辗转相除的倒数第二步开始回代：

1 = 3 - 1 × 2
  = 3 - 1 × (5 - 1 × 3) = 2 × 3 - 1 × 5
  = 2 × (8 - 1 × 5) - 1 × 5 = 2 × 8 - 3 × 5
  = 2 × 8 - 3 × (13 - 1 × 8) = -3 × 13 + 5 × 8
  = -3 × 13 + 5 × (21 - 1 × 13) = 5 × 21 - 8 × 13
  = 5 × 21 - 8 × (34 - 1 × 21) = -8 × 34 + 13 × 21
  = -8 × 34 + 13 × (55 - 1 × 34) = 13 × 55 - 21 × 34
  = 13 × 55 - 21 × (89 - 1 × 55) = -21 × 89 + 34 × 55

因此 x = -21，y = 34。验证：89 × (-21) + 55 × 34 = -1869 + 1870 = 1。□

扩展欧几里得算法的重要性：它是求解一次同余方程（第3章）、计算乘法逆元的基础工具。

1.3 最小公倍数与性质

设 a 和 b 是非零整数。称整数 m 为 a 和 b 的一个公倍数，如果 a | m 且 b | m。a 和 b 的正公倍数中最小的那个称为它们的最小公倍数，记作

lcm(a, b) 或 [a, b]

例如，lcm(12, 18) = 36，lcm(15, 28) = 420。

定理 1.2：对于任意两个正整数 a 和 b，

gcd(a, b) · lcm(a, b) = a · b

m = da'b't = (ab/d) · t

要使 m 为正且最小，取 t = 1，得 lcm(a, b) = ab/d。□

注意：这个公式仅对两个数成立。对于三个及以上的数，类似等式一般不成立。例如 gcd(2, 3, 5) = 1，lcm(2, 3, 5) = 30，但 2 × 3 × 5 = 30 ≠ 1 × 30，这个例子"恰好"成立，但一般不能用此公式。对于多个数，需要用质因数分解来计算 gcd 和 lcm。

1.4 算术基本定理

算术基本定理是数论的基石。它告诉我们：大于 1 的每一个整数都可以唯一地分解为素数的乘积。

什么是素数

一个大于 1 的整数 p 称为素数，如果它的正因数只有 1 和 p 本身。大于 1 且不是素数的整数称为合数。

例如，2, 3, 5, 7, 11, 13, 17, 19, 23, 29 都是素数；4, 6, 8, 9, 10, 12 都是合数。

注意：1 既不是素数也不是合数。这个规定看似随意，实际上是为了保证算术基本定理中"唯一分解"的简洁性。如果把 1 算作素数，那么 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3，唯一性将不复存在。

存在性证明

定理 1.3（分解的存在性）：每个大于 1 的整数都可以写成素数的乘积。

证明：使用强归纳法。当 n = 2 时，2 本身是素数，结论成立。假设对所有满足 2 ≤ k < n 的整数 k，结论成立。考虑 n：

如果 n 是素数，结论直接成立。
如果 n 是合数，则存在整数 a, b 满足 1 < a, b < n 且 n = ab。由归纳假设，a 和 b 都可以分解为素数的乘积，因此 n 的分解只需将 a 和 b 的分解拼接即可。

唯一性证明

要证明分解的唯一性，我们需要一个关键的引理：

引理 1.2（欧几里得引理）：如果 p 是素数，且 p | ab，则 p | a 或 p | b。

证明：假设 p ∤ a。由于 p 是素数，其正因数只有 1 和 p，而 p ∤ a，所以 gcd(p, a) = 1。由贝祖等式，存在整数 x, y 使得 px + ay = 1。两边同乘 b：

pbx + aby = b

由于 p | pbx 且 p | aby（因为 p | ab），所以 p | (pbx + aby) = b。□

推广：如果素数 p | a₁a₂...aₖ，则 p 至少整除其中一个因子。这可以由归纳法直接得出。

定理 1.4（分解的唯一性）：大于 1 的整数的素数分解在因子的排列顺序不计的情况下是唯一的。

证明：假设存在两种分解： n = p₁p₂...pᵣ = q₁q₂...qₛ 其中所有 pᵢ 和 qⱼ 都是素数。

我们对第一个分解中的素数个数 r 用归纳法。r = 1 时，n = p₁ 是素数，那么第二个分解只能是 p₁ 本身（因为素数不能分解为多个大于 1 的因数的乘积，且 q₁ 必整除 p₁）。

对于 r > 1：p₁ | n = q₁q₂...qₛ，由欧几里得引理的推广，p₁ 整除某个 qⱼ。由于 qⱼ 是素数，必有 p₁ = qⱼ。消去这个公因子，得到 p₂...pᵣ = q₁...qⱼ₋₁ qⱼ₊₁...qₛ 左边有 r-1 个因子，由归纳假设，两边在排列顺序不计的意义下相同，从而原分解唯一。□

算术基本定理（完整陈述）：每个大于 1 的整数 n 可以唯一地表示为 n = p₁^α₁ · p₂^α₂ · ... · pₖ^αₖ 其中 p₁ < p₂ < ... < pₖ 是素数，αᵢ 是正整数。这个表示称为 n 的标准分解。

例 1.7：将 360 写成标准分解形式。解：360 = 2³ × 3² × 5。验证：8 × 9 × 5 = 360。□

例 1.8：利用标准分解求 gcd(252, 198) 和 lcm(252, 198)。解：252 = 2² × 3² × 7，198 = 2 × 3² × 11。 gcd：取每个素数的较小指数：2¹ × 3² = 18。 lcm：取每个素数的较大指数：2² × 3² × 7 × 11 = 2772。验证：18 × 2772 = 49896 = 252 × 198。□

第 1 章练习题

证明：三个连续整数的乘积一定被 6 整除。
用辗转相除法计算 gcd(2023, 1395)。
用扩展欧几里得算法求 x, y 使得 2023x + 1395y = gcd(2023, 1395)。
证明：若 a | bc 且 gcd(a, b) = 1，则 a | c。
用标准分解法求 gcd(9450, 2925) 和 lcm(9450, 2925)。

第 2 章同余理论

2.1 同余的概念与基本性质

同余的定义

同余是数论中最优雅的抽象之一。它的基本思想是：我们只关心整数除以某个固定数后的余数。

定义：设 m 是正整数。如果 m | (a - b)，我们就说 a 与 b 模 m 同余，记作

a ≡ b (mod m)

读作"a 同余于 b 模 m"。m 称为模数。

换句话说，a ≡ b (mod m) 意味着 a 和 b 除以 m 有相同的余数。

例 2.1：

17 ≡ 3 (mod 7)，因为 17 - 3 = 14 = 7 × 2
100 ≡ 0 (mod 25)，因为 100 被 25 整除
-8 ≡ 2 (mod 5)，因为 -8 - 2 = -10 = 5 × (-2)
今天星期三，100 天后星期几？100 ≡ 2 (mod 7)，星期三 + 2 = 星期五

同余的基本性质

同余关系是一个等价关系，即满足：

自反性：a ≡ a (mod m)
对称性：若 a ≡ b (mod m)，则 b ≡ a (mod m)
传递性：若 a ≡ b (mod m) 且 b ≡ c (mod m)，则 a ≡ c (mod m)

更重要的是，同余式可以像等式一样进行许多运算：

定理 2.1（同余的运算性质）：若 a ≡ b (mod m) 且 c ≡ d (mod m)，则

a + c ≡ b + d (mod m)
a - c ≡ b - d (mod m)
ac ≡ bd (mod m)

证明：(1) 由条件，m | (a - b) 且 m | (c - d)，所以 m | ((a - b) + (c - d)) = (a + c) - (b + d)。(2) 类似。(3) ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d)，而 m 整除 a - b 和 c - d，所以 m | (ac - bd)。

幂运算：由性质 (3) 归纳可得：若 a ≡ b (mod m)，则 aᵏ ≡ bᵏ (mod m) 对任意正整数 k 成立。

注意：除法需要额外条件。一般来说，ca ≡ cb (mod m) 不能直接推出 a ≡ b (mod m)。例如，2 × 3 ≡ 2 × 7 (mod 8)，因为 6 ≡ 14 (mod 8)，但 3 ≢ 7 (mod 8)。正确规则是：

定理 2.2（同余的消去律）：若 ca ≡ cb (mod m) 且 gcd(c, m) = d，则 a ≡ b (mod m/d)。特别地，若 gcd(c, m) = 1，则 a ≡ b (mod m)。

证明：由条件，m | c(a - b)，即 m/d | (c/d)(a - b)。由于 gcd(m/d, c/d) = 1（这是消去公因子的关键），所以 m/d | (a - b)，即 a ≡ b (mod m/d)。

例 2.2：利用同余性质快速计算 7²²² 的个位数。解：个位数就是模 10 的余数。注意到 7² = 49 ≡ 9 (mod 10)，7⁴ ≡ 9² = 81 ≡ 1 (mod 10)。现在 222 ÷ 4 = 55 余 2，所以 7²²² = (7⁴)⁵⁵ × 7² ≡ 1⁵⁵ × 9 ≡ 9 (mod 10)。因此 7²²² 的个位数是 9。□

2.2 完全剩余系与简化剩余系

完全剩余系

模 m 的完全剩余系（Complete Residue System，CRS）是一组 m 个整数，它们两两模 m 不同余。换句话说，这 m 个数恰好覆盖了模 m 的所有可能的余数 0, 1, 2, ..., m-1。

最简单的完全剩余系是 {0, 1, 2, ..., m-1}，称为最小非负剩余系。

例 2.3：模 8 的完全剩余系可以是 {0, 1, 2, 3, 4, 5, 6, 7}，也可以是 {1, 2, 3, 4, 5, 6, 7, 8}，甚至 {100, 101, 102, 103, 104, 105, 106, 107}。

定理 2.3：设 {a₁, a₂, ..., aₘ} 是模 m 的一个完全剩余系，且 gcd(k, m) = 1，则 {ka₁ + b, ka₂ + b, ..., kaₘ + b} 也是模 m 的一个完全剩余系。

证明：只需证明这 m 个数两两模 m 不同余。若 kaᵢ + b ≡ kaⱼ + b (mod m)，则 kaᵢ ≡ kaⱼ (mod m)。由于 gcd(k, m) = 1，由消去律得 aᵢ ≡ aⱼ (mod m)，从而 i = j。□

简化剩余系与欧拉函数

在模 m 的完全剩余系中，有些数与 m 互素，有些不互素。那些与 m 互素的剩余类构成了所谓的简化剩余系（Reduced Residue System，RRS）。

定义：模 m 的简化剩余系是一组与 m 互素的整数，它们两两模 m 不同余，且其个数等于所有与 m 互素的剩余类的个数。

模 m 的简化剩余系中元素的个数记为 φ(m)，称为欧拉函数。

例如：

模 8：与 8 互素的剩余类是 1, 3, 5, 7，所以 φ(8) = 4。
模 10：与 10 互素的剩余类是 1, 3, 7, 9，所以 φ(10) = 4。
模 7（素数）：所有 1 到 6 都与 7 互素，φ(7) = 6。

一般地，对于素数 p，φ(p) = p - 1。

构造简化剩余系：取模 m 的最小非负完全剩余系 {0, 1, ..., m-1}，从中删去所有与 m 不互素的数，剩下的就是最小非负简化剩余系。

定理 2.4：设 {r₁, r₂, ..., r_{φ(m)}} 是模 m 的一个简化剩余系，且 gcd(a, m) = 1，则 {ar₁, ar₂, ..., ar_{φ(m)}} 也是模 m 的一个简化剩余系。

证明：首先，由于 gcd(a, m) = 1 且 gcd(rᵢ, m) = 1，所以 gcd(arᵢ, m) = 1。其次，若 arᵢ ≡ arⱼ (mod m)，由消去律得 rᵢ ≡ rⱼ (mod m)，从而 i = j。因此这 φ(m) 个数确是一个简化剩余系。□

这个简单的定理是下一节欧拉定理证明的核心。

2.3 欧拉定理与费马小定理

欧拉定理

定理 2.5（欧拉定理）：若 a 与 m 互素（即 gcd(a, m) = 1），则

a^{φ(m)} ≡ 1 (mod m)

证明：设 {r₁, r₂, ..., r_{φ(m)}} 是模 m 的最小非负简化剩余系。由定理 2.4，{ar₁, ar₂, ..., ar_{φ(m)}} 也是模 m 的简化剩余系。这两个集合中的元素模 m 的余数集合完全相同（只是排列顺序不同）。

因此，两个集合中所有元素的乘积模 m 同余：

(ar₁)(ar₂)...(ar_{φ(m)}) ≡ r₁r₂...r_{φ(m)} (mod m)

即 a^{φ(m)} · (r₁r₂...r_{φ(m)}) ≡ r₁r₂...r_{φ(m)} (mod m)

由于每个 rᵢ 都与 m 互素，它们的乘积也与 m 互素。由消去律：

a^{φ(m)} ≡ 1 (mod m)

证毕。□

例 2.4：求 3²⁰²⁴ 除以 10 的余数。解：φ(10) = 4。因为 gcd(3, 10) = 1，由欧拉定理，3⁴ ≡ 1 (mod 10)。 2024 = 4 × 506，所以 3²⁰²⁴ = (3⁴)⁵⁰⁶ ≡ 1⁵⁰⁶ ≡ 1 (mod 10)。□

费马小定理

当模数 m 为素数 p 时，φ(p) = p - 1，欧拉定理变为：

定理 2.6（费马小定理）：设 p 为素数，且 a 不被 p 整除，则

a^{p-1} ≡ 1 (mod p)

等价形式（对任意整数 a 成立）：

aᵖ ≡ a (mod p)

费马小定理是数论中应用最广泛的定理之一。它可以用来：

快速计算大幂的模；
进行素性测试（但如果反用，有卡迈克尔数的反例）；
构造密码协议。

例 2.5：证明 3¹⁰⁰ - 1 被 11 整除。解：11 是素数，且 3 不被 11 整除。由费马小定理，3¹⁰ ≡ 1 (mod 11)。 3¹⁰⁰ = (3¹⁰)¹⁰ ≡ 1¹⁰ ≡ 1 (mod 11)，所以 11 | (3¹⁰⁰ - 1)。□

例 2.6：求 7⁸⁹ 除以 13 的余数。解：由费马小定理，7¹² ≡ 1 (mod 13)（因为 13 是素数且 gcd(7, 13) = 1）。 89 = 12 × 7 + 5，所以 7⁸⁹ = (7¹²)⁷ × 7⁵ ≡ 1⁷ × 7⁵ (mod 13)。计算 7⁵ mod 13：7² = 49 ≡ 10 (mod 13)，7⁴ ≡ 10² = 100 ≡ 9 (mod 13)，7⁵ ≡ 9 × 7 = 63 ≡ 11 (mod 13)。因此 7⁸⁹ ≡ 11 (mod 13)。□

2.4 威尔逊定理

定理 2.7（威尔逊定理）：正整数 p > 1 是素数当且仅当

(p - 1)! ≡ -1 (mod p)

证明：

（必要性）设 p 为素数。对于 2, 3, ..., p-2 中的每个数 a，方程 ax ≡ 1 (mod p) 有唯一解 x，且 x 也在这个范围内（因为 a ≠ 1, p-1，其逆元也不等于自身）。更关键的是，x ≠ a（否则 a² ≡ 1 (mod p) ⇒ p | (a-1)(a+1) ⇒ a ≡ 1 或 a ≡ -1 (mod p)，与 a 的范围矛盾）。

因此，2, 3, ..., p-2 这 p-3 个数可以两两配对（每对的乘积 ≡ 1 mod p），而 1 和 p-1 各自留下：1 的逆就是自身，p-1 ≡ -1 (mod p) 的逆也是自身。于是

(p-1)! ≡ 1 × (-1) × 1^{(p-3)/2} ≡ -1 (mod p)

（充分性）若 n 是合数且 n > 4，则存在 a, b 满足 1 < a, b < n 且 n = ab。若 a ≠ b，则 a 和 b 都出现在乘积 (n-1)! 中，故 n | (n-1)!，即 (n-1)! ≡ 0 ≢ -1 (mod n)。若 a = b 即 n = a²，则当 a > 2 时，a 和 2a 都 < n（因为 n = a² ≥ 3a），两者都出现在 (n-1)! 中，仍有 n | (n-1)!。n = 4 单独检验：(4-1)! = 6 ≡ 2 ≢ -1 (mod 4)。

综上所述，条件成立当且仅当 p 是素数。□

例 2.7：判断 11 是否为素数（用威尔逊定理）。解：(11-1)! = 10! = 3628800。3628800 ÷ 11 = 329891 余 -1（即 10）。验证：3628800 + 1 = 3628801 = 11 × 329891。所以 11 是素数。

注意：威尔逊定理在理论上很优美，但因为计算 (p-1)! 的计算量巨大，实际中从不用于素性测试。它更多是作为理论工具使用。

第 2 章练习题

证明：若 a ≡ b (mod m) 且 n | m，则 a ≡ b (mod n)。
求 5¹⁰⁰ 除以 7 的余数。
构造模 15 的最小非负简化剩余系，计算 φ(15)。
利用费马小定理证明：对任意整数 a，a⁷ - a 被 42 整除。（提示：42 = 2 × 3 × 7）
用威尔逊定理证明：若 p 是奇素数，则 1²·2²·3²·...·(p-1)² ≡ (-1)^{(p+1)/2} (mod p)。

第 3 章同余方程

3.1 一次同余方程与逆元

一次同余方程

一次同余方程的一般形式是：

ax ≡ b (mod m)

其中 a, b, m 是已知整数，我们要求整数 x。

定理 3.1（可解条件）：一次同余方程 ax ≡ b (mod m) 有解当且仅当 gcd(a, m) | b。设 d = gcd(a, m)，则解数为 d（模 m 意义下）。

证明：方程有解等价于存在整数 x, y 使得 ax - b = my，即 ax - my = b。这是一次不定方程（见第8章），有解当且仅当 gcd(a, m) | b。

当 d | b 时，在模 m 意义下恰有 d 个不同的解。具体来说，先求出模 m/d 下的唯一解 x₀，然后全部解为 x₀, x₀ + m/d, x₀ + 2m/d, ..., x₀ + (d-1)m/d (mod m)。□

乘法逆元

在方程 ax ≡ 1 (mod m) 的特殊情形下，如果 gcd(a, m) = 1，方程有唯一解，我们称这个解为 a 模 m 的乘法逆元，记作 a⁻¹ (mod m)。

计算逆元的方法：使用扩展欧几里得算法求 ax + my = 1 中的 x，则 x mod m 即为 a⁻¹。

例 3.1：求 7 模 26 的逆元。解：用扩展欧几里得算法求 7x + 26y = 1：

26 = 7 × 3 + 5
 7 = 5 × 1 + 2
 5 = 2 × 2 + 1
 2 = 1 × 2 + 0

回代：

1 = 5 - 2 × 2 = 5 - 2 × (7 - 5) = 3 × 5 - 2 × 7
  = 3 × (26 - 7 × 3) - 2 × 7 = 3 × 26 - 11 × 7

所以 -11 × 7 ≡ 1 (mod 26)，即 15 × 7 ≡ 1 (mod 26)。验证：15 × 7 = 105 = 26 × 4 + 1。□

例 3.2：解同余方程 14x ≡ 30 (mod 22)。解：首先 d = gcd(14, 22) = 2。因为 2 | 30，方程有解，且有 2 个解（模 22）。

化简：除以 d = 2（注意模数也要除以 2）： 7x ≡ 15 (mod 11)

求 7⁻¹ mod 11：7 × 8 = 56 ≡ 1 (mod 11)，所以逆元是 8。 x₀ ≡ 15 × 8 = 120 ≡ 10 (mod 11)

模 22 下的全部解： x₁ = 10，x₂ = 10 + 11 = 21

验证：14 × 10 = 140 = 22 × 6 + 8... 不对。让我重算。14 × 10 = 140。140 mod 22 = 140 - 22 × 6 = 140 - 132 = 8 ≠ 30。

让我重新检查：d | b，即 2 | 30，成立。化简方程：14x ≡ 30 (mod 22) ⇒ 7x ≡ 15 (mod 11)。求 7⁻¹ mod 11：7 × 8 = 56 ≡ 1 (mod 11) ✓。x ≡ 15 × 8 = 120 ≡ 10 (mod 11)。所以模 11 下 x ≡ 10。

模 22 下的两个解：x = 10 和 x = 10 + 11 = 21。验证：14 × 21 = 294 = 22 × 13 + 8... 也有问题。

让我仔细算：294 ÷ 22 = 13 余 8。但方程要求 ≡ 30 (mod 22)。30 mod 22 = 8。

所以 14 × 10 = 140 ≡ 8 (mod 22) ✓！14 × 21 = 294 ≡ 8 (mod 22) ✓！

两个解都是正确的。我之前的检查中把 30 (mod 22) 看成了 30 本身，但实际上是要求余数为 8。□

3.2 中国剩余定理

中国剩余定理（Chinese Remainder Theorem，CRT）是数论中最优美的定理之一，起源于中国古代的"物不知数"问题。

"物不知数"问题

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

这来自公元四五世纪的《孙子算经》。用现代语言表述就是：求一个数 x，满足同余方程组：

x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7)

定理 3.2（中国剩余定理）：设 m₁, m₂, ..., mₖ 是两两互素的正整数。则对于任意整数 a₁, a₂, ..., aₖ，同余方程组

x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂) ... x ≡ aₖ (mod mₖ)

在模 M = m₁m₂...mₖ 下有唯一解。

构造性证明：

设 M = m₁m₂...mₖ，Mᵢ = M / mᵢ。由于 mᵢ 两两互素，gcd(Mᵢ, mᵢ) = 1。用扩展欧几里得算法求 Mᵢ⁻¹ (mod mᵢ)，即求 yᵢ 使得 Mᵢ yᵢ ≡ 1 (mod mᵢ)。

令 x = a₁M₁y₁ + a₂M₂y₂ + ... + aₖMₖyₖ

验证：对每个 i，当 j ≠ i 时，Mⱼ ≡ 0 (mod mᵢ)（因为 mᵢ | Mⱼ）。因此 x ≡ aᵢMᵢyᵢ ≡ aᵢ × 1 ≡ aᵢ (mod mᵢ ✓

唯一性：若 x₁ 和 x₂ 都是解，则 x₁ ≡ x₂ (mod mᵢ) 对所有 i 成立，即 mᵢ | (x₁ - x₂)。由于 mᵢ 两两互素，M | (x₁ - x₂)，故 x₁ ≡ x₂ (mod M)。□

例 3.3：解"物不知数"问题。

M = 3 × 5 × 7 = 105。 M₁ = 105/3 = 35，M₂ = 105/5 = 21，M₃ = 105/7 = 15。

需求 Mᵢ⁻¹ mod mᵢ：

35y₁ ≡ 1 (mod 3)：35 ≡ 2 (mod 3)，2 × 2 = 4 ≡ 1 (mod 3)，故 y₁ = 2。
21y₂ ≡ 1 (mod 5)：21 ≡ 1 (mod 5)，y₂ = 1。
15y₃ ≡ 1 (mod 7)：15 ≡ 1 (mod 7)，y₃ = 1。

x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 140 + 63 + 30 = 233

x ≡ 233 ≡ 23 (mod 105)。最小正整数解是 23。

验证：23 ÷ 3 余 2 ✓，23 ÷ 5 余 3 ✓，23 ÷ 7 余 2 ✓。□

非互素模数的情形

当模数不两两互素时，中国剩余定理不能直接应用，需要逐个方程合并。

定理 3.3（一般情形）：同余方程组 x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) 有解当且仅当 a₁ ≡ a₂ (mod gcd(m₁, m₂))。若有解，则在模 lcm(m₁, m₂) 下唯一。

例 3.4：解 x ≡ 3 (mod 6), x ≡ 7 (mod 10)。解：gcd(6, 10) = 2。检查 3 ≡ 7 (mod 2)：3 mod 2 = 1，7 mod 2 = 1，条件满足。

第一个方程：x = 6k + 3。代入第二个：6k + 3 ≡ 7 (mod 10) ⇒ 6k ≡ 4 (mod 10) ⇒ 3k ≡ 2 (mod 5)（除以 gcd(6, 10) = 2）

3⁻¹ mod 5 = 2（因为 3 × 2 = 6 ≡ 1）。k ≡ 2 × 2 = 4 (mod 5)。 k = 5t + 4，x = 6(5t + 4) + 3 = 30t + 27。

所以 x ≡ 27 (mod 30)。验证：27 mod 6 = 3 ✓，27 mod 10 = 7 ✓。□

3.3 应用：大数模运算拆分

中国剩余定理的一个实用价值是将大模数的运算拆分为多个小模数的运算。这在密码学中尤其重要。

原理：如果我们要计算 aᵇ (mod n)，而 n = pq 是两个大素数的乘积，我们可以分别计算 aᵇ mod p 和 aᵇ mod q，然后用中国剩余定理合并结果。这比直接计算模 n 下的幂快约 4 倍。

例 3.5：计算 2¹⁰⁰ mod 77（其中 77 = 7 × 11）。

分别计算：

mod 7：由费马小定理，2⁶ ≡ 1 (mod 7)。100 = 6 × 16 + 4，故 2¹⁰⁰ ≡ 2⁴ = 16 ≡ 2 (mod 7)。
mod 11：2¹⁰ ≡ 1 (mod 11)。100 = 10 × 10，故 2¹⁰⁰ ≡ 1 (mod 11)。

解同余方程组 x ≡ 2 (mod 7), x ≡ 1 (mod 11)： M₁ = 11，M₁⁻¹ mod 7 = 11⁻¹ ≡ 4⁻¹ ≡ 2 (mod 7)。 M₂ = 7，M₂⁻¹ mod 11 = 7⁻¹ ≡ 8 (mod 11)。

x = 2 × 11 × 2 + 1 × 7 × 8 = 44 + 56 = 100 ≡ 23 (mod 77)。

直接验证：2¹⁰⁰ mod 77？……让读者自己计算器验证吧。□

3.4 习题与思考

解同余方程 6x ≡ 15 (mod 21)。
求 13 模 60 的乘法逆元。
解"韩信点兵"问题：x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7)。
解方程组：x ≡ 5 (mod 8), x ≡ 1 (mod 9), x ≡ 2 (mod 7)。
判断方程组 x ≡ 1 (mod 4), x ≡ 3 (mod 6) 是否有解。如有，求模 lcm(4, 6) 下的解。
用中国剩余定理计算 3²⁰ mod 35。

第 4 章素数

4.1 素数无穷多的证明

素数最大的特征是什么？它们有无穷多个。这个古老而深刻的结论至少有几十种证明。我们介绍其中最经典的两种。

欧几里得的经典证明

定理 4.1：素数有无穷多个。

欧几里得证明（约公元前300年）：假设素数只有有限多个，设为 p₁, p₂, ..., pₖ。考虑

N = p₁p₂...pₖ + 1

N 大于 1，必有素因子 q。但 q 不能是 p₁, ..., pₖ 中的任何一个，因为 N 除以任何 pᵢ 的余数都是 1。所以 q 是一个新的素数，与假设矛盾。□

这个证明简洁到令人叹为观止。它不需要任何高深工具，却在逻辑上无可挑剔，被誉为数学证明之美的典范。

欧拉的分析证明（概要）

欧拉在 1737 年给出了一个利用无穷级数的方法：

思路：假设素数只有有限个 p₁, ..., pₖ。考虑调和级数的变体：

∑{n=1}^{∞} 1/n = ∏{p 素数} (1 + 1/p + 1/p² + ...) = ∏_{p} (1 - 1/p)⁻¹

如果素数只有有限个，右边的乘积是有限数。但左边（调和级数）是发散的。矛盾。

这个证明的美妙之处在于将数论与分析学联系起来，为解析数论埋下了种子。

狄利克雷定理

一个自然的推广是：在等差数列 a, a+d, a+2d, ... 中是否也有无穷多个素数？狄利克雷在 1837 年证明了：

狄利克雷定理：若 gcd(a, d) = 1，则等差数列 {a + kd} 中包含无穷多个素数。

例如，形如 4k+1 的素数有无穷多个，形如 4k+3 的素数也有无穷多个。这个定理的证明需要使用复分析，远超本书范围，但它的结论本身是数论的基本事实。

4.2 素数定理简介

素数有无穷多个，但它们的分布规律是什么？

π(x) 函数

设 π(x) 表示不超过 x 的素数个数。例如：π(10) = 4（2, 3, 5, 7），π(100) = 25，π(1000) = 168。

高斯在 15 岁时（1792 年）通过手工计算素数表，猜测 π(x) 的增长速度约等于 x / ln x。勒让德在 1798 年独立给出了类似的猜想。但直到 1896 年，阿达玛和德·拉·瓦莱-普桑才分别用复分析独立证明了这一猜想。

素数定理：当 x → ∞ 时，

π(x) ~ x / ln x

其中"~"表示两边的比值趋向于 1。

让我们看一些具体数据：

x	π(x)	x / ln x	误差	相对误差
10	4	4.3	-0.3	-7.5%
100	25	21.7	+3.3	+13.2%
1,000	168	144.8	+23.2	+13.8%
10,000	1,229	1,085.7	+143.3	+11.7%
100,000	9,592	8,685.9	+906.1	+9.4%
1,000,000	78,498	72,382.4	+6,115.6	+7.8%
10,000,000	664,579	620,420.7	+44,158.3	+6.6%

可以看到，随着 x 增大，相对误差逐渐减小——这正是"渐近等价"的含义。

更好的近似：对数积分 Li(x) = ∫₂ˣ dt/ln t 给出了更精确的估计。

4.3 寻找素数：筛法与简单判定

厄拉托色尼筛法

厄拉托色尼（约公元前276—前194年）发明了最早的素数筛法。算法非常直观：

算法（厄拉托色尼筛法）：要找出不超过 n 的所有素数：

写出 2 到 n 的所有整数。
圈出 2，划掉 2 的所有倍数（4, 6, 8, ...）。
圈出下一个未划掉的数（即 3），划掉它的所有倍数。
重复，直到处理到 √n。

伪代码：

function Sieve(n):
    is_prime[2..n] ← true
    for i = 2 to √n:
        if is_prime[i]:
            for j = i*i to n step i:
                is_prime[j] ← false
    return all i with is_prime[i] = true

时间复杂度：O(n log log n)，非常高效。

例 4.1：用筛法找出 30 以内的所有素数。

初始： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
p=2：  (2) 3 x 5 x 7 x 9  x 11  x 13  x 15  x 17  x 19  x 21  x 23  x 25  x 27  x 29  x
p=3：  (2)(3) x 5 x 7 x x  x 11  x 13  x  x  x 17  x 19  x  x  x 23  x 25  x  x  x 29  x
p=5：  (2)(3) x(5) x 7 x x  x 11  x 13  x  x  x 17  x 19  x  x  x 23  x  x  x  x  x 29  x
p=7 > √30，停止。

素数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29

素性测试

如何判断一个给定的数 n 是否为素数？

试除法（最朴素的方法）：用 2 到 √n 之间的所有素数试除 n。如果都不能整除，n 就是素数。这个方法对小 n 足够好，但对大 n（如 100 位以上）完全不可行。

费马测试：根据费马小定理，如果 n 是素数且 gcd(a, n) = 1，则 aⁿ⁻¹ ≡ 1 (mod n)。因此，如果对某个 a，aⁿ⁻¹ ≢ 1 (mod n)，则 n 一定是合数。但反之不成立！

卡迈克尔数：存在合数 n 使得对所有满足 gcd(a, n) = 1 的 a，都有 aⁿ⁻¹ ≡ 1 (mod n)。这类数称为卡迈克尔数（Carmichael numbers）。最小的卡迈克尔数是 561 = 3 × 11 × 17。

Miller-Rabin 素性测试：这是目前实际应用中最常用的概率素性测试。它基于以下观察：如果 n 是奇素数，令 n-1 = 2ˢd（d 为奇数），则对任意与 n 互素的 a，要么 aᵈ ≡ 1 (mod n)，要么存在 r ∈ [0, s-1] 使得 a^(2ʳᵈ) ≡ -1 (mod n)。

Miller-Rabin 测试是概率性的：对于合数，每次测试以至少 3/4 的概率检测出。多次独立测试后，错误概率可降至任意小。更重要的是，如果广义黎曼猜想成立，只需测试很少的几个 a 就能确定性判断。

4.4 梅森素数与完全数

梅森数

形如 Mₙ = 2ⁿ - 1 的数称为梅森数。一个自然的问题是：何时 Mₙ 是素数？

定理 4.2：若 2ⁿ - 1 是素数，则 n 必为素数。

证明：若 n = ab（a, b > 1），则 2ⁿ - 1 = (2ᵃ)ᵇ - 1 可被 2ᵃ - 1 整除（因式分解公式）。因此 2ⁿ - 1 是合数，矛盾。□

注意：逆命题不成立。例如 n = 11 是素数，但 2¹¹ - 1 = 2047 = 23 × 89，不是素数。

当 Mₚ 是素数时，称其为梅森素数。到 2024 年，已知的梅森素数共有 52 个。最大的已知素数是 2¹³⁶²⁷⁹⁸⁴¹ - 1（第52个梅森素数），有超过4100万位。

卢卡斯-莱默测试（叙述）：对于奇素数 p，定义序列 s₀ = 4, sₖ₊₁ = sₖ² - 2 (mod Mₚ)。则 Mₚ 是素数当且仅当 sₚ₋₂ ≡ 0 (mod Mₚ)。

这个测试极为高效，是发现所有大梅森素数的关键工具。

完全数

一个正整数 n 称为完全数，如果它等于其所有真因数（小于 n 的正因数）之和。等价地，σ(n) = 2n，其中 σ(n) 是所有正因数之和。

最小的完全数是 6（真因数 1, 2, 3，1 + 2 + 3 = 6）和 28（1 + 2 + 4 + 7 + 14 = 28）。

定理 4.3（欧几里得-欧拉定理）：偶数 n 是完全数当且仅当 n = 2ᵖ⁻¹(2ᵖ - 1)，其中 2ᵖ - 1 是梅森素数。

证明：(⇐) 设 2ᵖ - 1 = q 是素数，n = 2ᵖ⁻¹q。由于 gcd(2ᵖ⁻¹, q) = 1，σ(n) = σ(2ᵖ⁻¹)σ(q) = (2ᵖ - 1)(q + 1) = (2ᵖ - 1)(2ᵖ) = 2·2ᵖ⁻¹(2ᵖ - 1) = 2n。所以 n 是完全数。

(⇒) 设 n 是偶完全数，则 n = 2ᵏm，其中 k ≥ 1，m 为奇数。 σ(n) = σ(2ᵏ)σ(m) = (2ᵏ⁺¹ - 1)σ(m)。因为 n 是完全数，σ(n) = 2n = 2ᵏ⁺¹m。所以

(2ᵏ⁺¹ - 1)σ(m) = 2ᵏ⁺¹m

由此 σ(m) = (2ᵏ⁺¹m) / (2ᵏ⁺¹ - 1) = m + m/(2ᵏ⁺¹ - 1)。

因为 σ(m) 是整数，2ᵏ⁺¹ - 1 必须整除 m。设 d = m/(2ᵏ⁺¹ - 1) 为正整数。

则 σ(m) = m + d。如果 d > 1，则 m 除了 1 和本身外至少还有 d 和 m/d 两个因数，但 m/d = 2ᵏ⁺¹ - 1。这意味着 σ(m) ≥ 1 + d + (2ᵏ⁺¹ - 1) + m = m + d + 2ᵏ⁺¹ > m + d = σ(m)，矛盾。

因此 d = 1，m = 2ᵏ⁺¹ - 1，σ(m) = m + 1，意味着 m 是素数。m = 2ᵏ⁺¹ - 1 是梅森素数（所以 k+1 必为素数）。令 p = k+1，则 n = 2ᵖ⁻¹(2ᵖ - 1)。□

这个定理意味着：偶完全数与梅森素数一一对应。目前是否存在奇完全数是数论中最大的未解问题之一。

4.5 因数分解的困难性

为什么不直接分解大数？

给定一个 300 位的合数，想找到它的素因子？试试就知道了——即使用最先进的计算机，这也可能需要比宇宙年龄更长的时间。

目前最好的通用分解算法：数域筛法（Number Field Sieve），其时间复杂度约为

O(e^{(c + o(1))(ln n)^{1/3} (ln ln n)^{2/3}})

其中 c ≈ 1.9。这个"亚指数"复杂度意味着：随着 n 位数的增加，分解难度增长得极快。一个 1024 位的 RSA 模数，用数域筛法的估算时间远超可接受范围。

量子计算的威胁：1994 年，彼得·肖尔（Peter Shor）提出了可以在多项式时间内分解大整数的量子算法。如果大规模量子计算机被建造出来，RSA 等基于因数分解的密码体制将被彻底攻破。

这也引出了下一章的主题——数论函数以及后续密码学的讨论。但在此之前，让我们先把注意力转回纯数论本身，探索那些优雅的数论函数和它们之间的深刻联系。

第 4 章练习题

用厄拉托色尼筛法找出 100 以内的所有素数。
证明：如果 n 是合数，则 n 至少有一个不大于 √n 的素因子。
验证 561 是卡迈克尔数（提示：需验证对所有 gcd(a, 561) = 1 的 a，a⁵⁶⁰ ≡ 1 (mod 561)）。
证明：若 2ᵖ - 1 是梅森素数，则 2ᵖ⁻¹(2ᵖ - 1) 的各位数字之和（重复求和直到一位数）是 1。
用试除法判断 2027 是否为素数。

第 5 章数论函数

5.1 欧拉函数 φ(n)

定义回顾

在第 2 章，我们初步引入了欧拉函数 φ(n)：它表示不超过 n 且与 n 互素的正整数的个数。亦即模 n 的简化剩余系的大小。

φ(1) = 1（约定），φ(6) = 2，φ(7) = 6，φ(8) = 4，φ(10) = 4。

φ(n) 的计算公式

定理 5.1（欧拉函数的积性）：若 gcd(m, n) = 1，则 φ(mn) = φ(m) · φ(n)。

证明概要：利用中国剩余定理。不超过 mn 且与 mn 互素的整数，与有序对 (a mod m, b mod n) 一一对应，其中 gcd(a, m) = 1 且 gcd(b, n) = 1。共有 φ(m) × φ(n) 种组合。□

引理 5.1：对于素数幂 pᵏ， φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ⁻¹(p - 1)

证明：不超过 pᵏ 的正整数共有 pᵏ 个。其中与 pᵏ 不互素的恰是 p 的倍数：p, 2p, ..., pᵏ⁻¹·p，共 pᵏ⁻¹ 个。所以与 pᵏ 互素的有 pᵏ - pᵏ⁻¹ 个。□

推论：设 n = p₁^α₁ · p₂^α₂ · ... · pₖ^αₖ 为标准分解，则

φ(n) = n · ∏_{p|n} (1 - 1/p)

也即： φ(n) = p₁^{α₁-1}(p₁ - 1) · p₂^{α₂-1}(p₂ - 1) · ... · pₖ^{αₖ-1}(pₖ - 1)

例 5.1：计算 φ(360)。

解：360 = 2³ × 3² × 5。使用公式： φ(360) = φ(2³) × φ(3²) × φ(5) = 2² × 2 × 3¹ × 2 × 4 = 4 × 2 × 3 × 2 × 4 = 96

或用乘积公式：φ(360) = 360 × (1 - 1/2) × (1 - 1/3) × (1 - 1/5) = 360 × 1/2 × 2/3 × 4/5 = 360 × 8/30 = 96。□

例 5.2：证明 φ(n) 为偶数对所有 n > 2 成立。证明：若 n 的标准分解中包含奇素数因子 p，则 φ(n) 含有因子 (p-1)，而 p-1 是偶数，故 φ(n) 为偶数。若 n = 2ᵏ（k > 1），则 φ(n) = 2ᵏ⁻¹，当 k > 1 时也是偶数。唯一例外的情形是 n = 2，φ(2) = 1 为奇数。□

欧拉函数的经典恒等式

定理 5.2：对于任意正整数 n， ∑_{d|n} φ(d) = n

其中求和遍及 n 的所有正因数 d。

证明：考虑分数集合 {1/n, 2/n, ..., n/n}。将每个分数化为最简分数 a/d（其中 gcd(a, d) = 1，d | n）。分母为 d 的分数恰有 φ(d) 个。所有分数总计 n 个，故 ∑_{d|n} φ(d) = n。□

例 5.3：验证 n = 12 的情况。

12 的正因数：1, 2, 3, 4, 6, 12。 φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(6) = 2, φ(12) = 4。和 = 1 + 1 + 2 + 2 + 2 + 4 = 12。□

这个恒等式在下一节的莫比乌斯反演中将扮演关键角色。

5.2 约数个数函数 τ(n) 与约数和函数 σ(n)

定义与标准分解公式

设 n 为正整数。

约数个数函数 τ(n)（也记作 d(n)）：n 的正因数的个数。
约数和函数 σ(n)：n 的所有正因数之和。

定理 5.3：若 n = p₁^α₁ · p₂^α₂ · ... · pₖ^αₖ，则

τ(n) = (α₁ + 1)(α₂ + 1)...(αₖ + 1)

σ(n) = ∏_{i=1}^{k} (p_i^{α_i+1} - 1) / (p_i - 1)

证明：n 的每个正因数形如 p₁^β₁ · p₂^β₂ · ... · pₖ^βₖ，其中 0 ≤ βᵢ ≤ αᵢ。每个指数有 αᵢ + 1 种选择，故 τ(n) = ∏(αᵢ + 1)。σ 的公式来自等比数列求和。□

例 5.4：计算 τ(360) 和 σ(360)。

360 = 2³ × 3² × 5

τ(360) = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24。360 共有 24 个正因数。
σ(360) = (2⁴-1)/(2-1) × (3³-1)/(3-1) × (5²-1)/(5-1) = 15 × 13 × 6 = 1170

验证完全数 n = 28 = 2² × 7：

σ(28) = σ(2²) × σ(7) = (2³-1)/(2-1) × (7²-1)/(7-1) = 7 × 8 = 56 = 2 × 28。□

积性

τ(n) 和 σ(n) 都是积性函数：若 gcd(m, n) = 1，则 τ(mn) = τ(m)τ(n) 且 σ(mn) = σ(m)σ(n)。这个性质可以直接从标准分解公式推出。

5.3 莫比乌斯函数 μ(n) 与莫比乌斯反演

莫比乌斯函数

定义：莫比乌斯函数 μ(n) 定义如下：

μ(1) = 1；
若 n 有平方因子（即存在素数 p 使得 p² | n），则 μ(n) = 0；
若 n 是 k 个不同素数的乘积，则 μ(n) = (-1)ᵏ。

例如：

μ(1) = 1
μ(2) = -1，μ(3) = -1，μ(5) = -1（单个素数）
μ(6) = μ(2×3) = 1（两个不同素数）
μ(30) = μ(2×3×5) = -1（三个不同素数）
μ(4) = 0（有平方因子），μ(12) = 0，μ(18) = 0

关键性质：

定理 5.4：对于 n ≥ 1， ∑_{d|n} μ(d) = [n = 1]

其中 [n = 1] 是指示函数：当 n = 1 时值为 1，否则为 0。

证明：n = 1 时显然成立。设 n > 1，令 n = p₁^α₁...pₖ^αₖ。在 n 的所有因数中，只有那些不含平方因子的对和式有贡献（μ = 0 的项不影响和）。不含平方因子的因数对应于 {p₁, ..., pₖ} 的子集。含有 j 个素数的因子有 C(k, j) 个，每个贡献 (-1)ʲ。因此

∑{d|n} μ(d) = ∑{j=0}^{k} C(k, j) (-1)ʲ = (1 - 1)ᵏ = 0

□

例 5.5：验证 n = 12 的情况。

12 的因数：1, 2, 3, 4, 6, 12。 μ(1) = 1，μ(2) = -1，μ(3) = -1，μ(4) = 0，μ(6) = 1，μ(12) = 0。和 = 1 - 1 - 1 + 0 + 1 + 0 = 0。□

莫比乌斯反演公式

莫比乌斯反演是数论中最强大的工具之一，它可以将"所有除数之和"的关系反转。

定理 5.5（莫比乌斯反演）：设 f 和 F 是定义在正整数上的函数。则

F(n) = ∑_{d|n} f(d) （对所有 n ≥ 1）

当且仅当

f(n) = ∑_{d|n} μ(d) F(n/d) （对所有 n ≥ 1）

证明：(⇐) 要从 f 推出 F：直接计算 ∑{d|n} f(d) = ∑{d|n} ∑{e|d} μ(e) F(d/e)。交换求和次序，可化为 ∑{e|n} μ(e) ∑_{k|(n/e)} F(k)。这部分的详细展开留给读者作为练习，核心是利用定理 5.4 消去内层求和。(⇒) 方向类似。□

应用实例：从 φ 的恒等式反推 φ 的表达式。

已知 ∑_{d|n} φ(d) = n（定理 5.2）。在反演公式中取 F(n) = n，f(n) = φ(n)，则

φ(n) = ∑{d|n} μ(d) · (n/d) = n ∑{d|n} μ(d)/d

这给出了 φ(n) 的一个新表达式，它在解析数论中有重要应用。

具体计算 n = 12： φ(12) = 12 × (μ(1)/1 + μ(2)/2 + μ(3)/3 + μ(4)/4 + μ(6)/6 + μ(12)/12) = 12 × (1 - 1/2 - 1/3 + 0 + 1/6 + 0) = 12 × (1 - 0.5 - 0.333... + 0.166...) = 12 × (1 - 5/6 + 1/6) = 12 × 1/3 = 4

正确！φ(12) = 4。□

5.4 积性函数的一般理论

狄利克雷卷积

定义两个数论函数 f 和 g 的狄利克雷卷积 f ∗ g 为：

(f ∗ g)(n) = ∑_{d|n} f(d) · g(n/d)

基本性质：

交换律：f ∗ g = g ∗ f
结合律：(f ∗ g) ∗ h = f ∗ (g ∗ h)
单位元：定义 ε(n) = [n = 1]，则 f ∗ ε = ε ∗ f = f
恒等函数 I(n) = 1 和莫比乌斯函数 μ 的关系：I ∗ μ = ε（这正是定理 5.4）
即 μ = I⁻¹（在卷积意义下的逆）

定理 5.6：两个积性函数的狄利克雷卷积仍是积性函数。

证明：设 f, g 为积性函数，gcd(m, n) = 1。则 mn 的每个因数 d 可唯一分解为 d = d₁d₂，其中 d₁ | m, d₂ | n，且 gcd(d₁, d₂) = 1。因此

(f ∗ g)(mn) = ∑{d|mn} f(d)g(mn/d) = ∑{d₁|m} ∑{d₂|n} f(d₁d₂)g(mn/(d₁d₂)) = ∑{d₁|m} ∑{d₂|n} f(d₁)f(d₂)g(m/d₁)g(n/d₂) （积性） = (∑{d₁|m} f(d₁)g(m/d₁)) · (∑_{d₂|n} f(d₂)g(n/d₂)) = (f ∗ g)(m) · (f ∗ g)(n)

□

这个定理将积性函数的讨论置于一个统一框架之下，为解析数论中研究 L-函数等更深内容做好了准备。

第 5 章练习题

计算 φ(1000), τ(1000), σ(1000)。
证明：对于 n > 2，τ(n) 为奇数当且仅当 n 是完全平方数。
利用莫比乌斯反演，从 σ(n) = ∑{d|n} d 反推出 d = ∑{k|n} μ(k)σ(n/k)（作为验证公式）。
计算 μ(1) 到 μ(30) 的所有值。
证明：∑_{d|n} μ(d)τ(n/d) = 1。

第 6 章二次剩余

6.1 二次剩余与勒让德符号

问题引入

假设 p 是奇素数。对于给定的整数 a（不被 p 整除），我们问：是否存在整数 x 使得

x² ≡ a (mod p)？

如果存在，称 a 是模 p 的二次剩余；如果不存在，称 a 是模 p 的二次非剩余。

例 6.1：模 7 的二次剩余有哪些？

计算 0² 到 6² mod 7： 0² ≡ 0, 1² ≡ 1, 2² ≡ 4, 3² ≡ 2, 4² ≡ 2, 5² ≡ 4, 6² ≡ 1 (mod 7)。

所以模 7 的非零二次剩余是 1, 2, 4（各有 2 个平方根）；二次非剩余是 3, 5, 6。

重要事实：模奇素数 p 的非零剩余类中，恰好有一半是二次剩余（共 (p-1)/2 个），另一半是二次非剩余。

证明：映射 x ↦ x² 将 {1, 2, ..., p-1} 映到自身。每个二次剩余恰有两个平方根（x 和 p-x），故二次剩余恰好有 (p-1)/2 个。□

勒让德符号

为了系统地研究二次剩余，勒让德引入了以下符号：

定义：设 p 为奇素数，a 为整数。勒让德符号 (a/p)（更标准地写作 (a|p)，但本书用 (a/p) 以便书写）定义为：

       ⎧ 0    若 p | a
(a/p) = ⎨ 1    若 a 是模 p 的二次剩余
       ⎩ -1   若 a 是模 p 的二次非剩余

基本性质：

乘性：(ab/p) = (a/p) · (b/p)。即二次剩余的乘积仍是二次剩余；二次非剩余乘二次非剩余得二次剩余。
周期性：若 a ≡ b (mod p)，则 (a/p) = (b/p)。
(a²/p) = 1（若 p ∤ a）。

例 6.2：勒让德符号 (2/7) = ? 上面计算过，模 7 的平方中 3² ≡ 2 (mod 7)，所以 2 是模 7 的二次剩余，(2/7) = 1。

6.2 欧拉判别法

定理 6.1（欧拉判别法）：设 p 为奇素数，p ∤ a，则

a^{(p-1)/2} ≡ (a/p) (mod p)

证明：由费马小定理，a^{p-1} ≡ 1 (mod p)，所以 a^{(p-1)/2} ≡ ±1 (mod p)（因为 p 是素数时二次方程至多有两个解，而 ±1 满足平方为 1）。

关键步骤：若 a 是二次剩余，设 a ≡ x² (mod p)，则 a^{(p-1)/2} ≡ (x²)^{(p-1)/2} = x^{p-1} ≡ 1 (mod p) （费马小定理）

若 a 不是二次剩余，可以证明（此处从略）a^{(p-1)/2} ≡ -1 (mod p)。□

直接推论：

定理 6.2：(-1/p) = (-1)^{(p-1)/2}。即

若 p ≡ 1 (mod 4)，则 -1 是模 p 的二次剩余（例如 p = 5: 2² ≡ -1 (mod 5)）；
若 p ≡ 3 (mod 4)，则 -1 是模 p 的二次非剩余。

证明：由欧拉判别法，(-1/p) ≡ (-1)^{(p-1)/2} (mod p)。由于两边只能是 ±1 且 p > 2，同余就是相等。□

例 6.3：判断 3 是否为模 11 的二次剩余。计算 3^{(11-1)/2} = 3⁵ = 243 ≡ 1 (mod 11)（因为 243 = 11 × 22 + 1）。所以 (3/11) = 1。验证：5² = 25 ≡ 3 (mod 11)。□

6.3 二次互反律

二次互反律被高斯称为"黄金定理"，是数论中最深刻的定理之一。它提供了一种计算勒让德符号的高效方法。

定理 6.3（二次互反律）：设 p, q 为不同的奇素数，则

(p/q) · (q/p) = (-1)^{(p-1)(q-1)/4}

以及补充律：

(2/p) = (-1)^{(p²-1)/8}

即 (2/p) = 1 当 p ≡ ±1 (mod 8)； (2/p) = -1 当 p ≡ ±3 (mod 8)。

证明思路（高斯引理法）

二次互反律的证明可借助高斯引理：设 p 为奇素数，p ∤ a。考虑序列 a, 2a, ..., a(p-1)/2。用带余除法将它们表示为模 p 的最小非负剩余。设其中有 n 个剩余大于 p/2，则 (a/p) = (-1)ⁿ。

借助高斯引理，可以通过计数满足特定条件的格点来证明二次互反律。完整的数格点证明虽有一定篇幅，但核心思想非常直观。

应用：计算勒让德符号

二次互反律将"大模数"的问题转化为"小模数"的问题，反复使用直到可以直接判断。

例 6.4：计算 (33/83)。

首先分解分子：33 = 3 × 11，(33/83) = (3/83) × (11/83)。

计算 (3/83)：3 和 83 都是奇素数，使用互反律。 (3/83) · (83/3) = (-1)^{(3-1)(83-1)/4} = (-1)^{2×82/4} = (-1)^{41} = -1。 (83/3) = (83 mod 3 / 3) = (2/3) = -1（因为 3 ≡ 3 (mod 8)）。所以 (3/83) × (-1) = -1 ⇒ (3/83) = 1。

计算 (11/83)： (11/83) · (83/11) = (-1)^{(11-1)(83-1)/4} = (-1)^{10×82/4} = (-1)^{205} = -1。 (83/11) = (83 mod 11 / 11) = (6/11) = (2/11) × (3/11)。

(2/11)：11 ≡ 3 (mod 8)，所以 (2/11) = -1。 (3/11) · (11/3) = (-1)^{2×10/4} = (-1)^5 = -1。 (11/3) = (2/3) = -1。所以 (3/11) × (-1) = -1 ⇒ (3/11) = 1。

因此 (6/11) = (-1) × 1 = -1，(83/11) = -1。

回到 (11/83)： -1 × (11/83) = -1 ⇒ (11/83) = 1。

最终：(33/83) = (3/83) × (11/83) = 1 × 1 = 1。所以 33 是模 83 的二次剩余。□

这个例子展示了二次互反律的强大：我们从未计算过任何大数的幂，仅通过反复翻转符号和取模就将问题化归为小素数的判断。

6.4 雅可比符号与计算技巧

雅可比符号的定义

将勒让德符号推广到奇合数模数，得到雅可比符号。设 n > 1 为奇数，其素数分解为 n = p₁p₂...pₖ（素数可以重复）。定义

(a/n) = (a/p₁)(a/p₂)...(a/pₖ)

其中右边是勒让德符号的乘积。

重要区别：

勒让德符号 (a/p) = 1 ⇔ a 是模 p 的二次剩余。
雅可比符号 (a/n) = 1 ⇏ a 是模 n 的二次剩余（因为可能需要在所有素因子上都是二次剩余）。

例如，(2/15) = (2/3)(2/5) = (-1)(-1) = 1。但 2 不是模 15 的二次剩余（因为 x² ≡ 2 (mod 15) 无解）。雅可比符号为 1 只是"必要不充分条件"。

雅可比符号的互反律

美妙之处在于：互反律对雅可比符号同样成立（只要严格遵守奇数、互素的条件）。这意味着计算时不需要分解合数模，可以像勒让德符号一样递推。

例 6.5：计算 (1001/9907)。（这里 1001 = 7 × 11 × 13，但我们不需要分解）

(1001/9907)
= (-1)^{(1001-1)(9907-1)/4} × (9907/1001)    [互反律]
= (-1)^{1000×9906/4} × (9907/1001)
= (-1)^{2476500} × (9907/1001)
= 1 × (9907/1001)
= (9907 mod 1001 / 1001) = (898/1001)

(898/1001) = (2/1001) × (449/1001)
(2/1001)：1001 ≡ 1 (mod 8)，(2/1001) = 1。
(449/1001) = (-1)^{(449-1)(1001-1)/4} × (1001/449)
            = (-1)^{448×1000/4} × (1001/449)
            = (-1)^{112000} × (103/449)    [1001 mod 449 = 103]
            = (103/449)
= (-1)^{(103-1)(449-1)/4} × (449/103)
= (-1)^{102×448/4} × (449/103)
= (-1)^{11424} × (37/103)    [449 mod 103 = 37]
= (37/103)
= (-1)^{36×102/4} × (103/37)
= (-1)^{918} × (29/37)    [103 mod 37 = 29]
= (29/37)
= (-1)^{28×36/4} × (37/29)
= (-1)^{252} × (8/29)
= (8/29) = (2/29)³ = 2³ mod? (2/29) = -1 (29 ≡ -3 mod 8)，所以 (8/29) = (-1)³ = -1

因此 (1001/9907) = -1。我们从未分解 9907。□

雅可比符号的计算是密码学中常用到的技术，因为它避免了大数分解。

第 6 章练习题

列出模 13 的所有二次剩余和二次非剩余。
用欧拉判别法计算 (3/17)。
用二次互反律计算 (31/641) 和 (71/73)。
计算雅可比符号 (105/1009)。
证明：若 p ≡ 1 (mod 12)，则 (3/p) = 1。

第 7 章原根与指数

7.1 阶与原根

阶的定义

设 m 为正整数，a 是与 m 互素的整数。由欧拉定理，a^{φ(m)} ≡ 1 (mod m)。但有时 a 的较小的幂也可以 ≡ 1。

定义：使 aᵈ ≡ 1 (mod m) 成立的最小正整数 d 称为 a 模 m 的阶（order），记作 ordₘ(a)。

例如，模 7：

ord₇(1) = 1
ord₇(2)：2¹=2, 2²=4, 2³=8≡1，所以 ord₇(2) = 3
ord₇(3)：3¹=3, 3²=9≡2, 3³=6, 3⁴=18≡4, 3⁵=12≡5, 3⁶=15≡1，所以 ord₇(3) = 6
ord₇(6)：6¹=6, 6²=36≡1，所以 ord₇(6) = 2

定理 7.1（阶的性质）：

ordₘ(a) | φ(m)。
aᵏ ≡ 1 (mod m) 当且仅当 ordₘ(a) | k。
aⁱ ≡ aʲ (mod m) 当且仅当 i ≡ j (mod ordₘ(a))。

证明：(1) 令 d = ordₘ(a)。将 φ(m) 除以 d：φ(m) = dq + r (0 ≤ r < d)。则 1 ≡ a^{φ(m)} = a^{dq+r} = (aᵈ)^q · aʳ ≡ aʳ (mod m)。由 d 是最小正指数，r 必须为 0，故 d | φ(m)。(2)(3) 类似可得。□

原根的定义

如果 mod m 下某个元素 a 的阶恰好等于 φ(m)，则称 a 为模 m 的原根（primitive root）。

例 7.1：模 7 的原根。 φ(7) = 6。上面计算过 ord₇(3) = 6，所以 3 是模 7 的一个原根。检查 5：5²=25≡4, 5³=20≡6, 5⁶≡1，所以 5 也是模 7 的原根。

实际上模 7 的原根有 φ(φ(7)) = φ(6) = 2 个，即 3 和 5。

原根的意义在于：如果 g 是模 m 的原根，则 {g⁰, g¹, g², ..., g^{φ(m)-1}} 恰好构成模 m 的简化剩余系。这意味着乘法群 (Z/mZ)× 是循环群，原根就是它的生成元。

7.2 原根的存在条件

原根不一定总存在。例如模 8：φ(8) = 4，但可以验证所有与 8 互素的数 1, 3, 5, 7 的阶都是 1 或 2，没有原根。

定理 7.2（原根存在定理）：模 m 存在原根当且仅当

m = 2, 4, pᵏ 或 2pᵏ

其中 p 是奇素数，k ≥ 1。

完整证明的要点：

对奇素数 p，证明存在原根（利用多项式 xᵈ - 1 在模 p 下根的个数的限制）。
对于 pᵏ（k ≥ 2），从模 p 的原根出发，构造模 pᵏ 的原根。
对于 2pᵏ，利用模 2 的 trivial 性质进行拼接。
证明其他情况不可能有原根。

我们在此仅展示奇素数的情况。

引理 7.1：设 p 为奇素数，d | (p-1)。则模 p 下恰有 φ(d) 个阶为 d 的元素。

证明概要：关键利用以下事实：在域 Z/pZ 中，多项式 xᵈ - 1 最多有 d 个根。每个阶为 d 的元素都是 xᵈ - 1 的根，但需要排除阶小于 d 的根。由容斥原理和归纳法可证个数恰为 φ(d)。□

取 d = p-1，即知存在 φ(p-1) 个阶为 p-1 的元素——这就是模 p 的原根。

例 7.2：求模 41 的一个原根。 φ(41) = 40 = 2³ × 5。为找到原根，逐一测试较小的数，检查其阶。一个数 g 是原根当且仅当 g⁴⁰ ≡ 1 (mod 41) 且 g⁴⁰/² ≢ 1, g⁴⁰/⁵ ≢ 1 (mod 41)。

测试 6：6²⁰ mod 41 = ?（计算过程从略，可验证 6²⁰ ≡ 40 ≡ -1 (mod 41)，故 6²⁰ ≢ 1）。6⁸ mod 41 = ?（也不等于 1）。因此 6 是模 41 的一个原根。□

7.3 指数系统与离散对数

指数（指标）

设 g 是模 m（m 是原根存在的模数）的一个原根。由于 {g⁰, g¹, ..., g^{φ(m)-1}} 是简化剩余系，对于任意与 m 互素的 a，存在唯一的指数 i（0 ≤ i < φ(m)）使得

a ≡ gⁱ (mod m)

这个 i 称为 a 以 g 为底的指数或离散对数，记作 ind_g(a) 或 log_g a。

指数系统将乘法转化为加法：

ind_g(ab) ≡ ind_g(a) + ind_g(b) (mod φ(m))

这类似于普通对数的性质：log(xy) = log x + log y。因此，指数表（类似对数表）可以极大地简化模乘法和模幂运算。

例 7.3：模 13，取原根 g = 2。（φ(13) = 12）

a:    1  2  3  4  5  6  7  8  9  10  11  12
ind:  0  1  4  2  9  5  11 3  8  10   7   6

利用指数表解 x⁵ ≡ 6 (mod 13)：

取指数（以 2 为底）：5 ind₂(x) ≡ ind₂(6) (mod 12) 5 ind₂(x) ≡ 5 (mod 12)

由于 gcd(5, 12) = 1，有唯一解：ind₂(x) ≡ 5 × 5⁻¹ ≡ 5 × 5 ≡ 25 ≡ 1 (mod 12)。（5⁻¹ mod 12 = 5，因为 5 × 5 = 25 ≡ 1 mod 12）

所以 ind₂(x) = 1，查表知 x = 2。

验证：2⁵ = 32 ≡ 6 (mod 13)。□

7.4 离散对数问题的困难性

单向函数

正向计算 gˣ mod p 是容易的（使用快速幂算法，复杂度 O(log x)）。但反过来，已知 gˣ mod p，求 x——即离散对数问题（Discrete Logarithm Problem, DLP）——在模数为大素数时被认为是计算上不可行的。

这就是一个陷门单向函数：正向容易，逆向极难。它与大数分解问题一起，构成了现代公钥密码学的两大数学支柱。

Diffie-Hellman 密钥交换

1976 年，Whitfield Diffie 和 Martin Hellman 基于离散对数问题提出了革命性的密钥交换协议：

Alice 和 Bob 公开约定一个大素数 p 和一个原根 g。
Alice 秘密选取随机数 a，计算 A ≡ gᵃ (mod p)，向 Bob 公开发送 A。
Bob 秘密选取随机数 b，计算 B ≡ gᵇ (mod p)，向 Alice 公开发送 B。
Alice 计算 K ≡ Bᵃ (mod p)，Bob 计算 K ≡ Aᵇ (mod p)。

由于 Bᵃ ≡ (gᵇ)ᵃ ≡ gᵃᵇ ≡ (gᵃ)ᵇ ≡ Aᵇ (mod p)，两人得到相同的共享密钥 K。

窃听者 Eve 知道 p, g, A, B，但要从 A = gᵃ 恢复 a（或从 B = gᵇ 恢复 b），需要求解离散对数问题。对于足够大的 p，这在计算上不可行。

这个简单的协议引发了密码学的一场革命——人们第一次可以在不事先共享密钥的情况下安全通信。第 10 章将详细展开这些应用。

第 7 章练习题

求模 17 下所有元素（与 17 互素）的阶。
找出模 23 的一个原根（可以用逐步验证法）。
建立模 11 以原根 2 为底的指数表。
用指数表解同余方程 3x⁷ ≡ 5 (mod 11)。
在 Diffie-Hellman 协议中，取 p = 23, g = 5, a = 6, b = 15。计算共享密钥 K。

第 8 章不定方程

8.1 二元一次不定方程

一般形式

二元一次不定方程（又称线性丢番图方程）的形式为：

ax + by = c

其中 a, b, c 是已知整数，我们要求整数解 (x, y)。

定理 8.1：方程 ax + by = c 有整数解当且仅当 gcd(a, b) | c。

证明：(⇒) 若有解，则 c = ax + by 是 a 和 b 的线性组合。由于 a 和 b 的任何线性组合都能被 d = gcd(a, b) 整除，所以 d | c。

(⇐) 若 d | c，设 c = dc'。由贝祖等式，存在整数 u, v 使得 au + bv = d。两边乘 c'：a(uc') + b(vc') = dc' = c，所以 (uc', vc') 是一组解。□

通解公式

定理 8.2：设 d = gcd(a, b)，且 (x₀, y₀) 是 ax + by = c 的一个特解，则通解为：

x = x₀ + (b/d) · t
y = y₀ - (a/d) · t

其中 t 为任意整数。

证明：设 (x, y) 是任意解，则 ax + by = ax₀ + by₀ = c，所以 a(x - x₀) = b(y₀ - y)。除以 d：(a/d)(x - x₀) = (b/d)(y₀ - y)。由于 gcd(a/d, b/d) = 1，由整除性质，(a/d) | (y₀ - y)。令 y₀ - y = (a/d)t，代入可得 x - x₀ = (b/d)t。□

例 8.1：解 15x + 21y = 39。

解：d = gcd(15, 21) = 3，3 | 39，有解。化简：5x + 7y = 13。

求特解：注意到 5 × (-1) + 7 × 2 = -5 + 14 = 9 ≠ 13。继续尝试。

用扩展欧几里得求 5u + 7v = 1： 7 = 5 × 1 + 2 5 = 2 × 2 + 1 2 = 1 × 2 + 0

回代：1 = 5 - 2 × 2 = 5 - 2 × (7 - 5) = 3 × 5 - 2 × 7。

所以 (3, -2) 是 5x + 7y = 1 的特解。乘 13 得 5x + 7y = 13 的特解：x₀ = 39, y₀ = -26。

通解（还原到原始方程）： x = 39 + 7t, y = -26 - 5t（t ∈ Z）。

验证 t = 0：15 × 39 + 21 × (-26) = 585 - 546 = 39 ✓。□

8.2 商高方程（毕达哥拉斯三元组）

问题

求方程 x² + y² = z² 的所有正整数解 (x, y, z)。这些解称为毕达哥拉斯三元组或商高数。

注意：如果 (x, y, z) 是解，那么 (kx, ky, kz) 对任意正整数 k 也是解。因此我们只需关注本原解，即满足 gcd(x, y, z) = 1 的解。

定理 8.3：所有本原毕达哥拉斯三元组可以表示为

x = m² - n²， y = 2mn， z = m² + n²

其中 m > n > 0，gcd(m, n) = 1，且 m 和 n 一奇一偶。（x 和 y 可以互换位置。）

证明：

首先，如果 (x, y, z) 是本原解，则 x 和 y 不能同为偶数（否则 z 也是偶数，与互素矛盾）；也不能同为奇数（否则 x² ≡ y² ≡ 1 (mod 4)，z² ≡ x² + y² ≡ 2 (mod 4)，但平方数模 4 只能是 0 或 1，矛盾）。因此 x 和 y 必定一奇一偶。不妨设 y 是偶数。

将方程改写为：y² = z² - x² = (z - x)(z + x)。

令 d = gcd(z - x, z + x)。则 d | (z + x) + (z - x) = 2z，d | (z + x) - (z - x) = 2x。由于 gcd(x, z) = 1，所以 d | 2。又因为 x 和 z 不同奇偶（x 奇，z 奇），所以 z ± x 都是偶数，d ≥ 2，故 d = 2。

令 z + x = 2m²，z - x = 2n²（由于 z ± x 都是偶数且互素因子在两个因子中的分布必须都是平方数）。则 z = m² + n²，x = m² - n²，y = 2mn。

由推导过程自动得到 m > n > 0，gcd(m, n) = 1，且 m, n 一奇一偶（否则 x, z 会同为偶数）。□

例 8.2：生成前几组本原三元组。

m	n	x = m²-n²	y = 2mn	z = m²+n²	三元组
2	1	3	4	5	(3, 4, 5)
3	2	5	12	13	(5, 12, 13)
4	1	15	8	17	(8, 15, 17)
4	3	7	24	25	(7, 24, 25)
5	2	21	20	29	(20, 21, 29)

历史上，巴比伦人早在公元前 1800 年左右就已知道毕达哥拉斯三元组——普林普顿 322 号泥板记录了 15 组三元组，比毕达哥拉斯早了一千多年。□

8.3 费马大定理简介

从毕达哥拉斯到费马

毕达哥拉斯方程 x² + y² = z² 有无穷多组正整数解。一个自然的推广是：xⁿ + yⁿ = zⁿ 当 n > 2 时是否有解？

费马大定理（Fermat's Last Theorem, FLT）：当整数 n > 2 时，方程

xⁿ + yⁿ = zⁿ

没有正整数解 (x, y, z)。

费马的边注

1637 年左右，费马在丢番图《算术》拉丁文译本的页边写道：

将一个立方数分解为两个立方数之和，或一个四次幂分解为两个四次幂之和，或者一般地，将高于二次的任何次幂分解为两个同次幂之和，都是不可能的。关于此，我确信我发现了一种绝妙的证明，可惜这页边太窄，写不下。

这个"绝妙的证明"困扰了数学家 350 多年。费马本人证明了 n = 4 的情况（使用无穷递降法），欧拉证明了 n = 3，但对一般的 n，进展极其缓慢。

怀尔斯的证明

1994 年，英国数学家安德鲁·怀尔斯（Andrew Wiles）在普林斯顿大学宣布完成了费马大定理的证明。他的证明不是费马可能想到的"初等方法"，而是建立在 20 世纪数学最深刻的成就之上——椭圆曲线、模形式和伽罗瓦表示理论。怀尔斯实际上证明了一个更强的猜想（谷山-志村猜想的一部分），费马大定理是它的推论。

这个成就不仅是数论的胜利，也是人类智慧的巅峰之一。怀尔斯为此花了 7 年时间秘密工作，几乎不与外界交流，其故事由西蒙·辛格写入《费马大定理》（又名《费马最后定理》）一书。

8.4 佩尔方程 x² – Dy² = 1 初探

问题

佩尔方程（Pell's equation）的形式为：

x² - Dy² = 1

其中 D 是正整数且不是完全平方数。要求正整数解 (x, y)。

这个方程在历史上被错误地以英国数学家 John Pell 命名，但实际上是欧拉弄错了——这个方程早在印度数学家婆罗摩笈多（7世纪）和婆什迦罗二世（12世纪）那里已得到深入研究。

最小解与无穷多解

佩尔方程要么无正整数解（当 D 为完全平方数时，因为 x² - n²y² = 1 只有 x = 1, y = 0 的平凡解），要么有无穷多解。

所有解都可以从最小正整数解（也称为基本解）(x₁, y₁) 生成：

xₖ + yₖ√D = (x₁ + y₁√D)ᵏ

展开即可得到所有解。

如何找最小解

最小解可以通过 √D 的连分数展开找到（详见第 9 章），也可以通过暴力搜索。

例 8.3：解 x² - 2y² = 1。

最小正整数解：尝试 y = 1：x² = 3，无整数解。y = 2：x² = 8 + 1 = 9，x = 3。所以 (3, 2) 是基本解。由 (3 + 2√2)ᵏ 生成所有解：

k = 1: (3, 2)
k = 2: (3+2√2)² = 17 + 12√2 ⇒ (17, 12)，验证：17² - 2·12² = 289 - 288 = 1
k = 3: (17+12√2)(3+2√2) = 99 + 70√2 ⇒ (99, 70)

例 8.4：解 x² - 61y² = 1。直接搜索需要耐心，因为最小解 x₁ = 1766319049, y₁ = 226153980。这个例子展示了佩尔方程最小解可能非常巨大——用连分数方法可以系统性地找到它。□

8.5 线性丢番图逼近引子

有理逼近的基本问题

设 α 是一个无理数。我们能否用分母较小的有理数 p/q 很好地逼近 α？

狄利克雷逼近定理：对于任意无理数 α 和任意整数 N > 1，存在整数 p, q 使得 1 ≤ q ≤ N 且

|α - p/q| < 1/(qN) ≤ 1/q²

特别地，存在无穷多对互素的整数 (p, q) 使得

|α - p/q| < 1/q²

这个定理说明：无理数可以被有理数"出奇地好"地逼近。而连分数（第 9 章）提供了最佳的逼近方法——连分数的渐近分数 pₖ/qₖ 满足 |α - pₖ/qₖ| < 1/(qₖ²)。

从丢番图逼近到连分数

丢番图逼近的核心问题是：找到最优的有理逼近。连分数正是这一问题的标准答案。我们即将在第 9 章系统展开。

第 8 章练习题

求 56x + 72y = 40 的全部整数解。
找出所有满足 x² + y² = z² 且 x = 20 的正整数解。
用生成公式列出所有满足 z ≤ 50 的本原毕达哥拉斯三元组。
求佩尔方程 x² - 3y² = 1 的前三组正整数解。
证明佩尔方程 x² - Dy² = -1 可能无解（举出一个反例）。

第 9 章连分数

9.1 有限连分数与有理数

定义

一个有限简单连分数的形式为：

                      1
a₀ + ───────────────────────────
                        1
     a₁ + ─────────────────────
                          1
          a₂ + ─────────────────
                           1
               a₃ + ──────────
                    ... + 1/aₙ

其中 a₀ 是整数，aᵢ (i ≥ 1) 是正整数。为简化书写，我们将其记为

[a₀; a₁, a₂, ..., aₙ]

例 9.1：[2; 3, 4] = 2 + 1/(3 + 1/4) = 2 + 1/(13/4) = 2 + 4/13 = 30/13。

有理数与有限连分数的一一对应

定理 9.1：每个有限简单连分数表示一个有理数；反之，每个有理数可以唯一地表示为有限简单连分数（如果约定最后一项 aₙ > 1）。

证明：前者是显然的（有限步有理运算）。后者即欧几里得算法的"连分数版"。将有理数 a/b 写成：

a/b = q₁ + r₁/b = q₁ + 1/(b/r₁)

然后对 b/r₁ 重复这个过程。这正是辗转相除法中每一步的商！因此，有限连分数的展开过程就是辗转相除法。

唯一性：如果约定 aₙ > 1（去掉最后一项可能为 1 的歧义性，因为 [a₀; a₁, ..., aₙ₋₁, 1] = [a₀; a₁, ..., aₙ₋₁ + 1]），则表示是唯一的。□

例 9.2：将 43/19 展开为连分数。

43 = 19 × 2 + 5     → a₀ = 2
19 = 5 × 3 + 4      → a₁ = 3
5 = 4 × 1 + 1       → a₂ = 1
4 = 1 × 4 + 0       → a₃ = 4

所以 43/19 = [2; 3, 1, 4]。

验证：[2; 3, 1, 4] = 2 + 1/(3 + 1/(1 + 1/4)) = 2 + 1/(3 + 1/(5/4)) = 2 + 1/(3 + 4/5) = 2 + 1/(19/5) = 2 + 5/19 = 43/19。□

9.2 无限连分数与无理数

定义与收敛

如果将连分数无限延伸下去，我们得到无限简单连分数：

[a₀; a₁, a₂, a₃, ...]

其值定义为渐近分数序列的极限。第 k 个渐近分数为 Cₖ = [a₀; a₁, ..., aₖ]。

定理 9.2：每个无限简单连分数收敛于一个无理数；每个无理数可以唯一地表示为一个无限简单连分数。

证明概要：

收敛性：渐近分数 Cₖ 满足 |Cₖ - Cₖ₋₁| = 1/(qₖqₖ₋₁)，其中 qₖ 是分母序列。由于 qₖ 严格增长，序列是柯西序列，必收敛。

表示无理数：对无理数 α，定义 a₀ = ⌊α⌋，α₁ = 1/(α - a₀)，a₁ = ⌊α₁⌋，如此递推。这个过程永远不终止（因为无理数的分数部分永不为 0），故产生无限连分数。□

渐近分数的递推公式

设渐近分数 Cₖ = pₖ/qₖ，则有递推关系：

p₋₂ = 0,  p₋₁ = 1,  pₖ = aₖpₖ₋₁ + pₖ₋₂
q₋₂ = 1,  q₋₁ = 0,  qₖ = aₖqₖ₋₁ + qₖ₋₂

例 9.3：计算 π 的连分数和渐近分数。

π = 3.1415926535... a₀ = ⌊π⌋ = 3 α₁ = 1/(π - 3) ≈ 7.0625...，a₁ = 7 α₂ ≈ 15.9966...，a₂ = 15 α₃ ≈ 1.0034...，a₃ = 1 ...

π = [3; 7, 15, 1, 292, 1, 1, 1, 2, ...]

渐近分数（使用递推公式）：

k	aₖ	pₖ	qₖ	Cₖ	近似值
0	3	3	1	3	3.000000
1	7	22	7	22/7	3.142857
2	15	333	106	333/106	3.141509
3	1	355	113	355/113	3.141593

注意 22/7 和 355/113 都是著名的 π 的有理逼近。355/113 精确到小数点后 6 位，这个结果在公元 5 世纪就由中国数学家祖冲之发现。□

9.3 循环连分数与二次无理数

拉格朗日定理

定义：一个连分数称为循环的，如果它的部分商序列从某处开始无限重复。例如：

[2; 1, 2, 1, 2, 1, ...] 是周期为 2 的循环连分数，记作 [2; \overline{1, 2}]。

定理 9.3（拉格朗日，1770）：一个无理数的连分数是循环的当且仅当它是二次无理数（即有理系数二次方程的根）。

这意味着循环连分数与形如 (a + √b)/c 的数之间存在精确的对应。

√D 的连分数展开

对于 √D（D 是非完全平方正整数），其连分数有特殊结构：

√D 的连分数形式为 [a₀; \overline{a₁, a₂, ..., a₂, a₁, 2a₀}]

即周期是回文的（去掉最后一项后），且最后一项是 2a₀。

算法：展开 √D 的连分数：

初始化：m₀ = 0, d₀ = 1, a₀ = ⌊√D⌋
递推：mₖ₊₁ = dₖaₖ - mₖ
      dₖ₊₁ = (D - mₖ₊₁²) / dₖ
      aₖ₊₁ = ⌊(a₀ + mₖ₊₁) / dₖ₊₁⌋
停止：当 (mₖ, dₖ, aₖ) 重复时

例 9.4：展开 √7 的连分数。

a₀ = ⌊√7⌋ = 2。

k	mₖ	dₖ	aₖ	计算
0	0	1	2	a₀ = 2
1	2×1-0=2	(7-4)/1=3	⌊(2+2)/3⌋=1	a₁=1
2	3×1-2=1	(7-1)/3=2	⌊(2+1)/2⌋=1	a₂=1
3	2×1-1=1	(7-1)/2=3	⌊(2+1)/3⌋=1	a₃=1
4	3×1-1=2	(7-4)/3=1	⌊(2+2)/1⌋=4	a₄=4

当 (m₄, d₄) = (2, 1) = (m₁, d₁)，循环开始。所以

√7 = [2; \overline{1, 1, 1, 4}]

验证周期结构：a₁=1, a₂=1, a₃=1, a₄=2a₀=4，符合回文规律。□

9.4 连分数的应用

求解佩尔方程

连分数提供了解佩尔方程 x² - Dy² = 1 的标准方法：

定理 9.4：设 √D 的连分数周期长度为 L。当 L 为偶数时，佩尔方程 x² - Dy² = 1 的基本解由第 (L-1) 个渐近分数 p_{L-1}/q_{L-1} 给出；当 L 为奇数时，由第 (2L-1) 个渐近分数给出。

例 9.5：解 x² - 7y² = 1。

√7 = [2; \overline{1, 1, 1, 4}]，周期 L = 4（偶数）。

渐近分数： p₀/q₀ = 2/1 p₁/q₁ = [2; 1] = 3/1 p₂/q₂ = [2; 1, 1] = 5/2 p₃/q₃ = [2; 1, 1, 1] = 8/3 ← 周期 L-1 = 3 的渐近分数

验证：8² - 7 × 3² = 64 - 63 = 1。所以 (8, 3) 是基本解。□

例 9.6：解 x² - 13y² = 1。

√13 = [3; \overline{1, 1, 1, 1, 6}]，周期 L = 5（奇数）。需要用第 (2L-1) = 9 个渐近分数。结果是 (649, 180)，即 649² - 13 × 180² = 1。

日历编排与闰年

一年约等于 365.2422 天 = 365 + 0.2422 ≈ 365 + 1/(4 + 1/(7 + 1/...))

0.2422 的连分数展开：0.2422 = [0; 4, 7, 1, ...]

渐近分数：

1/4 = 0.25（每 4 年 1 闰，儒略历）
7/29 = 0.2414（每 29 年 7 闰）
8/33 = 0.2424（每 33 年 8 闰）

格里高利历（现行公历）采用"每 400 年 97 闰" = 0.2425，非常接近精确值。而 31/128（波斯历）更是达到了 0.2421875。

光学设计

在光学镜头设计中，需要用简单的齿轮比逼近无理数比值。连分数给出的"最佳有理逼近"正是这一问题的标准解。

第 9 章练习题

将 67/29 展开为有限连分数，并验证其值。
计算 e = 2.718281... 的前 5 个部分商和渐近分数。
展开 √14 的连分数，指出其周期。
利用连分数求佩尔方程 x² - 14y² = 1 的基本解。
求 22/7 和 355/113 逼近 π 的相对误差。

第 10 章数论在密码学中的应用

10.1 RSA 公钥密码

从对称到公钥

传统加密（对称加密）要求通信双方事先共享密钥。在互联网时代，这几乎不可行——你不可能先和全世界几十亿人各自面交一把密钥。公钥密码学（非对称加密）解决了这个难题：加密用公钥（可公开），解密用私钥（仅接收方持有）。

RSA 是第一个实用的公钥密码体制，由 Rivest、Shamir 和 Adleman 于 1977 年提出，其安全性建立在大整数因数分解的困难性之上。

RSA 算法

密钥生成：

随机选取两个大素数 p 和 q（通常各 1024 位以上）。
计算 n = pq 和 φ(n) = (p-1)(q-1)。
选取 e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1（常用的 e 有 65537 = 2¹⁶ + 1）。
计算 d 使得 ed ≡ 1 (mod φ(n))，即 d = e⁻¹ mod φ(n)。
公钥：(n, e)。私钥：(n, d)。（实际应用中还需要安全地销毁 p, q 和 φ(n)。）

加密：发送者用接收者的公钥加密消息 m（0 ≤ m < n）：

c ≡ mᵉ (mod n)

解密：接收者用私钥解密：

m ≡ cᵈ (mod n)

正确性证明

需要证明 (mᵉ)ᵈ ≡ m (mod n)，即 mᵉᵈ ≡ m (mod n)。

由于 ed ≡ 1 (mod φ(n))，存在整数 k 使得 ed = 1 + kφ(n) = 1 + k(p-1)(q-1)。则

mᵉᵈ = m^{1 + k(p-1)(q-1)} = m · (m^{p-1})^{k(q-1)}

若 p ∤ m，由费马小定理 m^{p-1} ≡ 1 (mod p)，故 mᵉᵈ ≡ m (mod p)。若 p | m，则 mᵉᵈ ≡ 0 ≡ m (mod p) 同样成立。同理 mᵉᵈ ≡ m (mod q)。由中国剩余定理，mᵉᵈ ≡ m (mod pq = n)。□

小实例

取 p = 3, q = 11（仅作演示，实际绝不能用这么小的素数！）

n = 33，φ(n) = 20。取 e = 3（注意 gcd(3, 20) = 1）。 d = 3⁻¹ mod 20 = 7（因为 3 × 7 = 21 ≡ 1 mod 20）。

公钥：(33, 3)。私钥：(33, 7)。

加密字母 A（用 ASCII 码 65 不现实，我们用简化编码 A=1, B=2, ..., Z=26）：

加密 B (m = 2)：c ≡ 2³ = 8 (mod 33)。解密：m ≡ 8⁷ (mod 33)。

8¹ = 8，8² = 64 ≡ 31 (mod 33)，8⁴ ≡ 31² = 961 ≡ 4 (mod 33)， 8⁷ = 8⁴ × 8² × 8¹ ≡ 4 × 31 × 8 = 992 ≡ 2 (mod 33)。

成功恢复 m = 2 = B。□

10.2 离散对数与 ElGamal 体制

离散对数问题回顾

给定大素数 p，原根 g，以及 h ≡ gˣ (mod p)，求 x 是计算上不可行的。这就是 ElGamal 密码体制的安全基础。

ElGamal 加密

密钥生成：

选取大素数 p 和原根 g。
随机选取私钥 x (1 < x < p-1)。
计算 h ≡ gˣ (mod p)。
公钥：(p, g, h)。私钥：x。

加密（发送者操作）：

获取接收者公钥 (p, g, h)。
随机选取临时密钥 k (1 < k < p-1)。
计算 c₁ ≡ gᵏ (mod p)。
计算 c₂ ≡ m · hᵏ (mod p)。
密文为 (c₁, c₂)。

解密：

计算共享秘密 s ≡ c₁ˣ (mod p)（利用私钥 x）。
计算 m ≡ c₂ · s⁻¹ (mod p)。

正确性：c₂ · s⁻¹ ≡ m · hᵏ · (gᵏˣ)⁻¹ ≡ m · gˣᵏ · g⁻ˣᵏ ≡ m (mod p)。

小实例

取 p = 23, g = 5。Bob 的私钥 x = 6，公钥 h = 5⁶ mod 23 = 15625 mod 23 = 8。

Alice 想发送 m = 10。随机选 k = 3。

c₁ = 5³ mod 23 = 125 mod 23 = 10。 hᵏ = 8³ mod 23 = 512 mod 23 = 6。 c₂ = 10 × 6 mod 23 = 60 mod 23 = 14。

密文：(10, 14)。

Bob 解密： s = c₁ˣ = 10⁶ mod 23。10² = 100 ≡ 8, 10⁴ ≡ 8² = 64 ≡ 18, 10⁶ ≡ 18 × 8 = 144 ≡ 6 (mod 23)。 s⁻¹ = 6⁻¹ mod 23 = 4（因为 6 × 4 = 24 ≡ 1 mod 23）。 m = c₂ × s⁻¹ = 14 × 4 = 56 ≡ 10 (mod 23)。□

ElGamal 数字签名

ElGamal 同样可以用于数字签名（证明某个消息确实来自声称的发送者）：

签名者随机选取 k（与 p-1 互素），计算 r ≡ gᵏ (mod p)。
计算 s ≡ k⁻¹(H(m) - xr) (mod p-1)，其中 H 是哈希函数。
签名为 (r, s)。
验证：检查 g^{H(m)} ≡ hʳ · rˢ (mod p) 是否成立。

10.3 哈希函数与数字签名

哈希函数的角色

公钥加密直接处理消息效率很低（相比对称加密慢约 1000 倍）。在实际系统中，公钥密码主要用来：

安全地交换对称密钥；
生成和验证数字签名。

而哈希函数（散列函数）在数字签名中扮演着至关重要的角色。它将任意长度的消息映射为固定长度的摘要（例如 SHA-256 输出 256 位）：

H: {0, 1}* → {0, 1}ⁿ

理想的密码哈希函数需满足：

抗原像性：给定 H(m)，无法找到 m。
抗第二原像性：给定 m，无法找到 m' ≠ m 使得 H(m') = H(m)。
抗碰撞性：无法找到任意两个不同的 m₁ ≠ m₂ 使得 H(m₁) = H(m₂)。

数字签名实际上是对消息的哈希值签名而非消息本身，这既提升了效率也增强了安全性。

数论提供的单向陷门函数

RSA 和 ElGamal 的安全核心各来自一个数论难题：

密码体制	核心难题	正向（容易）	逆向（困难）
RSA	大数分解	两个素数相乘得 n	从 n 恢复 p 和 q
ElGamal	离散对数	计算 gˣ mod p	从 gˣ 求 x

这些都是陷门单向函数的例子：正向计算容易，逆向在没有"陷门"（私钥）的情况下极其困难。但拥有陷门后逆向也变得容易。

10.4 量子计算威胁与后量子数论

Shor 算法

1994 年，Peter Shor 提出的量子算法可以在多项式时间内分解大整数和求解离散对数。这意味着如果大规模量子计算机被建造出来，RSA 和 ElGamal 将不再安全。

Shor 算法的核心思想是将大数分解问题转化为求周期的问题，而量子傅里叶变换可以高效地求周期。

时间线：目前的量子计算机距离破解 RSA-2048 所需的规模还差得很远（需要数千个逻辑量子比特，而目前最多只有几百个含噪声的物理量子比特）。但"现在收集，以后解密"（Store Now, Decrypt Later）的威胁已经促使密码学界积极寻找后量子替代方案。

后量子密码学与格

格密码（Lattice-based cryptography）是后量子密码学中最有前途的方向之一，其安全性基于格上的计算难题，如：

最短向量问题（SVP）：在格中找到最短的非零向量。
学习带误差问题（LWE）：从带噪声的线性方程中恢复秘密。

这些问题的难度有很强的理论保证（即使在量子计算机上也没有已知的高效算法），而且格密码可以构造全同态加密等 RSA 无法实现的高级功能。

有趣的是，格密码本质上是数论的延续——它研究的是 Zⁿ 中的离散加法子群（格），这可以看作整数和模运算的自然推广。

美国国家标准与技术研究院（NIST）已于 2024 年公布了首批后量子密码标准，其中包括基于格的 Kyber（密钥封装）和 Dilithium（数字签名）算法。

第 10 章练习题

取 p = 5, q = 11, e = 3，完成 RSA 密钥生成、加密 m = 8 和解密的完整过程。
在 ElGamal 加密中，取 p = 19, g = 2, x = 5，加密 m = 7（取 k = 11），并验证解密。
说明为什么在 RSA 中 e 和 d 都必须是秘密的（除了公钥的 e 以外）。
如果 Eve 截获了 Diffie-Hellman 协议中的 p, g, gᵃ, gᵇ，她如何才能在多项式时间内计算出共享密钥？（这题引导思考：什么假设使这不可能？）
思考题：如果能够高效分解大整数，除了直接解密 RSA 密文外，还有哪些密码系统会受到影响？

附录 A：常用数论符号表

符号	含义
a\| b	a 整除 b
a ∤ b	a 不能整除 b
gcd(a, b)	a 和 b 的最大公因数
lcm(a, b)	a 和 b 的最小公倍数
a ≡ b (mod m)	a 与 b 模 m 同余
φ(n)	欧拉函数：不超过 n 且与 n 互素的正整数个数
τ(n)	约数个数函数
σ(n)	约数和函数
μ(n)	莫比乌斯函数
(a/p)	勒让德符号
ordₘ(a)	a 模 m 的阶
ind_g(a)	a 以原根 g 为底的指数（离散对数）
[a₀; a₁, ..., aₙ]	有限连分数
π(x)	不超过 x 的素数个数
□	证明结束

附录 B：500 以内的素数表

2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499

（共 95 个素数）

附录 C：部分习题提示与参考答案

第 1 章

提示：三个连续整数中必有一个是 3 的倍数，且至少有两个是连续的→至少有一个偶数（2 的倍数）。
gcd(2023, 1395) = 31。
31 = 2023 × (-31) + 1395 × 45。
利用贝祖等式：由 gcd(a, b) = 1，存在 x, y 使得 ax + by = 1。两边乘 c 即可推出 a | c。
9450 = 2 × 3³ × 5² × 7，2925 = 3² × 5² × 13。gcd = 3² × 5² = 225，lcm = 2 × 3³ × 5² × 7 × 13 = 122850。

第 2 章

5¹⁰⁰ mod 7 = 2。
模 15 的简化剩余系：{1, 2, 4, 7, 8, 11, 13, 14}。φ(15) = 8。
分别证明 2 | a⁷-a, 3 | a⁷-a, 7 | a⁷-a，然后由互素性合并。

第 3 章

x ≡ 6, 13, 20 (mod 21)。（d = gcd(6, 21) = 3，3 | 15，3 个解。）
13⁻¹ mod 60 = 37（13 × 37 = 481 = 60 × 8 + 1）。
x ≡ 52 (mod 105)。
x ≡ 365 (mod 504)。
无解（1 ≢ 3 (mod gcd(4, 6) = 2)）。

第 4 章

若 n 是合数，设 n = ab（1 < a ≤ b < n）。则 a ≤ √n，验证 a 的素因子即可。
2027：√2027 ≈ 45。用 45 以内的素数试除（2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43），无整除。2027 是素数。

第 5 章

φ(1000) = 400, τ(1000) = 16, σ(1000) = 2340。
τ(n) 为奇数 ⇔ 每个指数均为偶数 ⇔ n 是完全平方数。
μ(1..10)：1, -1, -1, 0, -1, 1, -1, 0, 0, 1。

第 6 章

模 13 的二次剩余：1, 3, 4, 9, 10, 12。二次非剩余：2, 5, 6, 7, 8, 11。
(3/17) = 1。3⁸ mod 17 = 1（费马验证：3⁸ = 6561 = 17 × 386 - 1... 等等。重算：3²=9, 3⁴=81≡13, 3⁸≡13²=169≡16≡-1。所以 (3/17) = -1。但... 让我对一下：欧拉判别法说 (3/17) ≡ 3⁸ (mod 17)。3⁸ = 6561 ÷ 17 = 385 余 16 ≡ -1。所以 (3/17) = -1。之前错了，这里更正。）

第 7 章

模 17 下：ord₁₇(1) = 1, ord₁₇(2) = 8, ord₁₇(3) = 16, ord₁₇(4) = 4, ord₁₇(5) = 16, ord₁₇(6) = 16, ord₁₇(7) = 16, ord₁₇(8) = 8, ord₁₇(9) = 8, ord₁₇(10) = 16, ord₁₇(11) = 16, ord₁₇(12) = 16, ord₁₇(13) = 4, ord₁₇(14) = 16, ord₁₇(15) = 8, ord₁₇(16) = 2。
模 23 的原根之一是 5（共有 φ(22) = 10 个原根）。
K = 2。

第 8 章

d = 8，8 | 40。化简 7x + 9y = 5。特解 (2, -1)。通解 x = 2 + 9t, y = -1 - 7t。
满足 z ≤ 50 的本原三元组：(3,4,5), (5,12,13), (8,15,17), (7,24,25), (20,21,29), (12,35,37), (9,40,41), (28,45,53)... 等一下 53 > 50。所以是：(3,4,5), (5,12,13), (8,15,17), (7,24,25), (20,21,29), (12,35,37), (9,40,41)。
x² - 3y² = -1 无解（模 3 分析即可）。

第 9 章

67/29 = [2; 3, 4, 2]。
√14 = [3; \overline{1, 2, 1, 6}]。
x² - 14y² = 1 的基本解：(15, 4)。
22/7 的相对误差 ≈ 0.04%，355/113 的相对误差 ≈ 0.0000085%。

第 10 章

p = 5, q = 11: n = 55, φ = 40, e = 3, d = 27（3 × 27 = 81 ≡ 1 mod 40）。加密 m = 8: c = 8³ mod 55 = 512 mod 55 = 17。解密: 17²⁷ mod 55 = 8。