前言
本文主要参考了 OI-wiki。
如无特殊说明，默认 $p$ 为质数。
如有错误或不足，敬请指出。
前置知识
欧拉函数
欧拉函数，记为 $\varphi$，$\varphi(n)$ 表示所有小于 $n$ 且与 $n$ 互质的数的个数，即 $\varphi(n)=\sum\limits_{i=1}^n\left[\gcd(i,n)=1\right]$。
欧拉函数是积性函数，所以若 $\gcd(a,b)=1$，有 $\varphi(ab)=\varphi(a)\varphi(b)$。
Lemma：$\varphi(p^k)=p^k-p^{k-1}$
证明：简单容斥，$\left[1,p^{k}\right]$ 中与 $p^k$ 互质的仅有 $p^{k-1}$ 个 $p$ 的倍数，减去即可。
Lemma：由唯一分解定理，设 $n=\prod\limits_{i=1}^{s}p_i^{k_i}$，有$$\varphi(n)=n\prod\limits_{i=1}^s(1-\dfrac{1}{p_i})$$
证明：$$\begin{aligned}\varphi(n)&=\prod_{i=1}^s\varphi(p_i^{k_i})\\&=\prod_{i=1}^sp_i^{k_i}-p_i^{k_i-1}\\&=\prod_{i=1}^sp_i^{k_i}(1-p_i^{-1})\\&=\prod_{i=1}^sp_i^{k_i}(1-\frac{1}{p_i})\\&=\prod_{i=1}^sp_i^{k_i}\prod_{i=1}^s(1-\frac{1}{p_i})\\&=n\prod_{i=1}^s(1-\frac{1}{p_i})\end{aligned}$$
该引理与后面的证明无关，只是方便求欧拉函数罢了。
缩系
缩系，即简化剩余系，模 $m$ 的缩系即为 $m$ 的完全剩余系中与 $m$ 互质的数构成的子集。
设 $r_1,r_2,\cdots,r_{\varphi(m)}$ 为模 $m$ 的缩系，$a\in\mathbb{N^+}$ 且 $\gcd(a,m)=1$。
Lemma：$ar_1,ar_2,\cdots,ar_{\varphi(m)}$ 在模 $m$ 意义下互不相同。
证明：$\forall i,j\in\left[1,\varphi(m)\right],i\ne j$
$$ar_i-ar_j\equiv a(r_i-r_j)\pmod m$$$$\because r_i\not\equiv r_j\pmod m$$$$\therefore a(r_i-r_j)\not\equiv0\pmod m$$$$\therefore ar_i-ar_j\not\equiv0\pmod m$$$$\therefore ar_i\not\equiv ar_j\pmod m$$
Lemma：$\forall i\in\left[1,\varphi(m)\right],\gcd(ar_i\bmod m,m)=1$
证明：若 $\gcd(ar_i\bmod m,m)\ne1$，设 $ar_i=km+t$，其中 $t Lemma：$ar_1,ar_2,\cdots,ar_{\varphi(m)}$ 为模 $m$ 的缩系。 证明：由上述引理得 $ar_1,ar_2,\cdots,ar_{\varphi(m)}$ 均与 $m$ 互质，仅有 $\varphi(m)$ 种取值，又因 $ar_1,ar_2,\cdots,ar_{\varphi(m)}$ 互不相同，故 $ar_1,ar_2,\cdots,ar_{\varphi(m)}$ 为模 $m$ 的缩系。 欧拉定理 内容 欧拉定理：若 $\gcd(a,m)=1$，有 $a^{\varphi(m)}\equiv1\pmod m$。 证明 设 $r_1,r_2,\cdots,r_{\varphi(m)}$ 为模 $m$ 意义下的缩系。由引理 $1.5$ 得 $ar_1,ar_2,\cdots,ar_{\varphi(m)}$ 也为模 $m$ 的缩系，所以 $\prod\limits_{i=1}^{\varphi(m)}ar_i\equiv\prod\limits_{i=1}^{\varphi(m)}r_i\pmod m$，化简后得 $a^{\varphi(m)}\prod\limits_{i=1}^{\varphi(m)}r_i\equiv\prod\limits_{i=1}^{\varphi(m)}r_i\pmod m$，即 $a^{\varphi(m)}\equiv1\pmod m$。 此处提一下费马小定理。 费马小定理：若 $p\nmid a$，有 $a^{p-1}\equiv1\pmod p$。 实质上是欧拉定理的特殊情况，证明也类似，构造模 $p$ 的完全剩余系即可。 扩展欧拉定理 内容 扩展欧拉定理：$$a^b\equiv \begin{cases}a^{b\mod \varphi(m)}&\gcd(a,m)=1\\a^{b\bmod\varphi(m)+\varphi(m)}&\gcd(a,m)\ne 1,b\ge\varphi(m)\\a^b&\gcd(a,m)\ne 1,b<\varphi(m)\end{cases}\pmod m$$ 证明 对于 $\gcd(a,m)=1$ 的情况，由欧拉定理可证。 讨论 $\gcd(a,m)\ne 1,b\ge\varphi(m)$ 的情况。 令 $m=p^ks$，其中 $p|m,\gcd(p,s)=1$。 由欧拉定理得 $(p^{\varphi(p^k)})^{\varphi(s)}\equiv1\pmod s$，又 $\varphi(m)=\varphi(p^ks)=\varphi(p^k)\varphi(s)$，可得 $p^{\varphi(m)}\equiv 1\pmod s$。 设 $p^{\varphi(m)}=rs+1$，则 $p^{\varphi(m)+k}=p^{\varphi(m)}p^k=(rs+1)\cdot p^k=rm+p^k$，即 $p^{\varphi(m)+k}\equiv p^k\pmod m$。 这个结论 $\forall b\ge \varphi(m)$，有 $p^{b}\equiv p^{b-\varphi(m)}\pmod m$，故 $p^b\equiv p^{b\bmod\varphi(m)+\varphi(m)}\pmod m$。 将 $a$ 每一个质因子乘起来，可得 $a^b\equiv a^{b\bmod \varphi(m)+\varphi(m)}$。 需要注意，当 $b<\varphi(m)$ 时，该结论不一定成立。