同余
定义
若整数 \(a, b\) 除以正整数 \(m\) 的余数相等，则称 \(a, b\) 模 \(m\) 同余，记为 \(a \equiv b (\bmod m)\)。
同余类和剩余系
对于 \(\forall a \in [0, m - 1]\)，集合 \(\{ a + km \}(k \in \mathbb{Z})\) 的所有数模 \(m\) 同余，余数都为 \(a\)，该集合成为一个模 \(m\) 的同余类，记为 \(\overline{a}\)。
模 \(m\) 的同余类共有 \(m\) 个，分别为 \(\overline{0}, \overline{1}, \overline{2}, \dots, \overline{m - 1}\)。它们构成 \(m\) 的 完全剩余系。
\(1 \sim m\) 中与 \(m\) 互质的数代表的同余类共有 \(\varphi(m)\) 个，它们构成 \(m\) 的 简化剩余系。如，模 \(\{ \overline{1}, \overline{3}, \overline{7}, \overline{9} \}\)。
简化剩余系关于模 \(m\) 乘法封闭。这是因为如果 \(a, b(1 \leq a, b \leq m)\) 与 \(m\) 互质，则 \(a \times b\) 也不可能与 \(m\) 含有相同的质因子，即 \(a \times b\) 也与 \(m\) 互质。由余数的定义可得到 \(a \times b \bmod m\) 也与 \(m\) 互质，即 \(a \times b \bmod m\) 也属于 \(m\) 的简化剩余系。
乘法封闭指在一个集合中任意两个元素进行乘法运算，得到的结果还在这个集合中。例如对于集合 \(\mathbb{R}\)，任意两个数的乘积都还在集合内，所以集合 \(\mathbb{R}\) 是乘法封闭的。