INFO

若无特殊说明，本章涉及的变量皆为正整数。

定义

若 $amodm=\phantom{0}$$\phantom{0}bmodm$，则 $a$ 和 $b$ 模 $m$ 同余，记作 $a\equiv b(\mathrm{mod}m)$。

$$a\equiv b\iff a=b+km\iff m\mid (a-b)(\mathrm{mod}m)$$

性质

• 自反性：$a\equiv a(\mathrm{mod}m)$；
• 对称性：$a\equiv b\iff b\equiv a(\mathrm{mod}m)$；
• 传递性：$a\equiv b\wedge b\equiv c\iff a\equiv c(\mathrm{mod}m)$；
• 同加性：$a\equiv b\iff a+\phantom{0}$$\phantom{0}c\equiv b+\phantom{0}$$\phantom{0}c(\mathrm{mod}m)$；
• 同乘性：$a\equiv b\iff ac\equiv bc(\mathrm{mod}m)$；
• 同幂性：$a\equiv b\iff a^n\equiv b^n(\mathrm{mod}m)$。

同余不满足同除性。当 $a\equiv b(\mathrm{mod}m)$ 时不一定有 ${\displaystyle \frac{a}{n}\equiv \frac{b}{n}(\mathrm{mod}m)}$。

同余类

集合 $A$ 是模 $m$ 的同余类，当且仅当：

• $A$ 中的所有元素模 $m$ 都等于同一个值 $a$。

$$A=\{x\mid xmodm=a\}$$

$a$ 称为该同余类的代表元。

模 $m$ 的同余类有 $m$ 个，其代表元分别为 $0,\phantom{0}$$\phantom{0}1,\phantom{0}$$\phantom{0}2,\phantom{0}$$\phantom{0}\cdots ,\phantom{0}$$\phantom{0}m-\phantom{0}$$\phantom{0}1$。

剩余系

集合 $A$ 是模 $m$ 的剩余系，当且仅当：

• $A$ 中的元素模 $m$ 互不相同。

$$\mathrm{\forall }i\ne j,A_i\not\equiv A_j(\mathrm{mod}m)$$

完全剩余系

模 $m$ 的完全剩余系有 $m$ 个元素，是元素最多的剩余系。

简化剩余系

模 $m$ 的简化剩余系有 $\phi (m)$ 个元素，每个元素模 $m$ 后都与 $m$ 互质。

乘法封闭

从模 $m$ 的简化剩余系中任取两个数 $a,\phantom{0}$$\phantom{0}b$，则 $abmodm$ 也在模 $m$ 的简化剩余系中。

证

设 $a,\phantom{0}$$\phantom{0}b$ 属于模 $m$ 的简化剩余系，则 $amodm,\phantom{0}$$\phantom{0}bmodm$ 与 $m$ 互质，$(amodm)(bmodm)$ 也与 $m$ 互质。根据 欧几里得算法 有：

$$\begin{array}{rl}& \gcd ((amodm)(bmodm),m)\\ =& \gcd (m,(amodm)(bmodm)modm)\\ =& \gcd (m,abmodm)=1\end{array}$$

因此 $abmodm$ 与 $m$ 互质，也属于模 $m$ 的简化剩余系。