数论综合

前面的内容学习下来，我们已经构建了一套完整的初等数论语言——从整除的基本逻辑，到质数的分布特性，从最大公因数与最小公倍数的算法，到同余与裴蜀定理，再到费马小定理、威尔逊定理与中国剩余定理。 这些工具不是孤立的技巧，而是彼此咬合、相互支撑的一套理论体系。这部分我们将综合将做三件事：回顾前面的核心脉络，引入两个将所有工具汇聚使用的新主题（丢番图方程与 RSA 加密），以及把目光投向数论最前沿那些至今未解的谜题。

核心脉络

这门课程的整个旅程从整除这个概念出发，它定义了整数之间最基本的关系：$m \mid a$ 当且仅当 $a = mk$ 对某整数 $k$ 成立，即 $a$ 除以 $m$ 没有余数。整除的传递性（$a \mid b$ 且 $b \mid c$ 则 $a \mid c$）、与运算的相容性（若 $m \mid a$ 且 $m \mid b$ 则 $m \mid (xa + yb)$），是后续几乎所有推导的起点。

• 质数是整数世界的"原子"。算术基本定理保证了每个大于 $1$ 的整数都有唯一的质因数分解，这是整除理论的结构性基石。在此基础上，因数个数公式 $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$（其中 ），把质因数分解直接转化为一个计数答案。欧几里得证明了质数有无穷多个，但它们如何分布至今是数论最深刻的未解问题之一。

丢番图方程

公元三世纪的亚历山大城，数学家狄奥芬托斯（Diophantus）写下了一部叫《算术》的著作，其中充满了只要求整数或有理数解的方程题。后世把这类明确要求在整数（或有理数）范围内求解的方程，统称为丢番图方程（Diophantine equations）——无论是最简单的线性方程，还是费马大定理涉及的 $n$ 次方程。

线性丢番图方程

最基础的丢番图方程是线性的：$ax + by = c$，$a, b, c$ 为已知整数，求整数解 $(x, y)$。由裴蜀定理，此方程有整数解当且仅当 $\gcd(a, b) \mid c$。

当条件满足时，求解的标准流程是：用辗转相除法逆推找出裴蜀系数，得到一个特解 $(x_0, y_0)$（满足 $ax_0 + by_0 = c$），再写出通解：任意整数解可以表示为 ，，其中 ， 遍历全体整数。可以看出，整数解构成一个等差间隔的无穷点列，沿某条格线均匀分布——若加上正整数约束，则只有有限多组解。

以 $6x + 10y = 14$ 为例：$\gcd(6,10) = 2$，$2 \mid 14$，条件满足。辗转相除给出 $6\times 2+10\times (-1)$，两边乘以 得到特解 ；通解为 ，，。取 分别得到 ，都是合法的整数解。

更高次的丢番图方程

随着方程次数升高，丢番图方程呈现出截然不同的面貌。勾股方程 $x^2 + y^2 = z^2$ 有无穷多组正整数解，最小的是 $(3,4,5)$，一般公式为 ，，（ 整数，， 为奇数）——古巴比伦人在四千年前就掌握了这些三元组。

还有一类貌似简单却深藏玄机的方程：佩尔方程 $x^2 - Dy^2 = 1$，其中 $D$ 是非完全平方正整数。这类方程总有正整数解，但最小解可能非常大——$x^2 - 61y^2 = 1$ 的最小正整数解是 ，——找到最小解需要连分数理论的工具，是古典数论中一颗复杂而美丽的宝石。

RSA 加密：数论守护你的网络安全

RSA 公钥加密系统由 Rivest、Shamir 和 Adleman 三人于 1977 年发明，是今天互联网传输层安全（TLS/HTTPS）的核心组件之一。它之所以安全，不依赖任何物理屏障，而是依赖一个纯粹的数论事实：将两个大素数 $p$ 和 $q$ 相乘得 $n = pq$ 极易，但从 $n$ 反向分解出 $p$ 和 $q$ 在两者各有数百位时，以现有最优算法需要超过宇宙寿命的计算时间。正向快速、逆向困难的"单向性"，正是 RSA 的安全基石。

