同余运算

介绍

是一种在数论中的等价关系，当两个整数除以同一个正整数，若得到相同的余数，则两个整数同余。

性质

加法原理

$$(a+b)\ mod\ n=[(a\ mod\ n)+(b\ mod\ n)]\ mod\ n$$

乘法原理

$$ab\ mod \ n=[(a\ mod\ n)(b\ mod\ n)]\ mod\ n$$

传递性

$$a ≡ b\ (mod\ m),b ≡ c\ (mod\ m),可以推出 a≡c\ (mod\ m)$$