贡献者： int256
定义 1 同余与剩余
若（整数）$m$ 是（整数）$x$ 减去（整数）$a$ 的一个因子，即 $m | (x-a)$，则称 $x$ 与 $a$ 模1 $m$ 同余，记作
\begin{equation}
x \equiv a \pmod m ~.
\end{equation}
同时，若 $x \equiv a \pmod m$，就 说 $a$ 是作 $x$ 模 $m$ 的一个
剩余（residue）。若还有 $0 \le a < m$，就说 $a$ 是作 $x$ 模 $m$ 的
最小剩余（least residue）。
有时候会忽略整数条件，此时可以说 $\pi \equiv -\pi \pmod{2\pi}$。即只要 $x-a$ 是 $m$ 的整数倍即可。
定义 2 剩余类
在模 $m$ 的前提下，与给定的某个剩余关于 $m$ 同余的所有数将组成一个集合，称为模 $m$ 的一个剩余类（class of residue）。而这剩余类中的每个元素都叫做这个类的一个代表（represent）。
推论 1
显然，$m$ 共有 $m$ 个不同的剩余类，分别有代表
\begin{equation}
0, 1, \dots, (m-1) ~.
\end{equation}
定义 3 完全剩余系
对于模 $m$ 的前提下，将会有 $m$ 个不同的剩余系分别有代表 $0, 1, \dots, (m-1)$。对于任意 $m$ 个分别属于这 $m$ 个不同的剩余系的数，这 $m$ 个数组成的集合都称为模 $m$ 的一个完全剩余系，简称模 $m$ 的一个完系（complete system）。
同余式有一些经典的性质：
- $a \equiv b$ $\Leftrightarrow$ $b \equiv a$；
- $a \equiv b$, $b \equiv c$ $\rightarrow$ $a \equiv c$；
- $a \equiv a'$, $b \equiv b'$ $\rightarrow$ $a + a' \equiv b + b'$。
此外，在令 $a \equiv a', b \equiv b', c \equiv c', \dots$ 的前提下，还有
- $k_a a + k_b b + \cdots \equiv k_a a' + k_b b' + \dots$；
- $a^2 \equiv a'^2$, $a^3 \equiv a'^3$, $\dots$。
以及对于 $\varphi(a, b, \dots)$ 是某整系数多项式，则
$$\varphi(a, b, \dots) \equiv \varphi(a', b', \dots) ~.$$
定理 1
若 $a \equiv b \pmod n$ 且 $a \equiv b \pmod m$，则 $a \equiv b \pmod{[m, n]}$，其中 $[m, n]$ 是 $n$ 与 $m$ 的最小公倍数。
这定理有许多方法证明，这里给出一个证明思路：考虑 $p^c$ 是能整除 $[m, n]$ 的素数 $p$ 的最高次幂，则 $p^c | n$ 或 $p^c | m$，故 $p^c | (a - b)$，这对于 $[m, n]$ 的每个素因子都成立，即可证明。
定义 4 缩系
对于 $m$ 的一个完系，再取出其中所有与 $m$ 互素的元素组成一个新的集合，这就称为与 $m$ 互素的完全剩余系，又称 $m$ 的简化剩余系或简称 $m$ 的缩系。
1. ^ 此处的 “模” 对应英文 $\operatorname{mod}$，与整数模无关。