模運算

時鐘就是日常的模型。給 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。這也正是質數模如此宜人的原因 — 那時每個非零餘數都可逆。