模運算與同餘

看時鐘就是在做模運算

在 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|丟番圖方程]]何時有整數解。