同余的应用

我们刚刚建立了同余的语言框架：定义、等价关系、运算规则、剩余类与线性同余方程。 有了语言，下一步是看它能做什么。今天的内容将证明，同余理论远不只是数学课本里的符号游戏——它连接着两千年前的中国算术谜题、十七世纪的素数直觉、以及今天保护你网络支付安全的现代密码系统。

三个深刻的定理将成为主角：费马小定理、威尔逊定理和中国剩余定理，每一个都以同余为语言，揭示整数世界的一个不同侧面。

费马小定理

皮埃尔·德·费马（Pierre de Fermat，1601—1665）是法国波尔多的一名律师，数学只是他业余时间的爱好。这位业余数学家在 1640 年写给友人的信中提到了一个关于素数与幂次的神奇规律，一笔带过，没有给出证明——他当时的习惯正是如此，在书页空白处或信件里留下断言，让后人去证明。 这条断言后来被高斯系统地证明并收入《算术研究》，成为初等数论中使用频率最高的单条定理。

两种表述之间的关系很直接：后者 $a^p \equiv a \pmod p$ 当 $p \nmid a$ 时，两边除以 $a$（注意此时 $\gcd (a,p)$，可以合法约分），就得到前者 ；当 时，，两边都 ，等式平凡成立。

用具体数字感受一下。取 $p = 5$，$a = 3$：$3^4 = 81 = 16 \times 5 + 1$，故 ，符合定理。取 ，：，故 ，符合定理。定理的证明依赖上一篇提到的完全剩余系置换性质：当 时，集合 模 后仍然是 的一个排列，故两边之积模 相等，化简后正好得到 。

费马小定理在应用上有三个主要方向，理解它们比死记定理本身更重要。

计算大幂次的余数是最直接的应用。以 $3^{100} \bmod 7$ 为例：由费马小定理 $3^6 \equiv 1 \pmod 7$；将 除以 得 ；故 。这里的关键操作是"把指数模 "——原来一个 48 位的数的计算，被化简成了一个两位数的乘方。

求乘法逆元是费马小定理更精妙的应用。在模 $p$ 的世界里，若 $p \nmid b$，可以把"除以 $b$"理解为"乘以 $b$ 的逆元 $b^{-1}$"，其中 $b^{-1}$ 满足 。由费马小定理 ，故 。例如， 在模 下的逆元是 ，故 ；验证：，正确。这个公式把"求逆元"变成了"求大幂次"，结合快速幂算法，是现代密码学实现中的标准手段。

素性检验是费马小定理的逆用：若对某个正整数 $n$，存在 $\gcd(a, n) = 1$ 的整数 $a$ 使得 $a^{n-1} \not\equiv 1 \pmod n$，则 一定不是素数（反定理）。这是的基础。它不是完美的——存在"卡迈克尔数"（Carmichael numbers）这类合数，对所有与之互质的 都满足 ——但配合米勒-拉宾（Miller-Rabin）等更强检验，实践中已足够可靠，广泛用于密码学中的大素数选取。

威尔逊定理

费马小定理用指数刻画素数，威尔逊定理用阶乘刻画素数——两者是完全不同的视角，却都精确抓住了素数的本质。约翰·威尔逊（John Wilson，1741—1793）观察到了这条规律，但未能证明；严格证明由拉格朗日（Lagrange）在 1770 年给出。

三个验证感受一下。$p = 5$：$4! = 24 = 4 \times 5 + 4$，故 $4! \equiv 4 \equiv -1 \pmod 5$，满足。：，故 ，满足。（合数）：，故 ，不等于 ，不满足——合数确实被排除在外。

为什么结论恰好是 $-1$？这个问题有一个漂亮的回答。考察集合 $\{1, 2, 3, \ldots, p-1\}$ 中的数，大多数都和某个不同于自己的数互为乘法逆元（即两数之积 $\equiv 1 \pmod p$），它们在 的乘积中两两配对，贡献的乘积等于 ，可以从中"消去"。例外的情形是"自己是自己逆元"的数，即满足 的数，解为 或 ，对应 和 两个数。于是 中，所有其余数两两配对消去，最终只剩下 ，定理成立。

威尔逊定理在实际解题中最常见的用法，是把"接近 $p$ 的阶乘"转化为已知量。直接应用：$6! \equiv -1 \equiv 6 \pmod 7$，一步得到。稍作变形：若要求 $5! \pmod 7$，由 以及 ，得 ；因 ，故 ；两边乘以 ，得 。这种"用 Wilson 结论 + 乘法逆元倒推"的技巧，是竞赛中处理阶乘余数的标准手法。

中国剩余定理

公元三到五世纪，中国数学家孙子在《孙子算经》中记录了这样一道问题："今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？"即求满足

