同余的应用

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

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

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

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

费马小定理

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

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

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

费马小定理：设 $p$ 是素数， $a$ 是整数且 $p \nmid a$ （也就是 $a$ 不能被 $p$ 整除），则

$a^{p-1} \equiv 1 \pmod{p}$

也可以写成一个更宽松的版本：对任意整数 $a$ ，都有

$a^p \equiv a \pmod{p}$

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

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

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

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

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

第一，算大幂次的余数。

比如要算 $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}\equiv 5$ 。

费马小定理给了一个通用办法：如果 $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$ ，让这个式子不成立，那 $n$ 肯定不是素数。

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

威尔逊定理

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

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

威尔逊定理：正整数 $p$ 是素数，当且仅当

$(p-1)! \equiv -1 \pmod{p}$

注意这里是“当且仅当”。也就是说，素数一定满足这个式子；反过来，满足这个式子的数也一定是素数。

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

$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)!$ ，再往回倒推。

费马小定理与威尔逊定理对比图：左侧展示费马小定理，以p=7为例，列出a=1,2,3,4,5,6的a^6 mod 7的计算结果，全部等于1，体现指数为p-1的统一行为；右侧展示威尔逊定理，以p=7为例，展示1×2×3×4×5×6的配对消去过程（2与4配对，3与5配对，剩余1和6），最终乘积等于6≡-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$ 。这就像三个人分别给你一条线索，每条线索都不完整，但合在一起，居然能把答案锁住。

中国剩余定理（CRT）：设 $m_1,m_2,\ldots,m_k$ 是两两互质的正整数，令

$M=m_1m_2\cdots m_k$

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

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

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

这句话可以翻译成人话：

只要这些模数彼此不打架（两两互质），那么每个模数给出的余数条件，最终会拼出一个唯一的答案。这里的“唯一”，不是说只有一个整数，而是说在 $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$ ；只在第 $i$ 个方程里，通过乘上逆元 $y_i$ ，变成 $1$ 。

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

这里 $m_1=3,m_2=5,m_3=7$ ， $a=(2,3,2)$ 。

总模数：

$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$ ，就很难得到 $\varphi(n)$ ；没有 $\varphi(n)$ ，就很难得到私钥 $d$ 。

同余在这里扮演了很关键的角色：它让加密和解密都可以写成模幂运算。费马小定理和它的推广（欧拉定理）保证了这些运算能正确绕回来。中国剩余定理还常被用来加速 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$ 天，是星期五。

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

公历闰年规则：年份 $y$ 是闰年，当且仅当

$y$ 能被 $4$ 整除，但不能被 $100$ 整除；或
$y$ 能被 $400$ 整除。

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

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

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

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

例题精讲

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

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

先看能不能用费马小定理。 $13$ 是素数，且 $13\nmid 2$ ，所以

$2^{12}\equiv 1\pmod {13}$

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

把 $100$ 除以 $12$ ：

$100=12\times 8+4$

所以

$2^{100}=(2^{12})^8\cdot 2^4\equiv 1^8\cdot 16\pmod {13}$

$16$ 除以 $13$ 余 $3$ ，所以

$2^{100}\bmod 13=3$

这题的关键不是硬算 $2^{100}$ ，而是先把指数变小。 $\square$

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

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

$13$ 是素数，所以威尔逊定理给出：

$12!\equiv -1\equiv 12\pmod {13}$

而

$12!=12\times 11!$

所以

$12\times 11!\equiv 12\pmod {13}$

因为 $12\equiv -1\pmod {13}$ ，它的逆元还是 $12$ 。两边乘以 $12$ ：

$11!\equiv 12\times 12=144\equiv 1\pmod {13}$

所以答案是 $1$ 。 $\square$

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

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

先确认模数两两互质：

$\gcd(2,3)=\gcd(3,5)=\gcd(2,5)=1$

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

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

三个分量是

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

分别求逆元：

$15\equiv 1\pmod 2,\quad y_1=1$

$10\equiv 1\pmod 3,\quad y_2=1$

$6\equiv 1\pmod 5,\quad y_3=1$

这道题很友好，三个逆元刚好都是 $1$ 。

代入合成公式：

$x_0=1\times 15\times 1+2\times 10\times 1+3\times 6\times 1=53$

$53$ 除以 $30$ 余 $23$ ，所以

