同余是什么

一只只有时针的 $12$ 小时制钟表停在 $10$，让它向前走 $5$ 小时，时针最后指向 $3$。这件事人人都会算，可要是把过程写成 $10+5=3$，又明明不对。我们究竟在什么时候，把 $15$ 偷偷换成了 $3$？

换掉的是完整的小时数，留下的是表盘上的位置。$15$ 比 $3$ 多出一整圈，而表盘不会替我们记录已经转过多少圈。这里说的只是 $12$ 小时制的显示位置；真实生活中的上午、下午、日期并没有因此相同。晚上 $10$ 点过 $5$ 小时，是次日凌晨 $3$ 点。

上一章找最小公倍数时，我们关心两个周期什么时候重新对齐。这一章把眼光移到周期内部：不管已经走过多少圈，现在落在哪个位置？沿着这个问题走下去，我们会得到一套能加、能乘、能解方程的算法。至于除法，它会在途中给我们出一道小难题。

---

一整圈的差别，可以暂时忽略

在 $12$ 小时制表盘上，累计走 $3$、$15$、$27$ 个小时都落在同一位置，倒退 $9$ 小时也一样。把这些整数排起来：

$$\ldots,-21,-9,3,15,27,39,\ldots$$

相邻两项总差 $12$，任意两项的差都是 $12$ 的整数倍。我们不必真的画出一个表盘，只要检查“差了多少个整圈”，就知道它们会不会重合。

选定一个整数 $m\geq 2$，把它叫作模数。对于整数 $a,b$，如果 $m\mid(a-b)$，就说 $a$ 与 $b$ ，记作：

$$a\equiv b\pmod m \quad\Longleftrightarrow\quad m\mid(a-b).$$

所以 $27\equiv3\pmod{12}$，因为 $27-3=2\times12$；$-9\equiv3\pmod{12}$，因为 。如果差不能被模数整除，就用 ，例如 。

同余符号右边的模数不能随意省略。$15$ 与 $3$ 模 $12$ 同余，模 $5$ 却不同余，因为 $12$ 不是 $5$ 的倍数。同样两个整数，换了周期，结论可能就变了。

为什么“差被整除”就是“余数相同”

我们在第一章学过带余除法。对固定的正模数 $m$，可以唯一地写出：

$$a=q_1m+r_1,\qquad b=q_2m+r_2, \qquad 0\leq r_1,r_2<m.$$

如果 $r_1=r_2$，两式相减，余数正好抵消，得到 $a-b=(q_1-q_2)m$，因此 。这解释了余数相同为什么会让两数相差整圈。

反过来，假设 $m\mid(a-b)$。从

$$a-b=(q_1-q_2)m+(r_1-r_2)$$

可知 $m$ 也整除 $r_1-r_2$。可两个余数都在 $0$ 到 $m-1$ 之间，所以 。这个范围内唯一的 的倍数是 ，只能有 。两个方向都证明了，“差被模数整除”和“除以模数的余数相同”确实是同一件事。

这个证明对负整数也成立。比如 $-17$ 除以 $5$，应写成：

$$-17=(-4)\times5+3.$$

因此标准余数是 $3$，有 $-17\equiv3\pmod5$。虽然 $-17=(-3)\times5-2$ 也是真等式，但 不满足带余除法对余数的范围要求。它可以是计算时方便使用的同余代表，却不是最小非负余数。

---

无限多个整数，分成有限几组

模 $4$ 时，每个整数都有且只有一个标准余数：$0,1,2,3$。我们把余数相同的整数放在一起，就得到四组：

$$\begin{aligned} [0]_4&=\{\ldots,-8,-4,0,4,8,\ldots\},\\ [1]_4&=\{\ldots,-7,-3,1,5,9,\ldots\},\\ [2]_4&=\{\ldots,-6,-2,2,6,10,\ldots\},\\ [3]_4&=\{\ldots,-5,-1,3,7,11,\ldots\}. \end{aligned}$$

每一组叫作一个剩余类。一般地，$a$ 所在的模 $m$ 剩余类是：