密钥生成的数学设置如下（以小数字演示，实用中 $p, q$ 各有数百位）。选定两个素数 $p = 11$，$q = 13$，令 $n = pq = 143$。计算欧拉函数 $$，它表示 到 中与 互质的整数个数。选取公钥指数 （只需 ），用扩展欧几里得算法找私钥指数 满足 ；计算可得 ，因为 ，验证正确。于是公钥为 ，可以向全世界公开；私钥 由持有者秘密保存。

加密与解密各只需一次模幂运算。对明文 $m = 9$，发送方用公钥计算密文 $c \equiv m^e = 9^7 \pmod{143}$；利用快速幂逐步化简：，，，故密文为 。接收方持有私钥 ，计算 ，快速幂计算后得到 ，与原文一致。解密之所以成功，根源是 （当 时）：由 ，有 ，故 ，解密完美还原。

RSA 之美在于它的"非对称性"：任何人都可以用公钥 $(n, e)$ 加密消息，但只有知道私钥 $d$ 的持有者才能解密——而从公开的 $n$ 推出 $d$ 等价于分解 $n$，等价于已解决的大数分解难题。整个体系的安全性，是纯粹的数论困难性。

竞赛视角：数论题的思维路径

数论题在数学竞赛（AMC、奥林匹克、联赛）中出现频率极高。与计算题不同，数论竞赛题的核心在于整数结构的敏感性——看到一个表达式，立刻联想到它对哪些模有什么余数，它的因数结构如何约束解的数量，它的奇偶性或被小质数整除的条件如何削减可能性。

遇到要求"证明整除性"的题，标准路径是对关键变量取适当的模值进行分类讨论，或用质因数分解直接分析整除条件。遇到大幂次的余数问题，第一反应是找幂次的周期（利用费马小定理或直接计算，找到 $a^k \equiv 1 \pmod m$ 的最小正整数 $k$），再将指数对 $k$ 取余，把大指数缩小为小指数。遇到联立余数条件，中国剩余定理提供了系统的构造算法；若各余数关系特别规律（如各余数恰好等于模数减去同一常数），往往可以找到更短的巧解路径。遇到不定方程，先检验裴蜀条件是否满足，再用辗转相除法找特解，最后用通解公式叠加正整数范围约束来枚举有限解。

因数个数公式 $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$ 也是竞赛中的常用工具。一个计数类题型：满足 的正整数 有哪些形式？因数个数为 ，对应 、、（ 为不同素数）三种结构，对各结构再加额外限制即可枚举。

数论的未解谜题

数论有一个迷人的特殊性：它最著名的未解问题，其陈述往往只需要小学数学，但其解决却需要最深刻的现代数学。

哥德巴赫猜想（1742 年）断言：每个大于 $2$ 的偶数都可以表示为两个素数之和，如 $4 = 2+2$，$100 = 3+97$，$1000 = 3+997$。计算机已验证到 内所有偶数均满足，但普遍成立的证明至今缺席。中国数学家陈景润于 1966 年证明了"每个充分大的偶数都是一个素数与至多两个素数之积的和"（即""），被称为陈氏定理，是迄今最接近哥德巴赫的严格结果。

孪生素数猜想断言：差为 $2$ 的素数对（如 $(3,5), (11,13), (17,19), (1000000007, 1000000009)$）有无穷多个。2013 年，张益唐突破性地证明了存在无穷多对素数，其差不超过 $7000$ 万；此后 Maynard 和 Tao 等人通过筛法改进，将这个上界压低到数百，但最终想到达"恰好等于 $2$"这个目标，数学上仍是一道鸿沟。

黎曼假设（1859 年）是克雷数学研究所千禧年七大难题之一，解决可获百万美元奖金。它断言黎曼 $\zeta$ 函数的所有非平凡零点的实部恰为 $1/2$，而这直接决定了素数计数函数 $\pi(x)$（不超过 $x$ 的素数个数）的误差阶。黎曼假设成立即意味着素数分布在最优尺度上的均匀性，现已有数百万个零点被数值验证位于这条临界线上，但普遍成立的证明至今无人完成。

现代数论已不是象牙塔中的纯粹游戏。纠错码（保障通信可靠性）依赖有限域与多项式整除；伪随机数生成器（密码学与模拟计算的基础）大量使用线性同余；区块链的哈希函数底层是数论单向函数；抗量子计算攻击的格密码体系以整数格中的困难问题为根基。没有数论，就没有现代互联网的安全基础设施。

