费马小定理与快速求逆

1. 定理解决什么问题

当模数是质数时，幂运算具有稳定的周期结构。费马小定理（Fermat's Little Theorem）可以用于化简大指数，也可以把求模逆元转化为模幂运算。

---

2. 定理内容与条件

若 $p$ 是质数，且 $p\nmid a$，则

$$a^{p-1}\equiv1\pmod p.$$

条件不能省略：

• 模数 $p$ 必须是质数；
• $a$ 不能被 $p$ 整除，也就是 $a\not\equiv0\pmod p$。

另一个常见等价形式是

$$a^p\equiv a\pmod p,$$

它对任意整数 $a$ 成立。

---

3. 为什么可以用它求逆元

由

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

可得

$$a * a^{p-2}\equiv1\pmod p.$$

根据模逆元定义，

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

这不是普通的指数恒等式，而是在“$p$ 为质数且 $a\not\equiv0$”的条件下成立的模运算结论。

---

4. 完整例子：求 $3^{-1}\pmod7$

因为 7 是质数，且 7 不整除 3，所以

$$3^{-1}\equiv3^{7-2}=3^5\pmod7.$$

计算

$$3^5=243,$$

并取模：

$$243\bmod7=5.$$

因此

$$3^{-1}\equiv5\pmod7.$$

验证：

$$3 * 5=15\equiv1\pmod7.$$

---

5. 快速幂

直接计算 $a^{p-2}$ 可能产生极大的中间整数。二进制快速幂会不断平方，并在每一步取模，把时间复杂度降低到与指数二进制位数成正比。

Python 已提供三参数 pow：

p = 7
a = 3

inverse = pow(a, p - 2, p)
print(inverse)

预期输出：

5

---

6. 与扩展欧几里得算法的区别

两种方法都能求模逆元，但适用范围不同：

方法	适用条件	主要特点
扩展欧几里得算法	$\gcd(a,n)=1$	适用于一般模数
费马小定理	$p$ 为质数且 $a\not\equiv0$	可用快速幂实现

如果模数不是质数，不能直接把指数写成 $n-2$。一般模数需要使用扩展欧几里得算法，或在满足条件时使用欧拉定理。

---

7. 常见误区

忘记检查模数是否为质数

例如模 8 时，不能声称所有非零 $a$ 都满足 $a^7\equiv1\pmod8$。

把结论误写成普通相等

费马小定理给出的是同余关系，不是整数等式：

$$a^{p-1}\equiv1\pmod p,$$

而不是 $a^{p-1}=1$。

---

8. 自测

1. 费马小定理需要哪些条件？
2. 如何用它表示 $a^{-1}\pmod p$？
3. 为什么不能在模 15 下直接使用指数 $15-2$ 求所有逆元？
4. pow(a, p - 2, p) 与先计算巨大整数再取模相比有什么优势？

参考答案

1. $p$ 是质数，且 $p\nmid a$。
2. $a^{-1}\equiv a^{p-2}\pmod p$。
3. 15 不是质数，费马小定理的条件不成立。
4. 快速幂会控制中间结果大小，并只需要对数级数量的平方与乘法。

上一篇：模逆元：模运算中的除法。
下一篇：素域 $\mathbb F_p$。