$$[a]_m=\{a+km:k\in\mathbb Z\}.$$

例如 $[1]_4=[5]_4$，它们是同一组的两种名字，而 $1$ 与 $5$ 仍然是不同整数。不要把“一个代表”与“代表所在的整组”混在一起。

把模数换成 $3$，就只有三组。下图各列出每组中的五个整数；沿着同一行，每次加上或减去 $3$，仍然留在原来那一组。

这套分组为什么不会出现“$a$ 跟 $b$ 一组，$b$ 跟 $c$ 一组，$a$ 却跟 $c$ 不一组”的矛盾？因为固定模数后，同余满足三个性质。

• 自反性：$a\equiv a\pmod m$，因为 $a-a=0$，而 $m\mid0$。
• 对称性：若 $$，则 ，因为 ，仍是 的倍数。

满足这三个性质的关系叫作等价关系。对同余来说，带余除法又告诉我们：所有整数都能归入 $[0]_m,\ldots,[m-1]_m$ 中的一组，且不同组不会重叠。因此模 $m$ 恰好有 $m$ 个剩余类。

如果每组派出一位代表，我们就得到一个完全剩余系。模 $5$ 时，$\{0,1,2,3,4\}$ 最常用；$\{-2,-1,0,1,2\}$ 也可以，它们的标准余数依次是 $3,4,0,1$，五组一个不少。可 不行， 和 重复代表同一组，却漏了余数为 的一组。

连续的 $m$ 个整数总能组成模 $m$ 的完全剩余系。因为其中任意两个不同整数的差，绝对值都小于 $m$，不可能是非零的 $m$ 的倍数，所以它们两两不同余。既有 $m$ 个不同的类，就已经把全部类选齐了。

---

为什么可以边算边丢掉整圈

现在计算 $2026\times2027$ 除以 $7$ 的余数。直接乘当然能做，但已知

$$2026\equiv3\pmod7,\qquad2027\equiv4\pmod7,$$

能不能直接算 $3\times4$？答案是能，理由要从同余定义里找。

设 $a\equiv b\pmod m$，$c\equiv d\pmod m$。因为 $a-b$ 与 都被 整除，下面两个差也被 整除：

$$(a+c)-(b+d)=(a-b)+(c-d),$$ $$(a-c)-(b-d)=(a-b)-(c-d).$$

乘法稍微绕一点：在 $ac-bd$ 中加上再减去 $bc$，就能拆成已知的差：

$$ac-bd=c(a-b)+b(c-d).$$

右边每项都被 $m$ 整除，因而乘法也保留同余关系。我们得到：

$$\begin{aligned} a+c&\equiv b+d\pmod m,\\ a-c&\equiv b-d\pmod m,\\ ac&\equiv bd\pmod m. \end{aligned}$$

所以刚才的计算可以缩成：

$$2026\times2027\equiv3\times4=12\equiv5\pmod7.$$

这也解释了为什么选哪个剩余类代表都不影响结果。你用 $3$ 还是 $-4$ 代替 $2026$，最终得到的标准余数都一样。

乘方也可以，指数却不能随便改

既然乘法允许替换同余代表，把它重复使用，就得到：对正整数 $n$，

$$a\equiv b\pmod m \quad\Longrightarrow\quad a^n\equiv b^n\pmod m.$$

$n=0$ 时，若两个底数都非零，两边都等于 $1$，结论仍成立。本章不讨论 $0^0$。

但这条规则替换的是底数。即使 $5\equiv2\pmod3$，也不能因此把 $2^5$ 换成 $2^2$：前者模 $3$ 余 ，后者模 余 。以后我们会学习在特定条件下缩小指数的方法，现在不能把底数的规则挪到指数上。

负代表有时比标准余数更好用。求 $99^{37}+101^{38}$ 的末两位，就可以把两个底数分别换成模 $100$ 的 $-1$ 和 $1$：

$$99^{37}+101^{38}\equiv(-1)^{37}+1^{38}=-1+1=0\pmod{100}.$$

