模运算与同余

看时钟就是在做模运算

在 12 小时制的钟面上，9 点之后 5 小时是 2 点，而不是 14 点。我们悄悄“绕了一圈”：14 和 2 除以 12 时余数相同。[[modular-arithmetic|模运算]]把这件事正式化。我们说 a 与 b 关于模 n [[congruence-modulo-n|同余]]，记作 a ≡ b (mod n)，当 a 和 b 除以 n 余数相同时——等价地，当 n 整除 a − b 时。

17 ≡ 5 (mod 12)   because 17 − 5 = 12, and 12 | 12
38 ≡ 2 (mod 12)   because 38 = 12·3 + 2
-1 ≡ 11 (mod 12)  because -1 = 12·(-1) + 11

Every integer is congruent to exactly one of
0, 1, 2, …, 11 modulo 12 — its remainder.

在模 12 下，每个整数都归结为 0–11 这十二个余数之一。

算术在“绕圈”后依然成立

神奇之处在于：同余关系与加法和乘法相容。若 a ≡ b (mod n) 且 c ≡ d (mod n)，则 a + c ≡ b + d (mod n) 且 a·c ≡ b·d (mod n)。因此在计算过程中，你可以随时把数化简为它们的余数——这能让数字保持很小。

Find the last digit of 7^4 — i.e. 7^4 (mod 10).

  7^2 = 49 ≡ 9 (mod 10)
  7^4 = (7^2)^2 ≡ 9^2 = 81 ≡ 1 (mod 10)

So 7^4 ends in 1.  (Indeed 7^4 = 2401.) ✓

We never computed 2401 — we stayed under 100.

每一步都对 10 取模，无需算出整个幂就能求出末位数字。

它出现在哪里

一旦留意，模运算无处不在：一周的星期（模 7）、ISBN 的校验位、每个钟表的指针，以及保护网上银行的公钥密码学。把同样的思想用于余数，还能让我们判定最后一篇指南中的[[diophantine-equation|丢番图方程]]何时有整数解。