例题精讲

例题一：裴蜀定理与最大公因数线性表示

题目：已知 $\gcd(252, 180) = 36$，请找出整数 $x, y$，使得 $252x + 180y = 36$。

例题二：线性丢番图方程的正整数解

题目：求方程 $3x + 5y = 41$ 的所有正整数解。

例题三：费马小定理计算大幂次

题目：求 $3^{100} \bmod 7$。

例题四：整除性证明

题目：证明对任意正整数 $n$，有 $6 \mid n(n+1)(n+2)$。

例题五：质数判定

题目：判断 $221$ 是否为质数；若不是，写出质因数分解。

例题六：中国剩余定理与巧解

题目：某正整数 $N$ 满足：除以 $3$ 余 $1$，除以 $5$ 余 $3$，除以 $7$ 余 $5$。求最小正整数解。

练习

练习一：用线性丢番图方程的方法，找出满足 $15x + 21y = 9$ 的所有整数解，并确定哪些解满足 $x > 0, y < 0$。

练习二：计算 $2^{333} \bmod 11$ 与 $5^{100} \bmod 13$。

练习三：设 $p$ 是大于 $3$ 的素数，证明 $24 \mid (p^2 - 1)$。

要点收束

整数的世界比表面上看起来深邃得多。从"整除"的朴素概念出发，整个初等数论展开了一张复杂而统一的大网：算术基本定理给出了整数的结构，辗转相除法给出了 GCD 的高效算法，裴蜀定理揭示了 GCD 的线性表示能力，同余将计算的维度从无界的整数集压缩到有限的余数圈，费马小定理、威尔逊定理和中国剩余定理则分别从指数、阶乘和联立条件三个角度深挖了整数的内在规律。 丢番图方程把所有这些工具汇聚到"求整数解"这一古老的问题形式里。而 RSA 加密则以一种令人惊叹的方式说明：数论不是与现实脱节的抽象游戏——它是你每一次点击"支付"按钮时在后台悄然运行的安全盾牌。 哥德巴赫、孪生素数、黎曼假设……那些用小学语言陈述、却需要大师级数学证明的谜题，则是一个永远开放的邀请：整数世界的全部秘密，还远未被揭完。

通解：$x = 9 + 7t$，$y = -6 - 5t$，$t \in \mathbb Z$（步长为 $21/3=7$ 和 $15/3=5$）。

要求 $x > 0$ 且 $y < 0$：$x = 9 + 7t > 0$ 给 $t > -9/7$，即 $t \geq -1$；$y = -6 - 5t < 0$ 给 $-5t < 6$，即 $t > -6/5$，故 $t \geq -1$。两个约束合并为 $t \geq -1$，对应无穷多解：$t = -1$ 时 $(2,-1)$；$t = 0$ 时 $(9,-6)$；$t = 1$ 时 $(16,-11)$；……

$5^{100} \bmod 13$：$13$ 为素数，$5^{12} \equiv 1 \pmod{13}$。$100 = 12 \times 8 + 4$，故 $5^{100} \equiv 5^4 = 625 \pmod{13}$。$625 = 48 \times 13 + 1$，故 $5^{100} \equiv 1 \pmod{13}$。

被 $8$ 整除：$p > 3$ 为素数，故 $p$ 为奇数（$p \neq 2$），于是 $p-1$ 和 $p+1$ 都是偶数，且它们是两个连续偶数，其中之一必被 $4$ 整除，故 $(p-1)(p+1)$ 被 $2 \times 4 = 8$ 整除。

被 $3$ 整除：$p$ 为大于 $3$ 的素数，故 $3 \nmid p$，即 $p \equiv 1$ 或 $p \equiv 2 \pmod 3$。若 $p \equiv 1$，则 $3 \mid (p-1)$；若 $p \equiv 2$，则 $p + 1 \equiv 0 \pmod 3$，故 $3 \mid (p+1)$。两种情形下均有 $3 \mid (p-1)(p+1)$。

因 $\gcd(8,3) = 1$，由互质整除传递性得 $24 \mid (p^2-1)$。$\square$