$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 2 \pmod{7}$

的最小正整数。孙子给出了答案 $23$，以及一套口诀式的求解方法（"三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知"）。这套方法背后的数学，在七百年后由宋代数学家秦九韶系统化，再经欧洲数学家推广，最终以"中国剩余定理"之名载入数学史册。

构造解的方法有明确的算法。令 $M_i = M / m_i$，则 $\gcd(M_i, m_i) = 1$（因为 不含 的因子），故 在模 下有乘法逆元，记为 ，满足 。令

$x_0 = a_1 M_1 y_1 + a_2 M_2 y_2 + \cdots + a_k M_k y_k$

可以验证 $x_0 \equiv a_i \pmod{m_i}$ 对每个 $$ 成立：对于第 个方程， 的所有项 中， 含有 作为因子（因为 且 时……此处需注意 的定义让 对 成立），故这些项模 均为零，仅剩第 项 。最终解为 ，在模 意义下唯一。

以孙子的原题为例完整走一遍：$m_1 = 3, m_2 = 5, m_3 = 7$，，，。求逆元：，，故 ；，故 ；，故 。合并：；，故 ，最小正整数解为 。验证：（余 ），（余 ），（余 ），全部满足。

中国剩余定理的深层意义在于它揭示了同余结构的分解与重构：模 $M$ 意义下的一个整数，完全等价于它分别模各互质因子 $m_i$ 的余数组成的元组。这种等价关系在代数上形成了一个环同构，是代数数论、密码学、编码理论中反复出现的基本工具。

RSA 加密：同余守护你的网络安全

同余理论最壮观的现实应用，发生在你每次网购、发微信或者查阅银行余额的那一刻——RSA 公钥加密系统在后台默默运行。RSA 由 Rivest、Shamir 和 Adleman 三人于 1977 年发明，至今仍是互联网传输层安全（TLS）的核心组件之一。

RSA 的数学设置并不复杂。选定两个大素数 $p$ 和 $q$，令 $n = pq$（公开）和 $\varphi(n) = (p-1)(q-1)$（保密）。选一个与 互质的整数 作为，用扩展欧几里得算法找到 满足 ， 是。加密时，将明文 （转化为整数）映射为密文 ；解密时，对密文做 ，由欧拉定理可以证明 ，原文被精确还原。

RSA 安全性的根基是大数分解问题的困难性：$n = pq$ 对外公开，但从 $n$ 还原出 $p$ 和 $q$ 在 $p, q$ 各有数百位时，以现有最优算法需要超过宇宙寿命的计算时间。而没有 $p$ 和 $$，就无法计算 ，也就无从得知私钥 ，密文无从破解。整套系统的关键正是：正向（加密）只需知道公钥 和 ，逆向（由密文恢复明文）却依赖只有私钥持有者才知道的 ——这种"公开加密、私钥解密"的不对称性，来自大数分解问题两个方向的计算复杂度差异，而大数分解问题的难度，深扎于素数理论与同余代数的土壤之中。

费马小定理在密码学中的直接使用还体现在指数化简：计算 $a^b \pmod p$ 时，当 $p$ 是素数且 $p \nmid a$，可以把指数 $b$ 替换为 $$ 再计算，因为 保证了周期性。这是密钥交换协议（如 Diffie-Hellman）、数字签名以及零知识证明等密码学构件中反复用到的核心操作。

日历里的同余

同余不只藏在数论课本和密码系统里，它每天就印在你的日历上，决定着"今天是星期几"。

一个星期有 $7$ 天，"星期几"的计算就是模 $7$ 的同余运算。今天是星期三，$100$ 天后是星期几？$100 = 14 \times 7 + 2$，模 $7$ 余 $2$，故是星期三再过 天，即星期五。若某年 月 日是星期二，则 月 日是星期几（非闰年）？从 月 日到 月 日共 天，，故是星期二再过 天，即星期五。

公历的闰年规则同样是同余语言的直接表述：年份 $y$ 是闰年，当且仅当 $y \equiv 0 \pmod 4$ 且 $y \not\equiv 0 \pmod{100}$，或者 。因此 （被 整除且不被 整除）是闰年，（被 整除但不被 整除）不是闰年，（被 整除）是闰年。历史上泽勒（Zeller）公式把年、月、日转化为星期数的全过程，本质上就是把日历中的各种周期（ 天一周、 年一闰、 年一例外、 年一回正）叠加在一起的多项模运算。

例题精讲

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

题目：计算 $2^{100} \bmod 13$。

例题二：威尔逊定理推导阶乘余数

题目：计算 $11! \bmod 13$。

例题三：中国剩余定理的完整流程

