模运算

时钟就是日常的模型。给 10 点加上 5 小时，你得到的不是 15，而是 3，因为小时数过了 12 就会绕回来。模运算正是这种计数方式：数一旦到达某个固定值（称为模），就循环回到起点。

在模 n 下运算，意味着我们只关心除以 n 后的余数。两个余数相同的数被当作相等，记作 a ≡ b (mod n)。这些余数可以做加、减、乘，结果保持一致：(a + b) mod n 与 (a 乘以 b) mod n 只取决于 a 与 b 的余数，而与它们本身的大小无关。这让你在计算前能用小数替换巨大的数。

有一种运算很微妙：除法。在模 n 下并不总能做除法，因为并非每个非零余数都有乘法逆元。a 在模 n 下有逆元，当且仅当 a 与 n 互素。所以在模 12 下你能除以 5（因 gcd(5,12)=1），却不能除以 6。这也正是素数模如此宜人的原因 — 那时每个非零余数都可逆。