同余的应用

把一个整数换成它的余数，好像丢掉了很多信息：$23$、$128$、$233$ 除以 $105$ 都余 $23$，单看余数，我们分不清它们。可有意思的地方也在这里——原数有多大不再碍事，留下来的那一点信息，恰好可能就是问题需要的全部。

上一章，我们学会了在同余式里做加减乘法，也弄清了什么时候可以约分、怎样用逆元解方程。现在试着把这些工具接起来：一个大得写不下的幂，为什么几次乘法就能算出余数？几条各自模糊的余数线索，为什么能合成一个确定的答案？把一个数接连乘方两次，怎么还会回到原来的数？

我们先从幂的余数里找规律。等这些问题有了答案，再回到每天都在用的日历，你会发现，同余的用途虽然不同，推理用的始终是前面那些朴素的整数规则。

为什么不同的数，乘方后都余一

先在模 $7$ 的世界里算一小段。$2$ 的连续幂，余数是 $2,4,1,2,4,1,\ldots$；$3$ 的连续幂，余数是 $3,2,6,4,5,1,\ldots$。两组节奏不一样，却都在第六次幂处回到了 $1$。换成 $4$、$5$、$6$，第六次幂也一样余 $1$。

这不是模 $7$ 独有的巧合。只要模数 $p$ 是素数，所有不是 $p$ 的倍数的整数，都有这样一个共同的回归点：

这就是费马小定理。先把条件看牢：模数必须是素数，底数不能被它整除。比如 $7^6$ 模 $7$ 余 $0$，当然不会余 $1$。至于 $p-1$，它保证的是一个可用的周期，不一定是最短周期；刚才 $2$ 模 $$ 的幂每 步就重复了， 步只是走了两圈。

把同一排数重新排一次

为什么会有这个共同的回归点？直接展开大幂很难看出原因，我们换个动作：把 $1,2,\ldots,p-1$ 全部乘上 $a$，再取余。

例如模 $7$ 时全部乘 $3$，得到

右边还是 $1$ 到 $6$，只是顺序变了。这个现象能推广，需要说明两件事。首先，任何一个 $ka$ 都不可能余 $0$，因为 $p\nmid a$，如果 $p\mid ka$，素数整除乘积的性质就迫使 ，而 。其次，它们不可能有重复余数：若 ，由于 ，上一章的约分规则允许约去 ，得到 。两个数都在 到 之间，只能是 。

现在有 $p-1$ 个互不重复的非零余数，可用的非零余数也恰好只有 $p-1$ 个，所以它们必然把 $1,2,\ldots,p-1$ 各用了一次。把这些数全部相乘，顺序不会影响乘积，于是

记 $(p-1)!=1\cdot2\cdots(p-1)$，左边提出 $p-1$ 个 $a$，就变成

这个阶乘里没有 $p$ 的倍数，素数 $p$ 也就不整除它，因此 $\gcd((p-1)!,p)=1$。我们可以合法地约去阶乘，留下 $a^{p-1}\equiv1\pmod p$。共同的回归点，就藏在“乘上 只是重新排列非零余数”这件事里。

如果希望把 $p$ 的倍数也包括进来，可以用另一个形式：对任意整数 $a$，都有

当 $p\nmid a$ 时，把费马小定理两边乘 $a$ 即可；当 $p\mid a$ 时，两边都余 $0$。反过来，对 $p\nmid a$ 的情形约去 $a$，又能回到原式。因此两个形式并不矛盾，只是后一个把零余数也照顾到了。

幂很大，计算可以很小

现在计算 $3^{100}$ 除以 $7$ 的余数。因为 $3^6\equiv1\pmod7$，先把指数按 $6$ 分组：

这里缩小的是指数，但指数除以的是 $p-1$，不是模数 $p$。而且必须先确认底数与模数互质。若把 $7^6$ 的指数也随手模 $6$ 化成 $0$，就会错误地得到 $7^0=1$。

费马小定理还给出一种求逆元的办法。因为

