##### 同余 - 同余 - **同余**是指两个[[整数]]在[[模运算]]下余数相同的[[等价关系]]. 设 $a,b\in\mathbb{Z}$ 和 $m\in\mathbb{Z}^+$, 如果 $a\bmod m=b\bmod m$, 则称 $a$ 和 $b$ 是模 $m$ 同余, 记作 $a\equiv b\pmod{m}$, 或者说当且仅当存在 $k\in \mathbb{Z}$, 使得 $a=b+km$. 所有和 $a$ 模 $m$ 同余的整数集合称为 $a$ 模 $m$ 的**同余类** $[a]_m$, 即[[等价关系|等价类]], 并且同余在加减乘幂中保持, 而除法须借助[[模逆元]]. 模 $m$ 的全部同余类的代表数的集合称为[[完全剩余系]]. 相关有[[同余方程]], [[二次剩余]], [[乘法阶]], [[原根]]等 - 自反性, $a \equiv a \pmod{m}$ , 任何数与自己同余 - 对称性, 如果 $a \equiv b \pmod{m}$, 则 $b \equiv a \pmod{m}$ - 传递性, 如果 $a \equiv b \pmod{m}$ 且 $b \equiv c \pmod{m}$, 则 $a \equiv c \pmod{m}$ - 加性, 如果 $a \equiv b \pmod{m}$ 和 $c \equiv d \pmod{m}$, 则 $a + c \equiv b + d \pmod{m}$ - 乘性, 如果 $a \equiv b \pmod{m}$ 和 $c \equiv d \pmod{m},$ 则 $a \times c \equiv b \times d \pmod{m}$ - 减性, 如果 $a \equiv b \pmod{m}$ 和 $c \equiv d \pmod{m}$, 则 $a - c \equiv b - d \pmod{m}$ - 幂性, 如果 $a \equiv b \pmod{m}$ 和 $c\in\mathbb{Z}$, 则 $a^c \equiv b^c \pmod{m}$ - [[威尔逊定理]], $\displaystyle (p-1)!\equiv -1\ ({\mbox{mod}}\ p)$ - [[费马小定理]], $a^{p-1} \equiv 1 \pmod p$ - [[欧拉定理]], $a^{\varphi(n)} \equiv 1 \pmod{n}$ >[!example]- 同余 > - $17 \equiv 5 \pmod{12}$ > - 因为 $17−5=12$, 而 $12$ 是 $12$ 的倍数, 所以 $17$ 和 $5$ 在模 $12$ 下是同余的 > - $23 \equiv 7 \pmod{8}$ > - 因为 $23−7=16$, 而 $16$ 是 $8$ 的倍数, 所以 $23$ 和 $7$ 在模 $8$ 下同余