同余的应用

一个数除以另一个数，最后剩几？这个“剩几”，很多时候比原来的数本身还重要。

比如今天星期一，100 天后星期几？你当然不会真的数 100 个格子。因为星期每 7 天转一圈，$100$ 除以 $7$ 余 $2$，所以只要从星期一往后挪 2 天，就是星期三。这就是同余。

再比如一个很大的密码系统，电脑并不会傻乎乎地把天文数字完整算出来，它也会不断问：“这个数模某个数之后，余数是多少？”同余就是这种“只看余数”的语言。

这节我们要看的几件事，表面上一个比一个抽象：费马小定理、威尔逊定理、中国剩余定理、RSA 加密、日历计算。但你可以把它们看成同一个故事的不同章节：我们学会了余数的规则，然后开始用它解决真正的问题。

费马小定理

先讲个有点“数学圈段子”味道的故事。

费马是法国人，本职是律师，数学属于业余爱好。但这位业余玩家很猛，经常在信里或者书页空白处写一句“我发现了一个很妙的结论”，然后不写证明，留给后人慢慢补作业。

费马小定理就是这样一条结论。它说的是：如果 $p$ 是素数，那么很多数在模 $p$ 的世界里，都会出现一个非常稳定的循环。

这句话第一次看可能有点硬。我们拿数字试一下。

取 $p=5$，$a=3$。费马小定理说 $3^{4}$ 除以 $5$ 应该余 $1$。算一下：$3^4=81$，而 ，确实余 。

再取 $p=7$，$a=4$。它说 $4^6$ 除以 $7$ 也应该余 $1$。$4^6=4096$，，还是余 。

它背后的直觉其实不难：在模 $p$ 的世界里，如果 $a$ 和 $p$ 互质，那么 $a,2a,3a,\ldots,(p-1)a$ 这些数取余以后，只是把 $1,2$ 重新洗了一遍顺序。既然只是重新排队，所有数乘起来的余数不变。把两边能约掉的部分约掉，就会得到 。

那它有什么用？最常见的有三种。

第一，算大幂次的余数。

比如要算 $3^{100} \bmod 7$。直接算当然也行，但很笨。因为 $7$ 是素数，根据费马小定理：

$3^6 \equiv 1 \pmod 7$

于是指数每多 $6$，余数就绕回一圈。$100=6 \times 16+4$，所以

$3^{100}=(3^6)^{16}\cdot 3^4 \equiv 1^{16}\cdot 81 \equiv 4 \pmod 7$

原本是一个很大的幂，最后只用算 $3^4$。这就是“把指数压小”的威力。

第二，求模意义下的“除法”。

普通算术里，$5/3$ 就是除以 $3$。但在模运算里，我们更喜欢说：除以 $3$，等于乘以 $3$ 的逆元。所谓逆元，就是找一个数 $x$，让

$3x \equiv 1 \pmod 7$

试一下就知道 $x=5$，因为 $3 \times 5=15\equiv 1 \pmod 7$。所以在模 $7$ 的世界里，$3^{-1}$。

费马小定理给了一个通用办法：如果 $p$ 是素数，且 $p\nmid b$，那么

$b^{-1}\equiv b^{p-2}\pmod p$

因为 $b\cdot b^{p-2}=b^{p-1}\equiv 1 \pmod p$。这在算法和密码学里很常见，尤其配合快速幂，电脑算起来非常快。

第三，判断一个数“像不像素数”。

如果 $n$ 真的是素数，那么对很多 $a$，应该有 $a^{n-1}\equiv 1 \pmod n$。反过来，如果你找到某个 $a$，让这个式子不成立，那 肯定不是素数。

当然，这个方法不是百分之百完美。有些合数很会伪装，比如卡迈克尔数，会骗过一些费马测试。但这个思路很重要，后来的米勒-拉宾素性测试就是在它的基础上变得更可靠。今天很多大素数的筛选，都离不开这种“先用同余试探一下”的思想。

威尔逊定理

如果说费马小定理是在看“幂次”，那威尔逊定理就是在看“阶乘”。

它的味道很不一样。费马小定理像是在说：素数让幂次产生周期。威尔逊定理则像是在说：素数会让 $1$ 到 $p-1$ 这些数在乘起来之后，刚好留下一个 $-1$。

我们先不急着证明，先看几个小例子。

$p=5$ 时，$4!=24$，除以 $5$ 余 $4$，而 $4\equiv -1\pmod 5$。

$p=7$ 时，$6!=720$，除以 $7$ 余 $6$，而 $6\equiv -1\pmod 7$。

如果换成合数，比如 $n=6$，$5!=120$，除以 $6$ 余 $0$，就不是 $-1$ 了。

为什么偏偏会剩 $-1$？这里有一个很漂亮的配对故事。

