扩展欧拉定理

费马小定理

对于素数 $p$，$(a,p)$ 互质，有
$$
a^{p-1}\equiv1\pmod p
$$

欧拉定理

对于 $(a,m)=1$ ，有
$$
a^{\varphi(m)} \equiv 1\pmod m
$$

扩展欧拉定理

不用考虑 $a,m$ 是否互质
$$
a^b=\begin{cases}a^b&b<\varphi(m) \a^{b \bmod \varphi(m)+\varphi(m)}& b\ge \varphi(m)\end{cases}
$$