模運算

模運算 (modular arithmetic) 只關心除以 $m$ 的餘數:$a\equiv b\pmod m$ 表示 $m\mid(a-b)$。它與加減乘相容——先取餘再運算結果不變,所以算 $7^{100}\bmod 13$ 不必算出 $7^{100}$。

技巧:反覆平方 $a^2, a^4, a^8,\dots$ 每步取餘;找循環節(如 $2^n$ 的個位數以 $2,4,8,6$ 循環);負數餘數要補成 $0$ 到 $m-1$($-7\bmod 5 = 3$)。

算例:$3^{20}\bmod 7$:$3^6\equiv1$,$3^{20} = (3^6)^3\cdot3^2\equiv9\equiv2$。星期幾只看天數 $\bmod 7$;校驗碼(ISBN、身分證)用 $\bmod 10$ 或 $\bmod 11$。

模運算是數論的入口(費馬小定理、中國剩餘定理),也是密碼學(RSA、Diffie–Hellman)、雜湊函數、隨機數產生器的運算基礎。