所以末两位是 $00$。计算途中允许用负数，只有最终回答标准余数时才需要落回规定范围。这也让我们看清“丢掉整圈”真正保留了什么：它保留加减乘运算后的余数，却不会保留整数的大小关系。$99$ 比 $1$ 大，并不意味着选出的同余代表 $-1$ 也比 $1$ 大。

已经学过的十进制整除判别，也能用这套运算重新说清楚。设一个非负整数的各位数字是 $d_0,d_1,\ldots,d_s$，其中 $d_0$ 是个位，那么

$$N=d_0+10d_1+10^2d_2+\cdots+10^sd_s.$$

因为 $10\equiv1\pmod9$，所以

$$N\equiv d_0+d_1+\cdots+d_s\pmod9.$$

例如 $123456789$ 的数字和为 $45$，因此它能被 $9$ 整除。把模数换成 $11$，则 $10\equiv-1\pmod{11}$，各次幂在 $1,$ 之间交替，于是数字的交错和自然出现。第二章看起来各有口诀的判别法，现在都来自同一个运算原则。

把所有余数试一遍，就能排除无限多个数

完全剩余系还有一种用法：如果问题只取决于模 $m$ 的余数，我们只检查 $m$ 个代表，就等于检查了所有整数。比如一个平方数除以 $4$，会不会余 $2$ 或 $3$？

把模 $4$ 的四个代表分别平方：

$$0^2\equiv0,\quad1^2\equiv1,\quad2^2\equiv0,\quad3^2\equiv1\pmod4.$$

由于同一剩余类中的整数平方后仍然同余，这四次检查已经覆盖了全部整数。所以平方数模 $4$ 只能余 $0$ 或 $1$，绝不会余 $2$ 或 $3$。例如 $4k+3$ 不可能是整数的平方，任何整数 $k$ 都不行。

但方向不能倒过来：余数是 $0$ 或 $1$，只是“可能成为平方”的必要条件。$21$ 模 $4$ 余 $1$，它却不是平方数。这类判断能快速排除不可能的候选者，不能独自确认剩下的候选者一定成立。

---

除法为什么会把答案弄丢

普通等式里，两边乘了同一个非零数，可以约掉。同余却有一个立刻能检查的反例：

$$2\times3\equiv2\times0\pmod6, \qquad3\not\equiv0\pmod6.$$

左边确实同余，因为 $6$ 与 $0$ 都是 $6$ 的倍数；约掉 $2$ 后却不再同余。原因是乘以 $2$ 把原本不同的两个剩余类送到了同一个位置，丢掉了区分它们的信息。

其实并非完全不能约，而是约掉因子时，可能需要一起缩小模数。设 $c$ 是整数，$d=\gcd(c,m)$，则有准确的双向规则：

$$ca\equiv cb\pmod m \quad\Longleftrightarrow\quad a\equiv b\pmod{m/d}.$$

我们把 $c=dc'$、$m=dm'$ 代入定义：

$$m\mid c(a-b) \quad\Longleftrightarrow\quad m'\mid c'(a-b).$$

因为 $\gcd(c',m')=1$，第四章的互质整除性质允许从后一个式子推出 $m'\mid(a-b)$。反过来，若 ，乘上 就能恢复 ，因此两边确实等价。

例如 $6a\equiv6b\pmod{15}$，约掉 $6$ 后正确的模数是 $15/\gcd(6,15)=5$，所以得到 $$。特别地，只有当 时，这条通用约分规则才保留原模数 。

这里有一个边界值得交代：若 $m\mid c$，包括 $c=0$，那么 $d=m$，新模数是 $1$。虽然平时我们取 $m\geq2$，此处可以临时把定义延伸到模 ：任意两整数的差都被 整除，因此所有整数都同余。这正好对应原式无论 取什么都成立，约分后已经没有限制。

---

用逆元把乘法倒过来

