直观理解模运算（钟面上的算术，以及余数为何说了算）

现在是九点，航班五小时后起飞。没人会回答“十四点”。你说两点，而且是不假思索说出来的，因为钟面上没有十四这个刻度。时针走到十二就绕回去，重新开始。从你学会看钟那天起，你就一直在做模运算，只是从没见过它的记号。

这就是这个题目的全部内容。挑一个数作为绕回去的地方，把每一圈完整的行程都忘掉，只留下你最后落在哪里。值得为它写一篇文章，是因为“只保留余数”这一个习惯，能解开那些正面硬算看起来不可能的问题：一个七十位数的末位数字、一个巨大的数能不能被 9 整除、一张信用卡号为什么有效或无效，以及一条消息如何被打乱成只有指定的读者才能还原的样子。

这篇文章要给的是那幅图像：余数究竟是什么，为什么你被允许先化简再计算，遇上负数和幂次会发生什么，以及这个题目里唯一一处真正的难关，除法，是从哪里来的。

余数是你停在哪里，不是剩下了什么

标准定义说，$a \bmod n$ 是 $a$ 除以 $n$ 的余数。这话没错，但它也正是这个题目让人觉得像苦工的原因，因为“余数”听起来像是除完之后剩下的零头，一个附带品。

更好的图像：一条圆形跑道，上面有 $n$ 个刻度，编号从 $0$ 到 $n-1$。要求 $a \bmod n$，就从 $0$ 出发，沿跑道走 $a$ 步。你停在哪里，哪里就是答案。在有 5 个刻度的跑道上走 17 步，你会整整绕三圈（15 步），再多走 2 步，于是停在 2 号刻度。因此 $17 \bmod 5 = 2$。完整的圈数是商；你停在哪里就是余数。

这幅图像做到了两件定义做不到的事。它让余数永远落在 $0$ 到 $n-1$ 之间，因为跑道上只有这些刻度。它也解释了为什么两个相差极大的数可以在模 $n$ 下“是同一个”：$2$、$17$、$102$ 和 $5{,}000{,}002$ 在 5 刻度的跑道上全都停在 2 号刻度。它们彼此只差若干圈，而跑道不记圈数。

数学家把这个想法写成同余式：

$$17 \equiv 2 \pmod{5}$$

读作“在 5 跑道上，17 停在 2 停的地方”。那三条横线不是等号，因为 17 和 2 并不相等。它说的是，对于任何只关心跑道位置的问题，这两个数可以互换。精确的说法是：$a \equiv b \pmod{n}$ 意思是 $n$ 整除 $a - b$，而这不过是在说两个数相差整数圈。

加法和乘法只关心你在哪里

下面这个事实让模运算从一件奇趣变成一件工具。如果你打算把两个数相加再取余数，你可以先分别取余数，把余数相加，再化简一次。答案完全一样。减法和乘法也同理。

在跑道上这是显然的。加 17 就是走 17 步，也就是三圈再加 2 步。那三圈把你送回出发点，什么也没改变，所以加 17 的效果和加 2 一模一样。藏在一个数里面的圈数是死重，而且它们在加法里、在乘法里都一直是死重，因为 $n$ 的倍数乘上任何东西仍然是 $n$ 的倍数。

写出来，设 $a = qn + r$，$b = pn + s$：

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

第一个括号里的一切都是圈数。只有 $rs$ 活了下来，所以 $ab \bmod n$ 就是 $rs \bmod n$。余数带着这个问题所需的全部信息。

这就是 Math Zen 算术模块里那条提示要你一步一步化简、而不是把完整数值算出来的原因。假设你要求 $123 \times 456 \bmod 7$。你可以乘出 56,088 再用 7 做长除法。或者你可以注意到 $123 = 119 + 4$，所以 $123 \equiv 4$，而 $456 = 455 + 1$，所以 $456 \equiv 1$，于是答案就是 $4 \times 1 = 4$。两次小小的化简替掉了一次四位数乘法。这个习惯是：如果你只关心一个数的余数，就绝不让它长过 $n$。

负数朝另一个方向走

跑道这幅图像也能对付最容易把人绊倒的那种情形。$-3 \bmod 5$ 是多少？

在 5 刻度的跑道上从 0 往后退 3 步。你经过 4，再经过 3，最后落在 2。所以 $-3 \equiv 2 \pmod{5}$。负数不过是朝另一个方向走，和直观理解负数里是同一个想法，而余数仍然是你停在哪里，仍然在 $0$ 和 $n-1$ 之间。

