数论中通常有四大定理：威尔逊定理、欧拉定理、中国剩余定理、费马小定理。但威尔逊定理涉及阶乘运算，其数值增长极快，在 OI 领域中应用较少，故本文暂不介绍。中国剩余定理涉及同余方程组的求解，相关内容请参见这篇文章（7.12号发）
::::info[定义]
:::info[同余]
若整数 a 与整数 b 除以正整数 m 的余数相等，则称 a, b 模 m 同余，记为 a \equiv b \pmod m。
:::
:::info[同余类]
对于任意 a \in [0, m - 1]，集合 \{a + km \mid k \in \mathbb{Z}\} 中的所有数模 m 同余，余数均为 a。该集合称为模 m 的一个同余类，简记为 \bar{a}。
:::
:::info[剩余系]
模 m 的同余类共有 m 个，分别为 \bar{0}, \bar{1}, \bar{2}, \dots, \overline{m - 1}。它们构成模 m 的完全剩余系。
:::
::::
---
这一部分内容十分重要，请大家务必深入理解。
## 一、同余
**前置结论：** 若 $n \mid (a - b)$，则 $a \equiv b \pmod n$。
::::success[证明]
设 $a = nk_1 + c$，$b = nk_2 + d$，则
$$
a - b = n(k_1 - k_2) + (c - d)
$$
若 $n \mid (a - b)$，则必须有 $c - d = 0$，即 $c = d$。因此 $a$ 与 $b$ 除以 $n$ 的余数相同，故 $a \equiv b \pmod n$。
证毕。
::::
### 同余的基本性质
#### 1. 自反性
$a \equiv a \pmod n
2. 对称性
若 a \equiv b \pmod n，则 b \equiv a \pmod n
3. 传递性
若 a \equiv b \pmod n，b \equiv c \pmod n，则 a \equiv c \pmod n
::::success[证明]
设 a - b = nk_1，b - c = nk_2，则
a - c = n(k_1 + k_2)
因此 a \equiv c \pmod n。
证毕。
::::
4. 同加性
若 a \equiv b \pmod n，则 a + c \equiv b + c \pmod n
::::success[证明]
设 a - b = nk，则 (a + c) - (b + c) = nk，故 a + c \equiv b + c \pmod n。
证毕。
::::
5. 同乘性
若 a \equiv b \pmod n，则 ac \equiv bc \pmod n
::::success[证明]
设 a - b = nk，则 ac - bc = nkc，故 ac \equiv bc \pmod n。
证毕。
::::
若 a \equiv b \pmod n，c \equiv d \pmod n，则 ac \equiv bd \pmod n
::::success[证明]
设 a - b = nk_1，c - d = nk_2，则
ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) = n(k_1 c + k_2 b)
因此 ac \equiv bd \pmod n。
证毕。
::::
6. 同幂性
若 a \equiv b \pmod n，则 a^k \equiv b^k \pmod n（k 为正整数）
::::success[证明]
在欧几里得算法的最后一步，即 b = 0 时，显然存在 x = 1, y = 0，使得
a \cdot 1 + 0 \cdot 0 = \gcd(a, 0)
若 b > 0，则 \gcd(a, b) = \gcd(b, a \bmod b)。假设存在整数 x, y 满足
b \cdot x + (a \bmod b) \cdot y = \gcd(b, a \bmod b)
因为 a \bmod b = a - b \lfloor a/b \rfloor，代入得
b x + (a - b \lfloor a/b \rfloor)y = a y + b(x - \lfloor a/b \rfloor y)
令 x' = y，y' = x - \lfloor a/b \rfloor y，则
a x' + b y' = \gcd(a, b)
对欧几里得算法的递归过程应用数学归纳法，可知 Bézout 定理成立。
证毕。
::::
Bézout 定理的上述证明同时给出了整数 x 和 y 的计算方法，这种方法称为扩展欧几里得算法。
::::info[代码实现]
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int z = x;
x = y;
y = z - y * (a / b);
return d;
}
::::
扩展欧几里得算法求线性不定方程
对于线性不定方程 ax + by = c，由 Bézout 定理可知，方程存在整数解当且仅当 \gcd(a, b) \mid c。否则方程无整数解。
先用扩展欧几里得算法求得 ax + by = \gcd(a, b) 的一组特解 x_0, y_0，再乘上系数 \dfrac{c}{\gcd(a, b)}，即可得到原方程的一组特解：
\begin{cases}
x = \dfrac{c}{\gcd(a, b)} \cdot x_0 \\[6pt]
y = \dfrac{c}{\gcd(a, b)} \cdot y_0
\end{cases}
原方程的通解为：
x = \frac{c}{\gcd(a, b)}x_0 + k \cdot \frac{b}{\gcd(a, b)},\qquad
y = \frac{c}{\gcd(a, b)}y_0 - k \cdot \frac{a}{\gcd(a, b)} \qquad (k \in \mathbb{Z})
::::info[代码实现]
int line_equation(int a, int b, int c, int &x, int &y) {
int d = exgcd(a, b, x, y);
if (c % d) return 0; // 方程无解
int k = c / d;
x = x * k;
y = y * k; // 求得一组特解，其余解可由通解公式得到
return 1;
}
::::
2. 乘法逆元
若整数 b, m 互质，且 b \mid a，则存在一个整数 x，使得
\frac{a}{b} \equiv a \cdot x \pmod m
称 x 为 b 在模 m 意义下的乘法逆元，记为 b^{-1} \pmod m。
由上式可知：
b \cdot b^{-1} \equiv 1 \pmod m
如果模数 m 是质数（此时常用符号 p 表示），且 b < p，根据费马小定理，b^{p-1} \equiv 1 \pmod p，即 b \cdot b^{p-2} \equiv 1 \pmod p。因此，当模数 p 为质数时，b^{p-2} 即为 b 的乘法逆元。
如果只保证 b 与 m 互质，则乘法逆元可通过求解同余方程 b \cdot x \equiv 1 \pmod m 得到（利用扩展欧几里得算法即可）。下一节我们将正式介绍线性同余方程及其求解方法。
有了乘法逆元，在计数类问题中遇到形如 a / b 的除法算式时，可以先将 a, b 分别对模数 p 取模，再计算 a \cdot b^{-1} \bmod p 作为结果。当然，前提是必须保证 b 与 p 互质（当 p 是质数时，等价于 b 不是 p 的倍数）。
直接计算 a / b \bmod p 时，若 a、b 过大，直接相除可能溢出精度，且除法不满足模运算的分配律。因此可将其转化为乘法逆元来求：a \cdot b^{-1} \bmod p。
::::info[代码实现]
// 利用费马小定理求 b 在模 m 下的逆元：b^(m-2) % m
int quick_pow(int b, int m) {
int r = 1, base = b, exp = m - 2;
while (exp) {
if (exp & 1) r = r * base % m;
base = base * base % m;
exp >>= 1;
}
return r % m;
}
::::
三、数论四大定理（中的两个）
1. 欧拉定理
若正整数 a 与 n 互质，则
a^{\varphi(n)} \equiv 1 \pmod n
::::success[证明]
设 n 的简化剩余系为 \{\overline{a_1}, \overline{a_2}, \dots, \overline{a_{\varphi(n)}}\}。