所以 $a^{p-2}$ 是 $a$ 模素数 $p$ 的逆元，前提仍是 $p\nmid a$。例如 $3$ 模 $7$ 的逆元可取 ；要解 ，便得到 。代回去，，正好。底数很大时仍可先取余，幂很大时则反复平方、每步取余，后面解密时我们会完整算一次。

能用它证明一个数是素数吗

有了这条规律，很自然会反过来试：某个数 $n$ 满足 $2^{n-1}\equiv1\pmod n$，它是不是素数？先别把箭头倒过来。费马小定理说“素数一定通过检查”，没有说“通过检查的一定是素数”。

一个具体的反例是 $341=11\times31$。它明明是合数，可是

所以 $2^{340}=(2^{10})^{34}\equiv1\pmod{341}$。这样的合数叫作以 $$ 为底的费马伪素数。一般说，合数 与底数 互质，却满足 ，就称 是以 为底的费马伪素数。

反方向的排除却可靠。$2$ 已知是素数；对 $n>2$，选择 $1<a<n$：如果发现 $\gcd(a,n)>1$，已经找到了非平凡公因数；如果互质却算出 ，也能断定 是合数。例如 ，不是 ，便排除了 为素数的可能。一次失败足以否定，通过一次则不能保证。还有一些合数会对所有与它互质的底数通过这种检查，叫作卡迈克尔数；因此单靠不断增加这类检查，也不能把费马小定理直接变成一个对所有整数都充分的素数判据。

把所有非零余数乘起来，会剩下谁

前面把 $(p-1)!$ 约掉了，没有计算它自己余几。现在反过来研究这个乘积。模 $7$ 时，$6!=720$ 余 $6$；模 $5$ 时，$4!=24$ 余 。结果都比模数少 ，也就是余 。

这条规律叫作威尔逊定理，而且它比刚才的单次费马检查更强：对整数 $n\ge2$，

这里的“当且仅当”有两个方向，两边都需要证明。

逆元会把大部分因子配成一

先设 $p$ 是奇素数。$1,2,\ldots,p-1$ 每个数都有唯一的逆元。模 $7$ 时，$2$ 与 $4$ 配成一对，$3$ 与 配成一对，因为

剩下 $1$ 和 $6$，它们的逆元各是自己。于是全部乘起来，结果就是 $1\times6\equiv-1\pmod7$。

一般情形中，必须排除“还有别的数以自己为逆元”的可能。若 $a$ 的逆元就是自己，则

$p$ 是素数，必然整除其中一个因子，所以 $a\equiv1$ 或 $a\equiv-1\pmod p$。在 $1$ 到 $p-1$ 里，这恰好就是 和 。其余数都与不同于自己的逆元配对，而且逆元的逆元会回到原数，配对不会重叠或遗漏。每一对乘积余 ，最后留下

$p=2$ 要单独检查，因为这时 $1$ 和 $p-1$ 是同一个数，不能算成两个因子。不过 $1!=1\equiv-1\pmod2$，结论照样成立。

为什么合数绝对过不了这一关

现在假设 $n\ge2$ 满足 $(n-1)!\equiv-1\pmod n$。如果 $n$ 是合数，就能找到一个因数 $d$，使 。因为 出现在 中，它整除 ；另一方面，同余条件说明 ，从而 也整除 。

两式相减就得到 $d\mid1$，这和 $d>1$ 矛盾。因此 $n$ 只能是素数，逆方向也证明完了。我们没有假定“所有合数的阶乘都余 $0$”；事实上 $3!$ 模 $4$ 余 $2$，那种说法会漏掉反例。

威尔逊定理给出了准确的素数判据，但直接从 $1$ 一直乘到 $n-1$，即使每步都取余，乘法次数仍随 $n$ 增长。数学上判得准，不代表这个直接算法适合检查很大的数。它更方便的用途，是计算接近 $(p-1)!$ 的阶乘余数。

例如求 $10!$ 模 $13$ 的余数。先用定理抓住 $12!\equiv-1$，再拆下最后两个因子：

所以 $2\cdot10!\equiv-1\equiv12\pmod{13}$。$2$ 的逆元是 $7$，两边乘 $7$ 得到 。这里每一次“除法”，背后仍然是上一章的逆元规则。

