模运算
“模运算就是钟表算术——绕一整圈之后，你又回到了起点。”
公式
a ≡ b (mod n) ⟺ n | (a − b)怎么读: a 和 b 在模 n 意义下同余，是指它们除以 n 的余数相同——也就是说 n 整除 a−b
- a ≡ b
- — 表示 a 和 b 同余（余数相同）的符号
- mod n
- — 表示以模 n 为标准来度量——比如钟表用的是 12
- n | (a−b)
- — n 整除 a−b（它们的差是 n 的倍数）
引子
在钟表上，9 点过后五小时不是 14 点，而是 2 点。这种「绕回起点」的运算就是模运算。
通俗地说
模运算是每到某个数 n 就绕回 0 重新开始的运算。如果两个数除以 n 的余数相同，就称它们「同余」，记作 a ≡ b (mod n)。这里只关心余数。
直觉
不要把数轴拉成一条直线，而是把它绕成一个有 n 格的圆圈（比如钟面）。数到 n 就绕回 0。在 12 小时制的钟面上，17 点正好落在 5 的位置——所以 17 和 5 在模 12 下同余。再大的数最终都会被折叠成「轮盘上的位置」。
如何构建
关键在于余数。a 除以 n 的余数就是 a「模 n 的值」。加法、减法、乘法都可以直接对余数进行运算，根本不需要用到原来的大数——只需摆弄余数即可：(a+b) mod n 就是两个余数相加后再对 n 取模。
示例
为什么 17 ≡ 5 (mod 12)：17 − 5 = 12 正好是 12 的倍数。在钟面上，17 点就是下午 5 点。同理 25 mod 7 = 4，因为 25 = 3·7 + 4。
常见误区
按照通常的约定，余数不会是负数。例如 −1 mod 5 不是 −1，而是 4（因为 −1 = (−1)·5 + 4）。这就像在钟面上往回拨一小时，落到 11 点的位置。
用在哪里
现代密码学的核心（RSA、椭圆曲线），哈希函数与校验码（ISBN 和信用卡号的校验），星期与日历的计算，随机数生成器，十二平均律的音阶——所有循环性的计算都离不开模运算。
从何而来
高斯在 1801 年的《算术研究》中引入了同余符号 ≡，系统化了数论。这正是这位称数论为「数学皇后」的学者留下的标志性工具。
前置概念
小测验
25 mod 7 是多少？（25 除以 7 的余数）
- 3
- 4✓
- 5
- 11
练习
计算 17 mod 5。
答案: 2
- 17 = 3·5 + 2
- 余数是 2
要点: a mod n 就是 a 除以 n 之后的余数。
计算 (7 + 8) mod 12。
答案: 3
- 7 + 8 = 15
- 15 mod 12 = 3（绕一圈后剩下 3）
要点: 钟表算术——超过 12 就从 0 重新开始。
计算 (4 × 6) mod 5。
答案: 4
- 4 × 6 = 24
- 24 = 4·5 + 4，余数为 4
要点: 乘法同样可以直接对余数进行运算。
如果今天是星期一，100 天后是星期几？（用 mod 7 计算）
答案: 1
- 100 mod 7 = 2（因为 98 = 14·7，余数为 2）
- 星期一 + 2 天 = 星期三
要点: 星期是以 7 为周期的——每过 7 天就回到起点。