同余

注意：若无特殊说明，本章涉及的变量皆为正整数.

若 $a \bmod m=b \bmod m$，则 $a$ 和 $b$ 模 $m$ 同余，记作 $a≡b\pmod{m}$.

$$a≡b \ (\bmod \ m)\eq a=b+km\eq m\mid(a-b)$$

• 自反性：$a≡a\pmod{m}$.

• 对称性：$a≡b\pmod{m}\eq b≡a\pmod{m}$.

• 传递性：$\left\{\begin{aligned}a&≡b \ (\bmod \ m)\\b&≡c \ (\bmod \ m)\end{aligned}\right.\eq a≡c\pmod{m}$.

• 同加性：$a≡b\pmod{m}\eq a+c≡b+c\pmod{m}$.

• 同乘性：$a≡b\pmod{m}\eq ac≡bc\pmod{m}$.

• 同幂性：$a≡b\pmod{m}\eq a^n≡b^n\pmod{m}$.

同余不满足同除性. 当 $a≡b \ (\bmod \ m)$ 时不一定有 $\frac{a}{n}≡\frac{b}{n} \ (\bmod \ m)$.

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

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

$$A=\{x\mid x \bmod m=a\}$$

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

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

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

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

$$A_i\not≡A_j \ (\bmod \ m)(i\not=j)$$

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

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

从模 $m$ 的简化剩余系中任取两个数 $a, b$，则 $ab \bmod m$ 也在模 $m$ 的简化剩余系中.

证

设 $a,b$ 属于模 $m$ 的简化剩余系，则 $a \bmod m,b \bmod m$ 与 $m$ 互质，$(a \bmod m)(b \bmod m)$ 也与 $m$ 互质. 根据 欧几里得算法 有：

$$\begin{aligned} &gcd((a \bmod m)(b \bmod m),m)\newline = \ &gcd(m,(a \bmod m)(b \bmod m) \bmod m)\newline = \ &gcd(m,ab \bmod m)=1 \end{aligned}$$

$∴ab \bmod m$ 与 $m$ 互质，也属于模 $m$ 的简化剩余系.