数论中的一些简单的常用定理
费马小定理
内容
若$p$是质数， 则对于任意正整数$a$， 有$a^p \equiv a (mod \ p)$
推论
如果$p$是质数， 那么对于$a < b$， $a$在$mod \ p$意义下的逆元$a^{-1} = a^{p - 2} \ (mod \ p)$
欧拉定理
内容
若正整数$a, n$互质， 则$a^{\phi(n)} \equiv 1 \ (mod \ n)$， 其中$\phi(n)$为欧拉函数
推论
若正整数$a, n$互质， 则对于任意正整数$b$， 有$ a^b \equiv a^{b \ mod \ \phi(n)} \ (mod \ n)$
贝祖定理
内容
对于任意正整数$a, b$， 存在一对整数$x, y$， 满足$ax + by = gcd(a, b)$
应用
拓展欧几里得算法
中国剩余定理
内容
设$m_1, m_2, \cdots, m_n$是两两互质的整数， $m = \Pi_{i = 1}^n m_i, M_i = m / m_i, t_i$是线性同余方程$M_i t_i \equiv 1 (mod \ m_i)$的一个解。 对于任意的$n$个整数$a_1, a_2, \cdots, a_n$， 方程组
$\left\{\begin{aligned}
&x \equiv a_1 (mod \ m_1) \\ &x \equiv a_2 (mod \ m_2) \\ & \vdots \\ &x \equiv a_n (mod \ m_n)\end{aligned}
\right.$
有整数解， 解为$x = \sum_{i = 1}^n a_i M_i t_i$
容斥原理
内容
设$S_1, S_2, \cdots, S_n$为有限集合, $|S|$表示集合$S$的大小， 则：