模运算——钟表数学、mod 与同余

模运算是指：相对于一个固定的正整数（称为模数）做除法后，只关注余数。如果两个数除以这个模数得到的余数相同，那么它们在这个模系统中的作用就相同，这也是为什么很多人把它叫作“钟表数学”。

在 $12$ 小时制的钟表上，$13$ 点会落在 $1$ 点的位置，$29$ 小时后也会落在和 $5$ 小时后相同的位置。这种不断循环重复的现象，就是理解模运算最直观的方式。

模运算里的 Mod 是什么意思

对于整数 $a$ 和正整数 $n$，表达式 $a \bmod n$ 表示 $a$ 除以 $n$ 后的余数。

例如：

$$29 \bmod 12 = 5$$

因为

$$29 = 12 \cdot 2 + 5$$

这里的模数是 $12$，所以加上或减去 $12$，都不会改变它在这个循环中的落点。

模 $n$ 同余是什么意思

同余是正式表达“两个整数在模 $n$ 意义下表现相同”的方式。

$$a \equiv b \pmod n$$

表示 $a$ 和 $b$ 除以 $n$ 时余数相同。一个等价的判断方法是

$$n \mid (a-b)$$

意思是“$n$ 整除 $a-b$”。

所以

$$29 \equiv 5 \pmod{12}$$

因为 $29 - 5 = 24$，而且 $12$ 整除 $24$。

这个区别很重要：

• $29 \bmod 12 = 5$ 是关于余数的陈述。
• $29 \equiv 5 \pmod{12}$ 是关于同余的陈述。

它们彼此相关，但不能互换使用。

例题：8 点过后 $29$ 小时是几点

假设现在是 $8$ 点，你想知道在 $12$ 小时制钟表上，$29$ 小时后是几点。

先把 $29$ 对 $12$ 取模：

$$29 \bmod 12 = 5$$

所以加上 $29$ 小时，和加上 $5$ 小时的效果相同：

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

于是

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

所以钟表上显示的是 $1$ 点。

关键步骤就是先化简。在模 $12$ 下，把 $29$ 换成 $5$，答案不会变，而且计算会更容易。

为什么先化简会让题目更容易

大数通常可以先换成一个更小、但与它同余的数，这样更容易处理。

例如，在模 $7$ 下，

$$100 \equiv 2 \pmod 7$$

因为 $100 - 2 = 98$ 能被 $7$ 整除。如果题目只关心模 $7$ 的结果，那么你可以用 $2$ 代替 $100$ 来计算。

常见错误

把相等和同余混为一谈

$29 \equiv 5 \pmod{12}$ 并不表示 $29 = 5$。它表示它们在模 $12$ 下属于同一个余数类。

忘记模数会影响结果

$17 \equiv 5 \pmod{12}$ 是真的，但 $17 \equiv 5 \pmod{10}$ 是假的。同余总是相对于某个特定模数而言的。

把 mod 当成普通除法

$29 \bmod 12$ 的结果是余数 $5$，不是商 $2$，也不是分数 $29/12$。

以为软件里的 % 总和数学里的约定完全一样

对于正数，编程语言中的 % 往往和学生最先学到的“取余数”含义一致。但遇到负数时，不同语言的约定可能不同，所以结果不一定等于很多数学课程里使用的“最小非负余数”。

模运算用在哪里

只要数值会按周期重复，你就会看到模运算：钟表、星期、校验位系统、哈希，以及数论中的很多内容。

它也出现在密码学中，但核心思想并没有变：数字按余数分组，而同余的数在这个系统内部可以视为等价。

试试类似的问题

如果今天是星期一，那么 $100$ 天后是星期几？因为星期按模 $7$ 循环，所以先把 $100$ 对 $7$ 取模，再作答。

如果你想再比较一个例子，可以在 GPAI Solver 里试试你自己的版本，看看先化简是否会让计算更短。