费马小定理
BrightNight
·
·
算法·理论
引言
费马小定理是数论中最基础的结论之一。它描述了整数在模素数下的幂次规律，形式简单但用途广泛，是素性检测、密码学和代数结构的常用工具。本文给出该定理的标准陈述、两种证明路径以及几个典型应用场景。
定理内容
设 p 为素数，a 为整数且 p \nmid a，则
a^{p-1} \equiv 1 \pmod{p}
等价表述为：对任意整数 a，
a^p \equiv a \pmod{p}
后者不要求 a 与 p 互素，因为若 p \mid a 则两边均为 0 \bmod p，等式自然成立。
证明
归纳法证明
固定素数 p，对 a 做归纳。
$$(k+1)^p = \sum_{i=0}^{p} \binom{p}{i}k^i$$
当 $1 \le i \le p-1$ 时，$\binom{p}{i} = \frac{p!}{i!(p-i)!}$ 的分子含因子 $p$，分母不含，故该项被 $p$ 整除。因此模 $p$ 下只保留首尾两项：
$$(k+1)^p \equiv k^p + 1 \pmod{p}$$
代入归纳假设 $k^p \equiv k \pmod{p}$，得到 $(k+1)^p \equiv k+1 \pmod{p}$。归纳完成。## 应用
### 简化模幂计算
计算 $3^{201} \bmod 11$。
由费马小定理，$3^{10} \equiv 1 \pmod{11}$。将指数拆分：
$$3^{201} = 3^{200} \cdot 3 = (3^{10})^{20} \cdot 3 \equiv 1^{20} \cdot 3 = 3 \pmod{11}$$
### 除法求逆
在模 $p$ 运算中，若需要计算 $b^{-1} \bmod p$（即找一个 $x$ 使得 $bx \equiv 1 \pmod{p}$），可直接取 $x = b^{p-2} \bmod p$。这是因为 $b \cdot b^{p-2} = b^{p-1} \equiv 1 \pmod{p}$。
在代码实现中，计算 $b^{p-2} \bmod p$ 时，由于指数 $p-2$ 可能非常大（例如 $p=10^9+7$），直接循环乘法是不可行的。此时需要使用**快速幂**算法，通过二进制拆分将指数降为 $O(\log p)$ 级别。
快速幂的核心思想是：将指数 $e$ 表示为二进制形式，从低位到高位遍历，若当前位为 $1$，则将底数的对应幂次乘入答案；同时每一步将底数平方，以准备下一位。
## 推广
欧拉定理将费马小定理从素数模推广到任意正整数模：若 $\gcd(a,n)=1$，则
$$a^{\varphi(n)} \equiv 1 \pmod{n}$$
其中 $\varphi(n)$ 是欧拉函数。当 $n=p$ 为素数时 $\varphi(p)=p-1$，退化为费马小定理。
另一个相关结论是威尔逊定理：$(p-1)! \equiv -1 \pmod{p}$ 当且仅当 $p$ 为素数。它与费马小定理共享了"模素数下的阶乘性质"这一主题，但计算复杂度更高，不适合做素性检测。
## 小结
费马小定理的核心价值在于把"大指数模运算"降维到"指数取模 $p-1$"。这个想法贯穿了整个公钥密码体系的设计逻辑。掌握它的证明不只是记住一个公式，更重要的是理解模素数剩余系的乘法结构——这是后续学习有限域和椭圆曲线的基础。