贡献者： 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}$，与整数模无关。
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。