模 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 互素时，约去才安全。