费马小定理&欧拉定理&扩展欧拉定理

费马小定理

当 $p$ 是质数，且 $a$ 与 $p$ 互质时，有：

$$a^{p-1} \equiv 1 \pmod p$$

因此在模质数的指数问题中，可以把指数对 $p-1$ 取模后再计算。

欧拉定理

当 $a$ 与 $m$ 互质时，有：

$$a^{\varphi(m)} \equiv 1 \pmod m$$

这里 $\varphi(m)$ 表示 $1\sim m$ 中与 $m$ 互质的整数个数。费马小定理可以看作欧拉定理在 $m$ 为质数时的特例。

扩展欧拉定理

当指数 $b$ 很大，且 $a$ 与 $m$ 不一定互质时，常用下面的降幂形式：

$$a^b \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod m \quad (b \ge \varphi(m))$$

如果 $b < \varphi(m)$，直接使用原指数即可。

使用场景

• 模数是质数，并且底数与模数互质：优先用费马小定理。
• 模数不一定是质数，但底数与模数互质：使用欧拉定理。
• 指数特别大，且互质条件不确定：使用扩展欧拉定理。