题目：求满足 $x \equiv 1 \pmod 2$，$x \equiv 2 \pmod 3$，$x \equiv 3 \pmod 5$ 的最小正整数 。

例题四：日历计算

题目：已知 $2024$ 年 $1$ 月 $1$ 日是星期一，问 $2024$ 年 $7$ 月 $4$ 日是星期几？

例题五：模意义下的"除法"

题目：在模 $17$ 意义下，求 $5/9$ 的值，即 $5 \times 9^{-1} \pmod{17}$。

练习

练习一：利用费马小定理，计算 $5^{999} \bmod 11$，以及 $7^{200} \bmod 13$。

练习二：用中国剩余定理解方程组 $x \equiv 3 \pmod 4$，$x \equiv 2 \pmod 7$，$x \equiv 4 \pmod 9$，求最小正整数解。

练习三：利用威尔逊定理，证明对素数 $p \geq 3$，$\left(\dfrac{p-1}{2}\right)!^2 \equiv (-1)^{(p+1)/2} \pmod p$（提示：将 写成两个"半阶乘"的乘积，并利用 ）。

要点收束

同余理论的应用，在三条定理的组合中达到顶点。费马小定理揭示了素数与幂次的深层联系：$a^{p-1} \equiv 1 \pmod p$，它不仅能把天文级别的大幂次化为小数运算（周期化简），还能用 $b^{p-2}$ 的形式计算乘法逆元，是密码学中快速模幂和离散对数问题的理论基础。

威尔逊定理则从完全不同的角度刻画素数：$(p-1)! \equiv -1 \pmod p$ 是充要条件，其背后的"逆元配对消去、只剩 $1$ 与 $p-1$"的证明思路是模运算结构的一个精美展示。

中国剩余定理把多个独立的同余条件联立，证明其解在大模意义下唯一存在并给出构造算法，揭示了整数在"按互质因子分解"时的完美对应关系。

三者汇流，便有了 RSA 加密系统：大素数保证了费马定理的威力，大数分解的困难性保证了系统的安全性，而模运算将一切串联起来，在你每次登录网银、发送加密消息时在后台瞬间完成。

$x \equiv a_i \pmod{m_i}, \quad i = 1, 2, \ldots, k$

在模 $M$ 意义下有唯一解。

$7^{200} \bmod 13$：$13$ 是素数，$7^{12} \equiv 1 \pmod{13}$。$200 = 12 \times 16 + 8$，故 $7^{200} \equiv 7^8 \pmod{13}$。$7^2 = 49 \equiv 10 \equiv -3$，$7^4 \equiv 9$，$7^8 \equiv 81 \equiv 81 - 6 \times 13 = 81 - 78 = 3 \pmod{13}$，故 $7^{200} \bmod 13 = 3$。

求逆元：$63 \equiv 3 \pmod 4$，求 $3y \equiv 1 \pmod 4$，$y = 3$（$3 \times 3 = 9 \equiv 1$）；$36 \equiv 1 \pmod 7$，$y_2 = 1$；$28 \equiv 1 \pmod 9$，$y_3 = 1$。

$x_0 = 3 \times 63 \times 3 + 2 \times 36 \times 1 + 4 \times 28 \times 1 = 567 + 72 + 112 = 751$。

$751 = 2 \times 252 + 247$，再 $247 < 252$，故 $x \equiv 247 \pmod{252}$，最小正整数解 $x = 247$。

验证：$247 = 61 \times 4 + 3$（余 $3$），$247 = 35 \times 7 + 2$（余 $2$），$247 = 27 \times 9 + 4$（余 $4$），全部正确。

于是 $(p-1)! = \left(\frac{p-1}{2}\right)! \times (p-1)(p-2)\cdots\frac{p+1}{2} \equiv \left(\frac{p-1}{2}\right)! \times (-1)^{(p-1)/2} \left(\frac{p-1}{2}\right)! = (-1)^{(p-1)/2} \left[\left(\frac{p-1}{2}\right)!\right]^2 \pmod p$。

由威尔逊定理 $(p-1)! \equiv -1 \pmod p$，故 $(-1)^{(p-1)/2} \left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv -1 \pmod p$，两边乘以 $(-1)^{(p-1)/2}$（注意 $(-1)^{(p-1)/2} \times (-1)^{(p-1)/2} = (-1)^{p-1} = 1$，因 $p-1$ 为偶数），得 $\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv (-1)^{(p-1)/2} \times (-1) = (-1)^{(p+1)/2} \pmod p$。$\square$

这个结论与二次剩余理论深度相关：$-1$ 是模 $p$ 的二次剩余的充要条件是 $p \equiv 1 \pmod 4$，恰好对应 $(p+1)/2$ 为偶数的情形。