在模 $p$ 的世界里，$1,2,\ldots,p-1$ 每个数都有乘法逆元。大多数数的逆元都不是自己，于是它们可以两两配对，乘积都是 $1$。

比如模 $7$：

$2\cdot 4\equiv 1 \pmod 7,\quad 3\cdot 5\equiv 1 \pmod 7$

配来配去，最后只有两个数比较特殊：$1$ 和 $p-1$。因为 $1$ 的逆元是自己，$p-1\equiv -1$ 的逆元也是自己。

所以 $(p-1)!$ 里，大多数因子都两两乘成 $1$，最后只剩

$1\cdot (p-1)\equiv -1\pmod p$

这就是威尔逊定理最核心的画面。

它有什么用？最常见的是处理“接近 $p$ 的阶乘余数”。

比如算 $5!\bmod 7$。我们知道

$6!\equiv -1\equiv 6\pmod 7$

而 $6!=6\cdot 5!$，所以

$6\cdot 5!\equiv 6\pmod 7$

因为 $6\equiv -1$，它自己的逆元还是 $6$。两边乘以 $6$，得到

$5!\equiv 36\equiv 1\pmod 7$

这类题的套路就是：先用威尔逊定理抓住 $(p-1)!$，再往回倒推。

中国剩余定理

《孙子算经》里有一道老题，大意是：有一堆东西，不知道多少个。三个三个数，剩 $2$ 个；五个五个数，剩 $3$ 个；七个七个数，剩 $2$ 个。问这堆东西最少有多少个？

翻译成同余就是：

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

答案是 $23$。

你可以真的验一下：$23$ 除以 $3$ 余 $2$，除以 $5$ 余 $3$，除以 $7$ 余 $2$。这就像三个人分别给你一条线索，每条线索都不完整，但合在一起，居然能把答案锁住。

这句话可以翻译成人话：

只要这些模数彼此不打架（两两互质），那么每个模数给出的余数条件，最终会拼出一个唯一的答案。这里的“唯一”，不是说只有一个整数，而是说在 $0$ 到 $M-1$ 这个范围里只有一个；之后每隔 $M$，又会重复一次。

怎么拼？方法很机械。

令

$M_i=\frac{M}{m_i}$

然后找 $M_i$ 在模 $m_i$ 下的逆元 $y_i$，也就是

$M_i y_i\equiv 1\pmod {m_i}$

最后把答案合成：

$x_0=a_1M_1y_1+a_2M_2y_2+\cdots+a_kM_ky_k$

这个公式看起来有点突然，但直觉很好理解：第 $i$ 项是专门为第 $i$ 个条件服务的。因为 $M_i$ 除掉了 $m_i$，却保留了其他所有模数的因子，所以它在其他方程里都会自动变成 $0$；只在第 个方程里，通过乘上逆元 ，变成 。

还是拿孙子那道题走一遍。

这里 $m_1=3,m_2=5,m_3=7$，。

总模数：

$M=3\times 5\times 7=105$

三个分量：

$M_1=35,\quad M_2=21,\quad M_3=15$

求逆元：

$35\equiv 2\pmod 3,\quad 2\times 2\equiv 1\pmod 3$

所以 $y_1=2$。

$21\equiv 1\pmod 5$

所以 $y_2=1$。

$15\equiv 1\pmod 7$

所以 $y_3=1$。

合起来：

$x_0=2\times 35\times 2+3\times 21\times 1+2\times 15\times 1=233$

$233$ 除以 $105$ 余 $23$，所以

$x\equiv 23\pmod {105}$

最小正整数解就是 $23$。

中国剩余定理真正厉害的地方，不只是会解这类古代趣题。它告诉我们：一个模大数的问题，可以拆成几个模小数的问题；算完以后，再拼回去。这个“拆开算，再合起来”的思想，在计算机算法、编码理论、密码学里都非常常见。

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

如果前面还像是在做数学题，那么 RSA 就是在告诉你：这些余数游戏真的能保护钱和隐私。

你网购、登录网站、传输敏感信息时，背后经常会用到公钥密码的思想。RSA 是其中最经典的一种。它的核心并不是把算法藏起来，而是反过来：加密方法可以公开，但只有拥有私钥的人才能解开。

RSA 大概是这样玩的。

先选两个非常大的素数 $p$ 和 $q$，把它们乘起来：

$n=pq$

$n$ 可以公开。别人看到 $n$ 没关系。

然后计算

$\varphi(n)=(p-1)(q-1)$

这个值不能随便公开，因为知道它基本就离私钥很近了。

接着选一个和 $\varphi(n)$ 互质的数 $e$，作为公钥指数。再找一个数 $d$，让

$ed\equiv 1\pmod{\varphi(n)}$