三条余数线索，怎样拼成一个答案

假设一堆小石子，三个一组余 $2$，五个一组余 $3$，七个一组余 $2$。单看第一条，$2,5,8,11,\ldots$ 都有可能；再加后两条，范围突然收紧了。我们不猜答案，沿着条件一步步找。

第一条说 $x=2+3t$。代入模 $5$ 的条件，得到

$3$ 的逆元是 $2$，所以 $t\equiv2\pmod5$，即 $t=2+5s$。这样前两条条件已经合成

再代入模 $7$ 的条件：$8+15s\equiv2\pmod7$，也就是 $1+s\equiv2\pmod7$，于是 。最终

所以最少有 $23$ 颗。检验也很直接：$23=3\times7+2=5\times4+3=7\times3+2$。而 颗同样符合题意，说明三条线索并没有确定一个唯一整数，它确定的是。

从这个解法读出一般规律

这就是中国剩余定理要描述的现象。设 $m_1,\ldots,m_k$ 都不小于 $2$，并且两两互质，令 $M=m_1\cdots m_k$。任意指定整数余数 ，方程组

总有解，而且在模 $M$ 的意义下唯一。“两两互质”是每一对模数的最大公因数都等于 $1$，不是仅仅全部模数的共同最大公因数等于 $1$。例如 $6,10,15$ 全体的最大公因数是 $1$，但任意一对都不互质，不能直接套这个版本。

先证明两个模数的情形。对 $x\equiv a\pmod m$ 和 $x\equiv b\pmod n$，把第一式写成 $x=a+mt$，第二式就变成 。只要 ， 模 的逆元存在，便一定能找到 ，所以解存在。

