费马小定理
定理
若 $p$ 为质数且 $\gcd(a,p)=1$，有 $a^{p-1}\equiv1\pmod p$，即 $a^p\equiv a\pmod p$。
证明
取一质数 $p$ 和整数 $a$ 满足 $\gcd(a,p)=1$，即 $a$ 不为 $p$ 的倍数。
则有： \(\prod\limits_{i=1}^{p-1}i\equiv\prod\limits_{i=1}^{p-1}(a\cdot i)\pmod p\)
证明
因为 $\gcd(i,p)=\gcd(a\cdot i,p)=1$，且 $a\cdot i\bmod p$ 是独一无二的，因此每一个 $i$ 都对应了一个 $a\cdot i$，且 $a\cdot i$ 互不相同。
又因为 $1\leq i\leq p-1,1\leq a\cdot i\bmod p\leq p-1$，因此，对于每一个 $i$ 都存在 $j$ 满足 $i\equiv a\cdot j\pmod p$。
故，原式成立：
$$ \prod_{i=1}^{p-1}i\equiv\prod_{i=1}^{p-1}(a\cdot i)\pmod p $$
令 $f=\prod\limits_{i=1}^{p-1}i$，则：
\[\begin{aligned} f&\equiv\prod\limits_{i=1}^{p-1}(a\cdot i)\\ &\equiv a^{p-1}\prod_{i=1}^{p-1}i\\ &\equiv a^{p-1}\cdot f \end{aligned} \pmod p\]即：$a^{p-1}\equiv1$。
证毕。
应用
求 $\dfrac ab\bmod p$，保证 $p$ 为质数。
这是个好问题。
对于整数 $a$，让其对 $p$ 取模，求 $a\bmod p$，a%p 即可。
但如果要求 $\dfrac ab\bmod p$ 呢？
这似乎就无解了，但是我们转换一下变成：
\[a\times b^{-1}\bmod p\]现在我们再来考虑。
由费马小定理得：$b^{p-1}\equiv 1\pmod p$。
那么 $b^{p-2}\equiv b^{-1}\pmod p$
那么，在模 $p$ 意义下，有 $a\times b^{-1}\bmod p=a\times b^{p-2}\bmod p$。
结合快速幂 $\mathcal O(\log p)$ 计算即可。
注意，此时 $b$ 不能为 $p$ 的倍数。
欧拉定理
定理
若 $\gcd(a,p)=1$，则 $a^{\varphi(p)}\equiv 1\pmod p$。
证明
其实与费马小定理的证明非常相似。
设序列 $\langle r_1,r_2,r_3,\cdots,r_{\varphi(p)}\rangle$ 满足 $r_i=i\bmod p$。
则有：
\[\prod_{i=1}^{\varphi(p)}r_i\equiv\prod_{i=1}^{\varphi(p)}(a\cdot r_i)\pmod p\]即：
\[a^{\varphi(p)}\equiv1\pmod p\]应用
当 $p$ 为素数时，有 $\varphi(p)=p-1$，即费马小定理。
扩展欧几里得算法
详见此处。