如果不想每次约分都回到整除定义，有没有一个数，乘上去就能把原来的系数“抵消成 $1$”？以模 $14$ 为例，$5\times3=15\equiv1\pmod{14}$。因此先乘 $5$ 再乘 $$，效果等于乘 。这个 就叫作 模 的。

一般地，若整数 $u$ 满足

$$au\equiv1\pmod m,$$

就称 $u$ 是 $a$ 模 $m$ 的逆元，常写作 $a^{-1}\equiv u\pmod m$。这里的 $$ 指模运算中的逆元，不是普通分数 。

逆元到底什么时候存在？假如 $au\equiv1\pmod m$，就有整数 $v$ 使 $au+mv=1$。任何 $a,m$ 的公因数都整除左边，因而整除 ，所以只能有 。

反过来，若 $\gcd(a,m)=1$，裴蜀等式保证存在整数 $u,v$ 使 $au+mv=1$。模 $m$ 看这个等式， 消失，恰好得到 。因此：

$$a\text{ 模 }m\text{ 有逆元} \quad\Longleftrightarrow\quad \gcd(a,m)=1.$$

逆元的整数代表可以有很多个，但模 $m$ 的剩余类只有一个。若 $au\equiv av\equiv1\pmod m$，利用 $a$ 与 $m$ 互质约分，就有 $u\equiv v$。

不靠试数，怎样把逆元算出来

我们求 $17$ 模 $43$ 的逆元。欧几里得算法给出：

$$43=2\times17+9,\qquad17=9+8,\qquad9=8+1.$$

从最后一步往回代：

$$\begin{aligned} 1&=9-8\\ &=9-(17-9)\\ &=2\times9-17\\ &=2(43-2\times17)-17\\ &=2\times43-5\times17. \end{aligned}$$

所以逆元是 $-5$，也可以选标准代表 $38$。验算 $17\times38=646=15\times43+1$，余数确实为 $1$。第四章里保存下来的线性组合，在这里直接给出了“倒着乘”的办法。

求逆元前先求最大公因数，可以避免白找。例如模 $12$ 时，$6$ 虽然不是 $0$，却没有逆元，因为 $6u$ 无论乘什么整数都被 $6$ 整除，不可能与 $1$ 相差 $12$ 的倍数。相比之下，若模数是素数 $p$，那么 每个数都与 互质，因此每个非零剩余类都有逆元。素数模数下的除法格外方便，原因已经藏在互质这个条件里。

互质乘法为什么只是重新排队

把模 $5$ 的完全剩余系 $0,1,2,3,4$ 全部乘以 $2$，取标准余数后得到 $0,2,4,1,3$。没有少，也没有重复，只是换了顺序。

一般地，如果 $\gcd(a,m)=1$，完全剩余系中的两个代表 $r,s$ 满足 $ar\equiv as\pmod m$，约去 就会得到 。所以原来不同类的代表，乘完仍然不同类。总共 个互不同余的结果，只能仍覆盖所有剩余类。

这个结论把逆元与“排队”联系起来：互质乘法不会把两组挤到一起，因此有办法倒着找回原来的组。下一章研究某些幂为什么会回到余数 $1$ 时，还会用到这种重新排列的想法。

---

一个同余方程，究竟有几个解

现在来解 $5x\equiv3\pmod{14}$。既然 $5$ 的逆元是 $3$，两边乘以 $3$，便得到

$$x\equiv9\pmod{14}.$$

这里的“一个解”是一个剩余类，全部整数解仍然有无限多个：$x=9+14k$，$k\in\mathbb Z$。代回去有 $5x-3=42+70k=14(3+5k)$，每一个都满足要求。

一般的线性同余方程写成 $ax\equiv b\pmod m$。设 $d=\gcd(a,m)$，如果有解，那么存在整数 $y$ 使

$$ax-my=b.$$

