同余及其性质

同余（Congruence Modulo）是数论中的一种等价关系。给定一个正整数 $m$ ，如果用 $m$ 去除任意两个正整数 $a$ 与 $b$ 所得到的余数相同，我们就称 $a,b$ 对模 $m$ 同余，记为 $a\equiv b\text{ (mod } m)$ ，否则称 $a,b$ 对模 $m$ 不同余，记为 $a\not\equiv b\text{ (mod } m)$ ，其中 $m$ 称作模。

性质1（反身性）： $a\equiv b\text{ (mod } m)$
性质2（对称性）：若 $a\equiv b\text{ (mod } m)$ ，那么 $b\equiv a\text{ (mod } m)$
性质3（传递性）：若 $a\equiv b\text{ (mod } m)$ ，那么 $b\equiv c\text{ (mod } m) \rightarrow a\equiv c\text{ (mod } m)$
性质4（可加减性）：若 $a\equiv b\text{ (mod } m)$ ， $c\equiv d\text{ (mod } m)$ ，那么 $a\pm c \equiv b \pm d\text{ (mod } m)$

证明：设 $a = V_{ab} + K_a*m,\ b= V_{ab} + K_b*m,\ c = V_{cd} + K_c*m,\ d = V_{cd} + K_d*m$ ，则 $(a \pm c)\%m=(A\pm C)$ ， $(b\pm d)\% m=(A\pm C)$ ，即 $a\pm c\equiv b\pm d\text{ (mod } m)$

性质5（可乘性）：若 $a\equiv b\text{ (mod } m)$ ， $c\equiv d\text{ (mod } m)$ ，那么 $ac\equiv bd\text{ (mod } m)$

证明：设 $a = V_{ab} + K_a*m,\ b= V_{ab} + K_b*m,\ c = V_{cd} + K_c*m,\ d = V_{cd} + K_d*m$ ，则 $ac=(V_{ab} + K_a*m)(V_{cd} + K_c*m)$ ， $ac=(V_{ab} + K_b*m)(V_{cd} + K_d*m)$ ，所以 $ac\%m=V_{ab}V_{cd}\% m$ ， $bd\%m=V_{ab}V_{cd}\% m$ ，即 $ac\equiv bd\text{ (mod } m)$

性质6：若 $a\equiv b\text{ (mod } m)$ ，那么 $ka\equiv kb\text{ (mod } m)$
性质7：若 $a\equiv b\text{ (mod } m)$ ， $gcd(c, m) = 1$ ，那么 $\frac{a}{c} \equiv \frac{b}{c}\text{ (mod } m)$
性质8：若 $a\equiv b\text{ (mod } m)$ ，则 $ka\equiv kb\text{ (mod } km)$
性质9：若 $a\equiv b\text{ (mod } m)$ ， $c$ 为 $a,b,m$ 的公因数，则 $\frac{a}{c}\equiv \frac{b}{c}\text{ (mod } \frac{m}{c})$
性质10：若 $a\equiv b\text{ (mod } m_i), i = 1, 2, \cdots, k$ ，则 $a \equiv b \text{ (mod lcm(} m_1, m_2, \cdots, m_k))$
性质11：若 $a\equiv b\text{ (mod } m), c|m,c>0$ ，则 $a\equiv b \text{ (mod } c)$
性质12：若 $a \equiv b \text{ (mod } m)$ ，则 $\gcd(a ,m) = \gcd(g, m)$