欧拉定理
若 \(\gcd(a,p)=1\)，则
\[
a^{\varphi (p)}\equiv1 \pmod p
\]
其中 \(\varphi(p)\) 为 \(p\) 的欧拉函数，表示 \([1,p]\) 中与 \(p\) 互质的数的个数。
容易发现，当 \(p\) 为质数的时候，\(\varphi(p)=p-1\)，欧拉定理变为费马小定理。这说明，费马小定理是欧拉定理的一般形式。
通过这个定理，我们可以通过以下方式对幂的指数进行取模：
\[
\begin{align*}
a^x \equiv
\begin{cases}
a^{x \bmod \varphi (p)} ,& gcd(a, p) = 1\\\
a^{x},& gcd(a,p)\neq 1 \wedge x< \varphi (p)\\\
a^{(x \bmod \varphi (p)) + \varphi (p)},& gcd(a,p)\neq1 \wedge x\geq \varphi (p)
\end{cases}
\pmod p
\end{align*}
\]