由于 $d$ 同时整除 $a$ 与 $m$，它必然整除左边，也就必须整除 $b$。例如 $4x\equiv3\pmod6$ 无解，因为 $\gcd ($，而 ；直观看， 永远是奇数，不可能成为 的倍数。

这个必要条件也足够。若 $d\mid b$，由裴蜀等式找到 $au+mv=d$，两边乘以 $b/d$，就有

$$a\left(u\frac bd\right)+m\left(v\frac bd\right)=b.$$

因此 $x_0=u(b/d)$ 就是一个解。我们证明了：

$$ax\equiv b\pmod m\text{ 有解} \quad\Longleftrightarrow\quad \gcd(a,m)\mid b.$$

有一个解以后，怎样保证一个也不漏

假设已经找到解 $x_0$。另一个整数 $x$ 也是解，当且仅当

$$a(x-x_0)\equiv0\pmod m.$$

用刚才的一般约分规则，这等价于 $x\equiv x_0\pmod{m/d}$。于是全部整数解恰好是：

$$x=x_0+k\frac md,\qquad k\in\mathbb Z.$$

如果要求用模 $m$ 的剩余类表达，我们只需取：

$$x_0,\quad x_0+\frac md,\quad\ldots,\quad x_0+(d-1)\frac md.$$

为什么恰好是 $d$ 类？其中第 $i$ 项与第 $j$ 项同余，等价于 $m\mid(i-j)m/d$，也就是 $d\mid(i-j)$。当 时，这只能发生在 ，所以没有重复。对任意整数 ，又能写成 ，，于是 与 相差 ，所以这 类也没有漏项。

从判断有解到写出全部解

解 $18x\equiv12\pmod{30}$。先求 $d=\gcd(18,30)=6$，且 $6\mid12$，所以有解，预计应有 个模 的解类。

根据整除定义，把系数、右边和模数同时除以 $6$，原方程等价于

$$3x\equiv2\pmod5.$$

$3$ 模 $5$ 的逆元是 $2$，于是 $x\equiv4\pmod5$。全部整数解为 $x=4+5k$，模 的标准代表为：

$$4,9,14,19,24,29.$$

验算任意一个通解：$18(4+5k)-12=60+90k=30(2+3k)$，所以全部成立。若只写 $x\equiv4\pmod{30}$，就会漏掉其余五个解类。

若出现 $d=m$，即 $m\mid a$，也不用硬找模 $1$ 的逆元：当 $m\nmid b$ 时无解；当 $m\mid b$ 时任意整数都是解。此时恰好有 个模 的解类，仍与刚才的计数吻合。

---

大指数不必展开：先平方，再挑选

计算 $3^{100}$ 除以 $7$ 的余数，可以先观察几个小幂：$3^2\equiv2\pmod7$，所以 $3^3\equiv 6\equiv$，进而 。把 代入：

$$3^{100}=(3^6)^{16}3^4 \equiv1^{16}\times4 \equiv4\pmod7.$$

这里缩小指数的依据，是我们已经算出 $3^6\equiv1\pmod7$，不是直接把 $100$ 对 $7$ 取余。不过，遇到新题时未必很快能找出一个有用的周期。有没有不靠猜周期、也不要求底数与模数互质的办法？

有。计算 $3^{45}$ 模 $100$，我们先把 $45$ 拆成 $2$ 的幂：

$$45=32+8+4+1.$$

只要算出 $3^1,3^2,3^4,3^8,3^{16},3^{32}$，再选出需要的四项相乘就够了。后一项总是前一项的平方，每平方一次立刻取余：

因为 $45=32+8+4+1$，选出对应四项，边乘边取余：

$$\begin{aligned} 3^{45}&=3^{32}3^8 3^4 3\\ &\equiv41\times61\times81\times3\pmod{100},\\ 41\times61&=2501\equiv1\pmod{100},\\ 1\times81\times3&=243\equiv43\pmod{100}. \end{aligned}$$

所以 $3^{45}$ 的末两位是 $43$。表中 $3^{16}$ 虽然没有被选来相乘，仍然是算出 $3^{32}$ 所需的中间步骤。

$45$ 的拆分也不必靠目测。依次做带余除法，得到 $45=2\times22+1$、$22=2\times11+0$、$11=2\times5+1$、、、。从最后一个余数往回读，就是二进制的 ，各位置对应 ，其中标成 的位置恰好是 。

这种方法叫作快速幂，也叫反复平方法。每个非负整数都能写成若干个不同的 $2$ 的幂之和：不断除以 $2$、记录余数 $0$ 或 $1$，就得到它的二进制展开。于是一般的 $a^n$ 都能拆成若干个 $a^{2^j}$ 的乘积；每个 由前一项平方得到，而每一步取余都由同余的乘法规则保证正确。

指数为 $n\geq1$ 时，需要的平方次数和额外乘法次数都不会超过它的二进制位数，各自约为 $\log_2 n$ 的量级，远少于逐次乘 $a$ 的 $n-1$ 次。指数为 $0$ 且底数非零时，直接返回余数 ；这里不讨论 。整个过程不要求 ，因为我们始终只用了乘法，没有求逆，也没有约分。

---

留几道题，把条件真正用一遍

练习一：求 $-58$ 模 $9$ 的最小非负余数，并判断 $-58\equiv14\pmod9$ 是否成立。再判断 $\{-4,-3,-2,-1,0,1,2,3,4\}$ 是否是模 的完全剩余系。

显示答案

写成带余除法是 $-58=(-7)\times9+5$，所以余数为 $5$。又有 $14=9+5$，两者余数相同；用差检验也得到 $-58-14=-72=-8\times9$，因此同余成立。

练习二：有人把 $8x\equiv8\pmod{12}$ 约成 $x\equiv1\pmod{12}$。这一步错在哪里？写出正确的全部解。

显示答案

$\gcd(8,12)=4$，约掉 $8$ 时应把模数改成 $12/4=3$。正确结论是 $x\equiv1\pmod3$，全部整数解为 。

练习三：用欧几里得算法求 $11$ 模 $26$ 的逆元，进而解 $11x\equiv7\pmod{26}$。

显示答案

先辗转相除：$26=2\times11+4$，$11=2\times4+3$，$4=3+1$。回代得到：

练习四：分别解 $14x\equiv8\pmod{20}$ 与 $14x\equiv9\pmod{20}$。对有解的方程，列出闭区间 $[-20,20]$ 中的全部整数解。

显示答案

$\gcd(14,20)=2$。第一式右边的 $8$ 被 $2$ 整除，所以有解；第二式右边的 $9$ 不被 $2$ 整除，所以无解。

第一式同时约去系数、右边和模数中的 $2$，得到 $$。由于 ，两边乘以 ，得 。全部解是 ，模 的两个解类为 和 。

练习五：不用任何关于素数模数的定理，求 $7^{200}\bmod11$，再用快速幂求 $2^{13}\bmod15$。

显示答案

逐步计算可得 $7^2\equiv5\pmod{11}$，$7^3\equiv2\pmod{11}$，，。所以 ，于是 。

练习六：证明对任意非负整数 $n$，都有 $7\mid(3^{2n+1}+2^{n+2})$。

显示答案

因为 $3^2=9\equiv2\pmod7$，两边取 $n$ 次幂可得 $3^{2n}\equiv2^n\pmod7$。于是：

---

当一个数需要同时满足几个余数条件

回到前一章的周期问题：每隔 $6$ 分钟发生一次的事件，如果第一次发生在第 $2$ 分钟，此后的时刻就满足 $t\equiv2\pmod6$。另一个事件每隔 $5$ 分钟发生一次，第一次在第 $4$ 分钟，则满足 $t\equiv 4($。

逐个查看 $2,8,14,20,\ldots$，会发现 $14$ 同时满足第二个条件。往后再加 $30=\operatorname{lcm}(6,5)$，两个条件仍成立。不过，当周期变大、条件变多时，逐个试就不太方便了。

我们现在已经会描述余数、在固定模数下运算，以及完整地解一个线性同余方程。下一章就从这里继续：怎样把不同模数下的条件合在一起？素数作模数时，幂又为什么经常回到 $1$？这些问题会把前面学过的素数、裴蜀等式和周期重新接起来。