扩展欧拉定理

扩展欧拉定理无需 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\)不一定正确。