扩展欧拉定理

扩展欧拉定理无需 a,m 互质。

结论

$$
b\ge\varphi(m)\text{时},a^b\equiv a^{\left(b\mod\varphi(m)\right)+\varphi(m)}\pmod m
$$

证明

先取$m$的一个质因数 $p$，令$m=p^r\times s$, $gcd(p,s)=1$

由欧拉定理得 $p^{\varphi(s)}\equiv1\pmod s$由欧拉函数的性质得 $\varphi(m)=\varphi(s)\times\varphi(p^r)$，所以 $p^{\varphi(m)}\equiv1\pmod s$ 。

设 $p^{\varphi(m)}=ks+1$，那么 $p^{\varphi(m)+r}=km+p^r$，所以 $p^{\varphi(m)+r}\equiv p^r\pmod m$ 。

当 $b\ge r$ 时，$p^b\equiv p^{b-r}\times p^r\equiv p^{b-r}\times p^{\varphi(m)+r}$ $\equiv p^{b+\varphi(m)}\pmod m$。

因为 $r\le\varphi(p^r)\le\varphi(m)$，所以当 $b\ge 2\varphi(m)$ 时 $b-\varphi(m)\ge r$，所以 $p^b\equiv p^{b-\varphi(m)}\pmod m$，即 $p^b\equiv p^{(b\mod\varphi(m))+\phi(m)}\pmod m$。

将 $a$ 质因数分解后乘起来，就可以得到 $a^b\equiv a^{(b\mod\varphi(m))+\varphi(m)}\pmod m$.

需要注意的是，$b<\varphi(m)$ 时，$a^b\equiv a^{(b\mod\varphi(m))+\varphi(m)}\pmod m$不一定正确。