$x\equiv 23\pmod {30}$

最小正整数解是 $23$ 。验一下： $23$ 除以 $2$ 余 $1$ ，除以 $3$ 余 $2$ ，除以 $5$ 余 $3$ 。 $\square$

例题四：日历计算

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

先判断 $2024$ 年是不是闰年。 $2024$ 能被 $4$ 整除，不能被 $100$ 整除，所以它是闰年， $2$ 月有 $29$ 天。

从 $1$ 月 $1$ 日到 $7$ 月 $4$ 日，经过的天数是：

$31+29+31+30+31+30+3=185$

这里最后的 $3$ ，是从 $7$ 月 $1$ 日走到 $7$ 月 $4$ 日。

把 $185$ 对 $7$ 取余：

$185=26\times 7+3$

所以从星期一往后推 $3$ 天，是星期四。答案： $2024$ 年 $7$ 月 $4$ 日是星期四。 $\square$

例题五：模意义下的“除法”

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

先找 $9$ 在模 $17$ 下的逆元。直接试也行： $9\times 2=18\equiv 1\pmod {17}$ ，所以

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

于是

$5/9\equiv 5\times 2=10\pmod {17}$

验算一下：

$9\times 10=90\equiv 5\pmod {17}$

说明 $10$ 的确就是模 $17$ 意义下的 $5/9$ 。 $\square$

中国剩余定理示意图：以孙子算经题目为例，三个同心圆外环分别标注mod3（红色）、mod5（蓝色）、mod7（绿色），内部圆盘旋转到使三条颜色箭头分别对准余数2、3、2的刻度，交汇点指向23，说明三个独立余数条件唯一确定了mod 105范围内的数

练习

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

$5^{999} \bmod 11$ ：

$11$ 是素数，所以 $5^{10}\equiv 1\pmod {11}$ 。

$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$ 。

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

三个模数两两互质，所以可以用中国剩余定理。

总模数：

$M=4\times 7\times 9=252$

三个分量：

$M_1=63,\quad M_2=36,\quad M_3=28$

求逆元：

$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 \geq 3$ ，

$\left(\dfrac{p-1}{2}\right)!^2 \equiv (-1)^{(p+1)/2} \pmod p$

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

把 $(p-1)!$ 拆成两半：

(p-1)! = \left(1\cdot 2\cdots \frac{p-1}{2}\right) \left(\frac{p+1}{2}\cdot \frac{p+3}{2}\cdots (p-1)\right)

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

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

所以

(p-1)(p-2)\cdots \frac{p+1}{2} \equiv (-1)^{(p-1)/2}\left(\frac{p-1}{2}\right)! \pmod p

于是

(p-1)! \equiv (-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}$ ，得到

\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv (-1)^{(p+1)/2} \pmod p

证毕。 $\square$

要点收束

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

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

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

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

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

同余的应用

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

费马小定理

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

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

费马小定理：设 $p$ 是素数， $a$ 是整数且 $p \nmid a$ （也就是 $a$ 不能被 $p$ 整除），则

$a^{p-1} \equiv 1 \pmod{p}$

也可以写成一个更宽松的版本：对任意整数 $a$ ，都有

$a^p \equiv a \pmod{p}$

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

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

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

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

第一，算大幂次的余数。

比如要算 $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}\equiv 5$ 。

费马小定理给了一个通用办法：如果 $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$ ，让这个式子不成立，那 $n$ 肯定不是素数。

威尔逊定理

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

威尔逊定理：正整数 $p$ 是素数，当且仅当

$(p-1)! \equiv -1 \pmod{p}$

注意这里是“当且仅当”。也就是说，素数一定满足这个式子；反过来，满足这个式子的数也一定是素数。

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

$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)!$ ，再往回倒推。

中国剩余定理

翻译成同余就是：

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

答案是 $23$ 。

中国剩余定理（CRT）：设 $m_1,m_2,\ldots,m_k$ 是两两互质的正整数，令

$M=m_1m_2\cdots m_k$

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

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

在模 $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$

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

这里 $m_1=3,m_2=5,m_3=7$ ， $a=(2,3,2)$ 。

总模数：

$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 大概是这样玩的。

先选两个非常大的素数 $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$ 。

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

所以你可以这样理解：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$ 天，是星期五。

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