捷径：不断加圈，直到这个数变成正的。$-3 + 5 = 2$。对 $-14 \bmod 5$，加上 15（三圈）得到 1。计算器和编程语言对负数余数的处理并不一致，有些会把 $-14 \bmod 5$ 返回成 $-4$，所以考试时一律把答案写成跑道上那个非负的刻度，并且在相信自己的计算器之前先确认它的约定。

减法也是同一个故事。$3 - 8 \pmod{5}$ 是 $-5$，正好是往后退一整圈，所以答案是 0。或者先化简：$8 \equiv 3$，于是 $3 - 3 = 0$。

一个巨大幂次的末位数字

这就是那个让人相信这个题目值得一学的问题，而它是“先化简”这条规则的直接结果。

一个数的末位数字就是这个数模 10，因为十位、百位以及更高的每一位都是 10 的倍数，在 10 刻度的跑道上都落回 0。所以“$7^{100}$ 的末位数字是多少”这个问题，就是“$7^{100} \bmod 10$ 是多少”，而你根本不必算出 $7^{100}$。

取而代之，看着 7 的各次幂在 10 跑道上走，每走一步都化简：

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

一旦撞上 1，循环就重新开始：7、9、3、1、7、9、3、1，周期是 4。既然 $100 = 4 \times 25$，第一百次幂正好坐在一个完整循环的末尾，和 $7^4$ 同一个位置，所以它的末位数字是 1。

每一个底数在模 10 下都有一个循环，而且大多数都很短。2 的各次幂循环走 2、4、8、6。3 的各次幂走 3、9、7、1。5 和 6 的各次幂从不移动。方法永远一样：边化简边找出循环长度，用循环长度去除指数，这次除法的余数就告诉你你处在循环的哪个位置。这就是指数那个反复相乘的想法，只是跑在圆形跑道上而不是一条直线上。

数字和判 9 整除为什么成立

每个人都学过，一个数的各位数字加起来是 9 的倍数，这个数就能被 9 整除，而几乎没人学过为什么。模运算把它变成一行话的论证。

在 9 跑道上，十是一圈再加一：$10 \equiv 1 \pmod{9}$。于是 $100 = 10 \times 10 \equiv 1 \times 1 = 1$，10 的每一次幂也同样同余于 1。所以像 $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ 这样的数，同余于 $4 + 5 + 2 + 7 = 18 \pmod{9}$，而 18 在 9 跑道上就是 $0$，所以 4,527 能被 9 整除。数字和不是什么戏法。它就是这个数本身，在模 9 下看到的样子。

判 3 整除的法则出于同样的理由成立，因为 $10 \equiv 1 \pmod{3}$ 也对。判 11 整除的法则来自 $10 \equiv -1 \pmod{11}$，它让 10 的各次幂在 $1$ 和 $-1$ 之间交替，于是给出交错数字和。别人要你背下来的所有整除法则，都是同一个事实“把 10 的各次幂化简”，施加在不同的跑道上而已。

校验位：你钱包里的模运算

每一个 ISBN、每一个信用卡号、每一个条形码，末尾都有一位数字，它唯一的职责就是当一个余数。

13 位 ISBN 的最后一位是这样选出来的：让全部十三位数字按 1 和 3 交替的权重加权求和，其结果同余于 $0 \pmod{10}$。只要打错一位数字，这个和就会落到 10 跑道上别的地方，扫码器便会拒收。信用卡用的是 Luhn 算法，一种略微精巧一些的加权方式，它还能抓出大多数相邻两位互换的情形，同样是靠检验一个和模 10。

这些是一个大得多的应用的朴素表亲。现代加密建立在这样一个事实上：把一个数在模一个极大的 $n$ 下取幂很容易，而没有密钥要把这个过程倒回去却不容易。你上面为 $7^{100}$ 做的找循环，就是同一种运算，只是放大到几百位的数上，而边算边化简这条规则，是它根本能被算出来的唯一原因。

除法是跑道变得坎坷的地方

加法、减法和乘法在跑道上的表现，和它们在数轴上完全一样。除法不是，而这正是这个题目落下坏名声的那一处。

