费马小定理

费马小定理不是“幂碰巧出现周期”，而是有限群中元素反复相乘必然回到单位元的具体表现。模 $p$ 的乘法世界只有 $p-1$ 个非零状态；群结构又禁止轨道在到达 $1$ 之前陷入不可逆的死路，因此每个元素的周期都整除 $p-1$。

定理给出的是一个统一有效的指数，不一定给出最短周期。某个底数的真正周期是它在 ${\mathbb{F}}_p^{\times }$ 中的阶，可以是 $p-1$ 的真因子。只有本原元的阶才恰好等于 $p-1$。

把所有底数同时放进一个多项式，还能得到有限域恒等式

费马小定理说明每个 $c\in {\mathbb{F}}_p$ 都是左侧的根；两边又都是首一的 $p$ 次多项式，因此完全相同。这个形式把逐个整数的同余提升为域上的结构结论：Frobenius 映射 $x\mapsto x^p$ 在素域上就是恒等映射。

取 $p=11$、$a=2$。因为

定理得到验证。但同样在模 $11$ 下，

所以 $3$ 的阶是 $5$，而不是 $10$。这说明 $p-1$ 只是所有非零底数共同适用的周期上界。

当底数被模数整除时，只能使用 $a^p\equiv a(\mathrm{mod}p)$。例如 $a=p=11$ 时，${11}^{10}\equiv 0(\mathrm{mod}11)$，显然不能写成 $1$。错误往往不在幂运算，而在忽略了消去 $a$ 所需的可逆性。

逆命题不成立。合数

满足 $2^{340}\equiv 1(\mathrm{mod}341)$，因为 $2^{10}=1024\equiv 1(\mathrm{mod}341)$。这样的数称为以 $2$ 为底的伪素数。更强的反例是 Carmichael 数；最小的 $561=3\cdot 11\cdot 17$ 对每个与 $561$ 互素的 $a$ 都满足

因此，若一个数通过若干次费马测试，只能说明它没有被这些底数识破，不能据此断言它是素数。

费马小定理可用于约化巨大指数。计算 $3^{2026}(\mathrm{mod}17)$ 时，$3$ 与 $17$ 互素，因此指数可按 $16$ 约化：

再由

得到

这里约化的是乘法群中的指数。若底数与模数不互素，就不能把指数简单地按 $p-1$ 处理。

对 $p\nmid a$，定理立即给出模逆公式

配合二进制快速幂，可以在 $O(\log p)$ 次模乘内计算逆元。例如模 $7$ 下，$3^{-1}\equiv 3^5\equiv 5$，因为 $3\cdot 5\equiv 1(\mathrm{mod}7)$。在需要大量逆元时，还要比较扩展 Euclid、批量递推与预处理等方法；费马公式提供的是一种结构上直接、实现上简洁的选择。

Euler 定理公理库欧拉函数Euler totient function计数不超过 n 且与 n 互素的正整数的算术函数。把结论推广到任意正整数模数：若 $gcd(a,n)=1$，则

当 $n=p$ 为素数时，$\phi (p)=p-1$，费马小定理正是这一一般群论结论的素数模特例。RSA 的正确性证明使用的是这条更一般的指数周期结构，而不是单独依赖素数模公式。

在有限域公理库有限域Finite field · Galois field底层集合有限的域。 ${\mathbb{F}}_q$ 中，相应推广是每个元素都满足 $x^q=x$。多项式 $x^q-x$ 因而恰好以该域全部元素为根。这个恒等式用于构造有限域、描述子域，并分析 Frobenius 自同态的轨道。

费马素性测试从本定理得到必要条件，但伪素数和 Carmichael 数表明该条件不充分。Miller–Rabin 测试进一步利用 $n-1=2^{s}d$ 的平方链结构，能够识别费马测试遗漏的大量合数；它的可靠性来自更强的群结构约束，而不是简单增加底数数量。