模 n 同餘

一週裡的兩天，若相隔整數個星期，就給人「相同」的感覺 — 今天和恰好 21 天後的那天，比如說都是星期二。模 n 同餘把這種感覺搬到整數上：把數軸繞成一個大小為 n 的圓後，落在同一點上的兩個數就算同餘。

定義是：a 與 b 模 n 同餘，記作 a ≡ b (mod n)，是指 n 整除差 a − b。等價地，a 與 b 除以 n 後餘數相同。例如 38 ≡ 14 (mod 12)，因為它們的差 24 是 12 的倍數，而且二者除以 12 都餘 2。

同餘的行為像一個規矩的等號。它滿足自反、對稱、傳遞，並且與加法、乘法相容：若 a ≡ b 且 c ≡ d (mod n)，則 a + c ≡ b + d，且 a 乘以 c ≡ b 乘以 d (mod n)。有一個陷阱：不能隨意約去公因子。由 6 ≡ 0 (mod 12) 推不出 3 ≡ 0 (mod 12)；只有當該因子與 n 互質時，約去才安全。