同餘運算

同餘 (congruence) $a\equiv b\pmod m$ 是整數上的等價關係,把 $\mathbb{Z}$ 分成 $m$ 個剩餘類 $\mathbb{Z}_m$。加減乘都與同餘相容,所以可以在 $\{0,\dots,m-1\}$ 裡做算術;除法要小心,只有與 $m$ 互質的數才能「除」(乘模反元素)。

算大冪 $a^k\bmod m$ 的策略:找 $a$ 的冪的循環節,或反覆平方;負數先加 $m$ 的倍數變正。數位和技巧:$10\equiv1\pmod 9$,所以一個數與它各位數字和模 9 同餘——這是「棄九法」驗算的原理。

算例:$2^{10} = 1024\equiv1\pmod{11}$,因此 $2^{100} = (2^{10})^{10}\equiv1$;$-17\bmod5 = 3$。

同餘是費馬小定理、歐拉定理、二次剩餘、橢圓曲線密碼的舞台;抽象代數的商群 $\mathbb{Z}/m\mathbb{Z}$ 就是把它形式化。