若 $x,y$ 都满足原方程组，那么 $m\mid(x-y)$，$n\mid(x-y)$。由于两个模数互质，$mn\mid (x-y$，即 ，这就证明了唯一性。多个模数时，先合并前两个，再把合并结果与下一个条件合并。两两互质保证已经合并的模数乘积仍与下一个模数互质，这个过程能一直进行下去。

也可以给每条线索做一个专用开关

逐步合并适合手算，还有一种一次性构造。令 $M_i=M/m_i$，因为 $\gcd(M_i,m_i)=1$，可取逆元 使 。那么 在第 个模数下余 ，在其他模数下全余 。乘上 ，就像只打开第 条线索的开关，其他线索都不受影响。

把这些项相加便得到

对任意一个 $m_j$ 取模时，只有第 $j$ 项留下 $a_j$，其余项全消失，所以它确实是解。回到石子问题，$M=105$，三个 是 ，对应逆元可取 ，因此

两种方法算出的代表数不同，却落在同一个剩余类里。如果要求最小非负解，就把结果化到 $0$ 至 $M-1$；如果要求最小正解而余数恰好是 $0$，答案应取 $M$。

模数不互质，就一定无解吗

也不是。例如 $x\equiv1\pmod4$ 和 $x\equiv3\pmod6$，两条都要求 $x$ 是奇数，没有互相冲突。令 $$，得到 。按上一章的线性同余解法，除去共同因子 ，得到 ，所以 ，最终

这里重复的间隔是 $\operatorname{lcm}(4,6)=12$，不是 $24$。若把第二条改成 $x\equiv2\pmod6$，它要求 $x$ 是偶数，就和第一条冲突了。

一般地，记 $g=\gcd(m,n)$。两个条件 $x\equiv a\pmod m$、$x\equiv b\pmod n$ 相容，当且仅当

原因不需要新工具：代入 $x=a+mt$ 后，得到 $mt\equiv b-a\pmod n$，上一章已经证明它可解当且仅当 $g\mid(b-a)$。如果相容，任意两解之差都同时被 整除，因而被它们的最小公倍数整除；反过来，给一个解加最小公倍数的整数倍，仍满足两个条件。因此解在模 下唯一。

多条条件也可以逐步合并，检查新条件与已经合并的条件是否相容。等价地，任意两条余数都必须在对应模数的最大公因数下相同：$a_i\equiv a_j\pmod{\gcd(m_i,m_j)}$。这个条件也充分：把每个模数分解成素数幂，对每种素数保留出现过的最高次幂及其余数；两两相容保证较低次幂的要求已包含其中，而不同素数的这些最高次幂彼此互质，便能用刚才的定理拼起来。最终的重复间隔仍是全部模数的最小公倍数。

乘方两次，为什么能解回原来的消息

余数可以拆开，再拼回来；幂也能绕一圈，回到原来的余数。把这两件事合在一起，就能理解 RSA 的数学原理。

设想我们公开一套把数字变成另一个数字的规则，让别人能够加密消息，同时自己保留一项信息，用来恢复原数。RSA 采用的是模幂：先把消息表示成 $0$ 到 $n-1$ 中的整数 $m$，计算 $m^e$ 模 $n$。这里先研究数字如何往返，不处理文字编码的具体安排。

先造一套能在纸上算完的钥匙

取两个不同的奇素数 $p=5,q=11$，于是 $n=pq=55$。再计算一个用来安排指数的数

选 $1<e<K$ 且 $\gcd(e,K)=1$，例如 $e=3$。接着找它模 $K$ 的逆元，取正整数 满足 。因为 ，可取 。公开的公钥是 ，保密的解密指数是 ，素因数 也要保密。

这时加密规则是取 $c\equiv m^3\pmod{55}$ 的最小非负余数，解密规则是取 $m'\equiv c^{27}\pmod{55}$ 的最小非负余数。例如消息 ，加密得到

接收者只收到 $13$，怎样把它还原成 $7$？不必完整展开 $13^{27}$，用重复平方，每做一次乘法就取余：

因为 $27=16+8+2+1$，所以

继续随算随取余：$31\times36=1116\equiv16$，$16\times4=64\equiv9$，$9\times13=117\equiv7$。解密结果果然是 。重复平方的好处在于，每增加一个二进制位只需要继续平方并选择是否相乘，不需要做 次，更不需要先写下整个大幂。

不能只证明与模数互质的消息

这个例子成功了，还不足以保证每条消息都能回来。特别是 $m=5$、$m=11$，甚至 $m=0$，它们与 $55$ 不互质，也必须能正常恢复。

一般地，取不同奇素数 $p,q$，令 $n=pq$、$K=(p-1)(q-1)$，按上面的办法选正整数 $e,d$，则 ，其中 是非负整数。加密再解密，相当于计算 模 。直接在模 下套费马小定理不行，因为 是合数；我们把问题拆到模 和模 下。

先看模 $p$。如果 $p\mid m$，那么 $m^{ed}$ 和 $m$ 都余 $0$，已经相同。如果 $p\nmid m$，费马小定理给出 ，于是

无论哪种情形，结论都成立。同样分情况考察模 $q$，也得到 $m^{ed}\equiv m\pmod q$。因为 $p,q$ 互质，中国剩余定理的唯一性告诉我们

因此任意消息 $0\le m<n$ 都能恢复；解密结果和原消息都在这个范围里，同余就意味着相等。这个证明完全处理了不互质的消息，没有要求它们拥有逆元。

还可以亲手检查 $m=5$：加密后 $5^3\equiv15\pmod{55}$。解密时在模 $5$ 下得到 $0$；在模 下，，而 ，所以 。由 、，得 。 到 中同时满足这两个余数条件的数就是 ，它确实回来了。

数学上的可逆性与实际加密的安全性是两件事。我们这组参数太小，一眼就能把 $55$ 分解，当然不能保护消息。知道 $p,q$ 就能算出 $K$，进而求出 $d$；这一点解释了为什么要保密素因数。不过上面的证明只保证往返正确，并不证明某个实际系统足够安全。这里展示的是未经填充的教学模型，实际使用需要合适的参数、标准的随机化填充和成熟的实现。不能把这些小数值或裸模幂直接当作可用的加密方案。

日历里最容易错的，其实是数了几天

从密码回到日历，模数一下子缩成了 $7$。不过日历题常见的错误，往往不是不会取余，而是把起点多算了一次。

假设今天星期三。说“$100$ 天后”，表示从今天向后移动 $100$ 次，每次一天。因为 $100\equiv2\pmod7$，结果是星期五。若题目说“把今天算第 $1$ 天，第 $100$ 天是星期几”，实际只移动 $99$ 天，，结果就成了星期四。

可以把星期一到星期日依次记作 $0,1,\ldots,6$。若起始日编号为 $w$，经过 $D$ 天后的编号满足 $w'\equiv w+D\pmod7$。往前推日期则减去 ，负余数最后换成 到 内的代表即可。用什么编号并不重要，前后一致才重要。

跨月时，先把经过的天数算清楚

公历平年有 $365$ 天，闰年有 $366$ 天，额外一天在二月。年份能被 $4$ 整除但不能被 $100$ 整除，或者能被 $400$ 整除，就是闰年。因此 $2024$ 是闰年，$2100$ 不是，$2000$ 是。判断世纪年时，不能只检查能否被 整除。

已知 $2024$ 年 $1$ 月 $1$ 日是星期一，计算同年 $7$ 月 $4$ 日的星期。$2024$ 是闰年，前六个月的天数依次是 $31,29,31,30,31,30$。从 月 日走到 月 日要经过这六个月的全部天数，从 月 日走到 月 日还要走 天，因此

星期一向后移 $3$ 天是星期四。最后加的是 $4-1$，不是 $4$：站在 $7$ 月 $1$ 日时还没有走任何一天。对于同年日期，从 $1$ 月 $1$ 日出发，通用做法就是“此前完整月份的总天数，加当天日期减一”。

同样的计数还能解释跨年变化：一个完整平年使次年同一月日起点的星期向后移 $1$ 天，因为 $365\equiv1\pmod7$；一个完整闰年则向后移 $2$ 天。说的是从这一年 $1$ 月 $1$ 日到下一年 $1$ 月 日这样的完整年份跨度，任意两个具体日期之间仍要检查是否跨过了二月的额外一天。

把这些方法连起来试一试

练习一：同样是大幂，先检查条件。 计算 $5^{123}\bmod11$ 和 $11^{120}\bmod11$。为什么不能把第二个指数也按 $10$ 取余？

练习二：少乘两个数。 计算 $14!$ 模 $17$ 的余数，并说明推导中为什么可以约分。

练习三：三条独立线索。 求满足 $x\equiv2\pmod5$、$x\equiv3\pmod7$、$x\equiv4\pmod8$ 的全部整数解和最小正整数解。

练习四：有共同因子时先对账。 解 $x\equiv5\pmod6$、$x\equiv1\pmod8$。如果把第二个余数改成 $2$，是否还有解？

练习五：让不互质的消息也走一遍。 使用正文的 RSA 参数 $n=55,e=3,d=27$，加密消息 $m=11$，再用模 $5$、模 $11$ 的计算验证解密结果。

练习六：同一个起点，两种数法。 某个平年的 $1$ 月 $1$ 日是星期二，问这一年 $3$ 月 $1$ 日是星期几；再问把 $1$ 月 $1$ 日算作第 $1$ 天，这一年的第 $60$ 天是星期几。如果这一年改为闰年，两个问题的答案分别怎样变化？

从最初的“能不能整除”，到现在的“幂运算能不能还原”，这门课其实一直围绕整数之间的约束展开。素数分解告诉我们一个数由什么组成，最大公因数帮助判断什么能约掉，最小公倍数决定几个周期何时重合，同余则让我们只保留当前问题需要的余数信息。

再遇到陌生的整数题，可以先做一个具体动作：挑几个小数算一算，看看哪些结果重复，哪些条件彼此冲突。发现规律以后，再追问它依赖哪个条件、有没有反例、能否用整除和余数把理由说完整。刚才那些看着像巧合的结果，就是这样一步步变成定理的。

若改为闰年，并仍假设 $1$ 月 $1$ 日星期二，$3$ 月 $1$ 日距离起点为 $31+29=60$ 天，$60\equiv4\pmod7$，所以是星期六。但是第 $60$ 天始终只距离第 $1$ 天 $59$ 天，因此仍是星期五；在闰年它对应 $2$ 月 $29$ 日。日期与序号的区别，正是多出来那一天改变的地方。