在普通数轴上，除以 4 就是乘 $\tfrac{1}{4}$，也就是那个乘上 4 等于 1 的数。在 12 跑道上，有没有哪个刻度乘上 4 会落在 1？把它们全试一遍：$4 \times 1 = 4$，$4 \times 2 = 8$，$4 \times 3 = 12 \equiv 0$，$4 \times 4 = 16 \equiv 4$，然后 4、8、0 这个花样永远重复下去。它从不碰到 1。所以在 12 跑道上，除以 4 这件事并不存在。

原因是 4 和 12 有公因数。从 4 的一个倍数出发，加上或去掉若干圈 12，你手里还是 4 的倍数，所以你永远不可能落在 12 的倍数再往前 1 的位置。换成 5 试试：$5 \times 5 = 25 = 24 + 1 \equiv 1$，所以 5 在 12 跑道上是自己的逆元，除以 5 没有问题。法则是：$a$ 在模 $n$ 下有逆元，恰好当 $a$ 和 $n$ 除 1 以外没有公因数时。

这条法则有一个引人注目的后果。如果 $n$ 是素数，那么 $1$ 到 $n - 1$ 里没有一个数和它有公因数，于是每个非零刻度都有逆元，你可以自由地做除法。素数跑道是四种运算全都能用的跑道，这在很大程度上解释了为什么素数，其供应由素数无穷多所保证，会坐在数论和密码学的正中央。

错误都出在哪里

模运算的零件很少，错误也相应地很具体。

第一种是化简了指数而不是底数。在 $7^{100} \bmod 10$ 里，你可以把 7 模 10 化简（它本来就是），在知道循环长度之后你也可以把指数模循环长度化简，但你不可以把 100 模 10 化简然后去算 $7^0$。指数活在另一条跑道上，那条跑道的大小是循环长度，而把两条跑道混在一起，是这个题目里最常见的一个错误。

第二种是负余数。$-14 \bmod 5$ 是 1，不是 $-4$。跑道上是同一个位置，但只有其中一个是约定的名字，而标准答案要的是那个非负的。

第三种是没检查逆元就做除法。从同余式两边消去一个公因数，只有当这个因数与模数没有公因数时才合法。从 $4 \times 2 \equiv 4 \times 5 \pmod{12}$ 出发，这是对的，因为两边都是 8，但你不能把 4 消掉从而断定 $2 \equiv 5$，那是错的。消去时丢掉的那些圈，必须是原来那条跑道的圈。

第四种是最后忘了化简。在 7 跑道上算出 $rs = 21$ 然后写 21，严格说不算错，但它也不算一个答案。答案是跑道上的一个刻度，而 21 是三圈，所以那个刻度是 0。

Math Zen 能帮上什么

Math Zen 的算术模块为模运算留了专门的一格，而它的进阶顺序是围着“先化简”这个习惯排的，不是围着记号排的。早期的题目只要求算普通余数和小模数下的同余，直到“我落在哪里”变成下意识的反应。中间几格把负数和乘积混进来，那里的要点是在相乘之前把每个因数都化简，并把答案写成非负余数。后面几格是末位数字和循环长度的题，正是竞赛卷和入学考试上会出现的那一类，也是专门惩罚那些想把整个幂次算出来的人的那一类。

由于每次练习都很短，而题目会按间隔重新出现，就像用间隔重复练数学里描述的那样，找循环这一手会变成反射动作，而不是一个你要去查的步骤。多数人并没有一个读一章书就能补上的模运算缺口。他们缺的是一幅从来没有人为他们画出来的图像，也就是那条跑道，以及大约四十次从来没有做过的重复。

核心总结

模运算就是在一条有 $n$ 个刻度的圆形跑道上做算术。余数是你走完 $a$ 步之后停在哪里，完整的圈数被忘掉，而两个数落在同一刻度时就是同余的。因为圈数对和与积都毫无贡献，你可以在相加或相乘之前把每个数都化简成它的余数，而这一个许可把本来不可能的计算，比如 $7^{100}$ 的末位数字，变成了你用手就能描出来的短短循环。整除法则就是 10 的各次幂在模 9、模 3 或模 11 下化简的结果。校验位是用来抓打字错误的余数。除法只有在这个数与跑道没有公因数时才行得通，这也正是素数跑道特殊的原因。

当一道模运算的题卡住时，把跑道画出来。问每一块落在哪里，边算边化简，并且让指数留在它自己的跑道上。答案是 $0$ 和 $n - 1$ 之间的一个刻度，而图像会比公式更早把你送到那里。