一些基本的定义
- 逆元：若 $ax\equiv1\pmod p$ 则称 $x$ 是在模 $p$ 意义下 $a$ 的逆元，记作 $a^{-1}$ 。
- 质因子次数和：$n$ 当中质因子 $p$ 的次数为 $v_p(n)$ 。
##费马小定理
$$a^{p-1}\equiv1\pmod p$$
限制：$p$ 为质数， $a$ 不是 $p$ 的倍数
##求逆元的方法
- 费马小定理：显然，由费马小定理我们可以知道求单个数的逆元的方法。$a^{-1}\equiv a^{p-2}\pmod p$ 。
- 线性求逆元：可以用递推法求得，当求 $i$ 的逆元时，我们已知 $1$ ~ $i-1$ 的逆元。设 $p = ki+r$ 。 $r \equiv -ki\pmod p$ ，两式同除 $ir$ ， $i^{-1}\equiv-kr^{-1}\equiv-\lfloor\frac{p}{i}\rfloor(p\bmod i)^{-1}$ 。
## 威尔迅定理
$(p-1)!\equiv -1\pmod p$