概念和性质
定义（同余）：
- 给定一个正整数 m，如果用 m 去除两个整数 a 和 b 所得到的余数相同，则称 a 和 b 模 m 同余：$$a \equiv b \pmod{m}$$。否则，称 a 和 b 模 m 不同余，记作 $$a \not\equiv b \pmod{m} $$
定理：
- 整数 a 和整数 b 模 m 同余 $$\Leftrightarrow m | (a - b)$$
定理：
设 $$a_1, a_2, b_1, b_2 \in \mathbb{Z}$$，如果有：$$a_1 \equiv b_1 \pmod{m}, a_2 \equiv b_2 \pmod{m}$$
$$a_1 x + a_2 x \equiv b_1 y + b_2 y \pmod{m}, \text{where }x, y \in \mathbb{Z}$$
$$a_1 a_2 \equiv b_1 b_2 \pmod{m}$$
$$a_1^n \equiv b_1^n \pmod{m}. \text{where }n > 0$$
即在模 m 的数域内，满足加法、乘法和指数律。
定理：
- 设 $$\displaystyle f(t) = \sum_{i = 0}^n a_i t^i\text{ and }g(t) = \sum_{j=0}^{n} b^i t$$ 是两个整系数多项式，满足 $$a_i \equiv b_i \pmod{m}, 0 \le i \le n$$
- 如果有 $$x \equiv y \pmod{m}$$，则 $$f(x) \equiv g(y) \pmod{m}$$
定理：
- 若 $$ac \equiv bc \pmod{m}$$，且 $$gcd(c, m) = d$$，则：$$\displaystyle a \equiv b \pmod{\frac{m}{d}}$$
定理：
若 $$a \equiv b \pmod{m}$$，且有正整数 d 满足 $$d | m$$，则：$$a \equiv b \pmod{d}$$
NOTE：模数化简定理
定理：
若 $$a \equiv b \pmod{m_i}, i = 1, 2, …, n$$，则：$$a \equiv b \pmod{lcm(m_1, m_2, …, m_n)}$$
NOTE：模数合并定理
剩余类和欧拉定理
定义（剩余类）：
设 m 是一个给定的正整数，令 $$C_r$$ 表示所有与整数 r 模 m 同余的整数所组成的集合，则任意这样的 $$C_r$$ 叫做模 m 的一个剩余类，一个剩余类中的任一整数叫做该类的代表元。
或可以用集合的形式来描述剩余类的定义：
$$C_r = {a | a \in \mathbb{Z}, a \equiv r \pmod{m}}$$
定义（完全剩余系）：
- 在模 m 的剩余类 $$C_0, C_1, …, C_{m-1}$$ 中各取一代表元 $$a_i \in C_i, i = 0, 1, …, m-1$$，则此 m 个数组成的集合称为模 m 的一个完全剩余系（又称完系）。
定义（欧拉定理）：