费马小定理

概述

费马小定理（Fermat’s Little Theorem）：若 $p$ 是素数且 $\gcd (a,p)=1$，则 $a^{p-1}\equiv 1(\mathrm{mod}p)$。等价形式：对任意整数 $a$，$a^p\equiv a(\mathrm{mod}p)$。

定理陈述

形式化陈述

定理（费马小定理）： 设 $p$ 为素数，$a\in \mathbb{Z}$。

• 形式一：若 $\gcd (a,p)=1$，则 $a^{p-1}\equiv 1(\mathrm{mod}p)$。
• 形式二（对任意整数 $a$）：$a^p\equiv a(\mathrm{mod}p)$。

两种形式等价：当 $p\mid a$ 时，$a^p\equiv 0\equiv a(\mathrm{mod}p)$ 自然成立；当 $p\nmid a$ 时，$\gcd (a,p)=1$，形式一推出形式二。

证明概要

证明思路（群论方法）

核心思想

利用模 $p$ 乘法群的群结构，通过 Lagrange 定理 直接得出结论。这是最优雅的证明路径。

详细步骤

第一步：构造模 $p$ 乘法群

定义 ${\mathbb{Z}}_p^{\ast }=\{1,2,3,\dots ,p-1\}$，即模 $p$ 的非零剩余类构成的集合。在模 $p$ 乘法下：

• 封闭性：若 $a,b\in {\mathbb{Z}}_p^{\ast }$，则 $ab\not\equiv 0(\mathrm{mod}p)$（因为 $p$ 是素数），故 $ab\in {\mathbb{Z}}_p^{\ast }$。
• 结合律：整数乘法的结合律自然继承。
• 单位元：$1$ 是单位元。
• 逆元存在：对任意 $a\in {\mathbb{Z}}_p^{\ast }$，因为 $\gcd (a,p)=1$，由 模逆元 的存在性，存在 $a^{-1}\in {\mathbb{Z}}_p^{\ast }$ 使得 $a\cdot a^{-1}\equiv 1(\mathrm{mod}p)$。

因此 ${\mathbb{Z}}_p^{\ast }$ 构成一个有限群，其阶（元素个数）为 $|{\mathbb{Z}}_p^{\ast }|=p-1$。

第二步：应用 Lagrange 定理

Lagrange 定理指出：有限群 $G$ 中任意元素 $g$ 的阶 $|g|$ 整除群 $G$ 的阶 $|G|$。

取 $g=a\in {\mathbb{Z}}_p^{\ast }$，则 $a$ 的阶 $|a|$ 整除 $|{\mathbb{Z}}_p^{\ast }|=p-1$。

即存在正整数 $k$ 使得 $|a|\cdot k=p-1$。

第三步：得出结论

由元素阶的定义，$a^{|a|}\equiv 1(\mathrm{mod}p)$，因此：

$a^{p-1}=a^{|a|\cdot k}=(a^{|a|}{)}^k\equiv 1^k\equiv 1(\mathrm{mod}p)$

证毕。$■$

其他证明方法

组合方法：考虑 $\{a,2a,3a,\dots ,(p-1)a\}$ 模 $p$ 的剩余。因为 $\gcd (a,p)=1$，这 $p-1$ 个数模 $p$ 恰好是 $\{1,2,\dots ,p-1\}$ 的一个排列。两边取乘积：

$a\cdot 2a\cdot 3a\cdots (p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1)(\mathrm{mod}p)$

$a^{p-1}\cdot (p-1)!\equiv (p-1)!(\mathrm{mod}p)$

因为 $(p-1)!\not\equiv 0(\mathrm{mod}p)$，两边消去得 $a^{p-1}\equiv 1(\mathrm{mod}p)$。

关键推论

• 推论1（逆元公式）：若 $p$ 为素数且 $\gcd (a,p)=1$，则 $a$ 模 $p$ 的逆元为 $a^{p-2}(\mathrm{mod}p)$。这是 快速幂 计算模逆元的理论基础。
• 推论2（素性检验）：若存在 $a$ 使得 $a^{p-1}\not\equiv 1(\mathrm{mod}p)$，则 $p$ 不是素数。这是 Fermat 素性检验 的核心原理（注意其逆命题不成立，存在 Carmichael 数）。
• 推论3（欧拉定理特例）：费马小定理是 欧拉定理 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$ 在 $n=p$ 为素数时的特例，因为 $\phi (p)=p-1$。

应用场景

1. RSA 密码系统：在 RSA 中，费马小定理保证了加密/解密运算的正确性。具体地，$m^{ed}\equiv m(\mathrm{mod}pq)$ 的证明依赖于费马小定理分别对模 $p$ 和模 $q$ 的应用。
2. 模逆元的高效计算：利用 $a^{-1}\equiv a^{p-2}(\mathrm{mod}p)$，可通过快速幂算法在 $O(\log p)$ 时间内计算模逆元，避免使用扩展欧几里得算法。
3. 离散对数问题：费马小定理限制了离散对数的取值范围——$a^x\equiv b(\mathrm{mod}p)$ 的解 $x$ 只需在 $\{0,1,\dots ,p-2\}$ 中搜索。
4. 整除性判定：例如验证 $2^{10}-1=1023$ 能被 $11$ 整除：$2^{10}\equiv 1(\mathrm{mod}11)$，故 $11\mid (2^{10}-1)$。

数值示例

验证 $3^6(\mathrm{mod}7)$：

$3^1=3\equiv 3(\mathrm{mod}7)$ $3^2=9\equiv 2(\mathrm{mod}7)$ $3^3=27\equiv 6(\mathrm{mod}7)$ $3^6=(3^3{)}^2\equiv 6^2=36\equiv 1(\mathrm{mod}7)$

确实有 $3^{7-1}\equiv 1(\mathrm{mod}7)$，与定理一致。

参见

• 模运算
• 欧拉函数
• 整除
• 模逆元
• RSA密码系统
• 快速幂
• 原根

参考链接

• Introductory Group Theory and Fermat’s Little Theorem (UChicago)
• Fermat’s Little Theorem - Brilliant