$e$ 可以公开，$d$ 必须保密。

加密时，把明文 $M$ 变成密文：

$C\equiv M^e\pmod n$

解密时，再算：

$M'\equiv C^d\pmod n$

在背后的数论保证下，$M'$ 会回到原来的 $M$。

这个系统为什么安全？一句话：乘两个大素数很容易，但把它们的乘积再拆回去很难。

比如你知道 $n=pq$，但不知道 $p$ 和 $q$。如果 $p,q$ 足够大，想从 $n$ 反推出这两个素数，成本会高到不现实。没有 $p,q$，就很难得到 ；没有 ，就很难得到私钥 。

同余在这里扮演了很关键的角色：它让加密和解密都可以写成模幂运算。费马小定理和它的推广（欧拉定理）保证了这些运算能正确绕回来。中国剩余定理还常被用来加速 RSA 解密，把一个大模数上的计算拆成两个小模数上的计算，再合并结果。

所以你可以这样理解：RSA 不是靠“别人不知道规则”来安全，而是靠“别人知道规则也算不回来”来安全。

日历里的同余

同余最日常的例子，其实每天都在我们手机日历里。

星期就是模 $7$。今天星期三，$100$ 天后星期几？因为

$100=14\times 7+2$

所以只需要往后数 $2$ 天，是星期五。

如果某年 $1$ 月 $1$ 日是星期二，问非闰年的 $3$ 月 $1$ 日是星期几？从 $1$ 月 $1$ 日到 $3$ 月 $1$ 日，过了

$31+28=59$

天。$59=8\times 7+3$，所以从星期二往后推 $3$ 天，是星期五。

闰年规则也可以用同余讲清楚：

比如 $2024$ 能被 $4$ 整除，不能被 $100$ 整除，所以是闰年。

$2100$ 虽然能被 $4$ 整除，但也能被 $100$ 整除，不能被 $400$ 整除，所以不是闰年。

$2000$ 能被 $400$ 整除，所以是闰年。

你看，日历本质上就是很多周期叠在一起：一周 $7$ 天，普通年份 $365$ 天，闰年 $366$ 天，闰年规则又按 $4,100,400$ 年循环。所谓算星期几，就是在这些周期里不断取余。

例题精讲

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

题目：计算 $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$

提示：把 $(p-1)!$ 分成前半段和后半段，再把后半段改写成负数。

要点收束

如果用一句话来结尾这一部分：同余让我们不用关心一个数“到底有多大”，只关心它落在某个周期里的哪个位置。

费马小定理告诉我们，在素数模数下，幂次会出现稳定周期，所以大幂次可以变小，逆元也可以靠幂来求。

威尔逊定理告诉我们，素数还可以被阶乘刻画：$(p-1)!$ 在模 $p$ 下刚好等于 $-1$。它背后的直觉是逆元配对，最后只剩 $1$ 和 $p-1$。

中国剩余定理告诉我们，只要模数两两互质，几个余数条件可以拼成一个完整答案。它是“拆开算，再合起来”的典型代表。

最后，RSA 和日历分别展示了同余的两个极端：一个在保护网络通信，一个在回答今天之后多少天是星期几。一个听起来高深，一个每天都用得上。但底层问题其实都是同一个：除完以后，余几？

那么对任意整数 $a_1,a_2,\ldots,a_k$，方程组

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

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

也就是说，指数每 $12$ 个一轮。

所以可以用中国剩余定理。总模数

$M=2\times 3\times 5=30$

三个分量是

$M_1=15,\quad M_2=10,\quad M_3=6$

$9^{-1}\equiv 2\pmod {17}$

$999=10\times 99+9$，因此

$5^{999}\equiv 5^9\pmod {11}$

继续算：

$5^2=25\equiv 3\pmod {11}$

$5^4\equiv 3^2=9\pmod {11}$

$5^8\equiv 9^2=81\equiv 4\pmod {11}$

所以

$5^9\equiv 5^8\cdot 5\equiv 4\times 5=20\equiv 9\pmod {11}$

答案是 $9$。

$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\pmod {13}$

$7^4\equiv 10^2=100\equiv 9\pmod {13}$

$7^8\equiv 9^2=81\equiv 3\pmod {13}$

答案是 $3$。

求逆元：

$63\equiv 3\pmod 4,\quad 3\times 3\equiv 1\pmod 4$

所以 $y_1=3$。

$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=751$

$751$ 除以 $252$ 余 $247$，所以

$x\equiv 247\pmod {252}$

最小正整数解是 $247$。

后半段里的数可以这样看：

$p-k\equiv -k\pmod p$

所以

于是

根据威尔逊定理，$(p-1)!\equiv -1\pmod p$，所以

两边同乘 $(-1)^{(p-1)/2}$，得到

证毕。$\square$