公历闰年规则：年份 $y$ 是闰年，当且仅当

$y$ 能被 $4$ 整除，但不能被 $100$ 整除；或
$y$ 能被 $400$ 整除。

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

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

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

例题精讲

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

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

先看能不能用费马小定理。 $13$ 是素数，且 $13\nmid 2$ ，所以

$2^{12}\equiv 1\pmod {13}$

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

把 $100$ 除以 $12$ ：

$100=12\times 8+4$

所以

$2^{100}=(2^{12})^8\cdot 2^4\equiv 1^8\cdot 16\pmod {13}$

$16$ 除以 $13$ 余 $3$ ，所以

$2^{100}\bmod 13=3$

这题的关键不是硬算 $2^{100}$ ，而是先把指数变小。 $\square$

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

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

$13$ 是素数，所以威尔逊定理给出：

$12!\equiv -1\equiv 12\pmod {13}$

而

$12!=12\times 11!$

所以

$12\times 11!\equiv 12\pmod {13}$

因为 $12\equiv -1\pmod {13}$ ，它的逆元还是 $12$ 。两边乘以 $12$ ：

$11!\equiv 12\times 12=144\equiv 1\pmod {13}$

所以答案是 $1$ 。 $\square$

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

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

先确认模数两两互质：

$\gcd(2,3)=\gcd(3,5)=\gcd(2,5)=1$

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

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

三个分量是

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

分别求逆元：

$15\equiv 1\pmod 2,\quad y_1=1$

$10\equiv 1\pmod 3,\quad y_2=1$

$6\equiv 1\pmod 5,\quad y_3=1$

这道题很友好，三个逆元刚好都是 $1$ 。

代入合成公式：

$x_0=1\times 15\times 1+2\times 10\times 1+3\times 6\times 1=53$

$53$ 除以 $30$ 余 $23$ ，所以

$x\equiv 23\pmod {30}$

最小正整数解是 $23$ 。验一下： $23$ 除以 $2$ 余 $1$ ，除以 $3$ 余 $2$ ，除以 $5$ 余 $3$ 。 $\square$

例题四：日历计算

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

先判断 $2024$ 年是不是闰年。 $2024$ 能被 $4$ 整除，不能被 $100$ 整除，所以它是闰年， $2$ 月有 $29$ 天。

从 $1$ 月 $1$ 日到 $7$ 月 $4$ 日，经过的天数是：

$31+29+31+30+31+30+3=185$

这里最后的 $3$ ，是从 $7$ 月 $1$ 日走到 $7$ 月 $4$ 日。

把 $185$ 对 $7$ 取余：

$185=26\times 7+3$

所以从星期一往后推 $3$ 天，是星期四。答案： $2024$ 年 $7$ 月 $4$ 日是星期四。 $\square$

例题五：模意义下的“除法”

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

先找 $9$ 在模 $17$ 下的逆元。直接试也行： $9\times 2=18\equiv 1\pmod {17}$ ，所以

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

于是

$5/9\equiv 5\times 2=10\pmod {17}$

验算一下：

$9\times 10=90\equiv 5\pmod {17}$

说明 $10$ 的确就是模 $17$ 意义下的 $5/9$ 。 $\square$

练习

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

$5^{999} \bmod 11$ ：

$11$ 是素数，所以 $5^{10}\equiv 1\pmod {11}$ 。

$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$ 。

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

三个模数两两互质，所以可以用中国剩余定理。

总模数：

$M=4\times 7\times 9=252$

三个分量：

$M_1=63,\quad M_2=36,\quad M_3=28$

求逆元：

$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 \geq 3$ ，

$\left(\dfrac{p-1}{2}\right)!^2 \equiv (-1)^{(p+1)/2} \pmod p$

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

把 $(p-1)!$ 拆成两半：

(p-1)! = \left(1\cdot 2\cdots \frac{p-1}{2}\right) \left(\frac{p+1}{2}\cdot \frac{p+3}{2}\cdots (p-1)\right)

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

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

所以

(p-1)(p-2)\cdots \frac{p+1}{2} \equiv (-1)^{(p-1)/2}\left(\frac{p-1}{2}\right)! \pmod p

于是

(p-1)! \equiv (-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}$ ，得到

\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv (-1)^{(p+1)/2} \pmod p

证毕。 $\square$

要点收束

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

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

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

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