扩展欧拉定理

欧拉定理 $$a^{\phi(n)} \equiv 1 \pmod n,(a,n)=1$$
进而有 $$a^b \equiv a^{b \bmod \phi(n)} \pmod n,(a,n)=1$$
那么对于a和n不互质 我们有扩展欧拉定理
$$a^b\equiv a^{b\bmod \phi(n)+\phi(n)} \pmod n,(a,n)\ne 1 \text{且} b\ge \phi(n)$$
注意 $$b<\phi(n)$$的时候是不成立的 比如$$2^2\bmod 8 \ne 2^{2+4}\bmod 8$$