概念

费马小定理

p 为素数时 a^(p-1) ≡ 1 (mod p)，是素性检验与模逆元计算的快速工具。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

费马小定理初等数论

01定义

若

p

为素数且

p\nmid a

，则

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

。这个一行定理同时是素性检验的探针、模逆元的快速通道（

a^{-1}\equiv a^{p-2}

）与费马大定理的「小号原型」。

模 p 乘法群中幂的周期循环

$(\mathbb{Z}/p\mathbb{Z})^\times$ 是阶 $p-1$ 的群，拉格朗日定理立得每个元素的阶整除 $p-1$ ——抽象代数对初等定理的降维打击。

取随机 $a$ 检验 $a^{n-1}\equiv 1\pmod n$ ：不通过必为合数，通过只是「嫌疑素数」——卡迈克尔数给出反例，催生了 Miller-Rabin 强化。

$a^{-1}\equiv a^{p-2}\pmod p$ ：用快速幂 $O(\log p)$ 求逆——椭圆曲线密码与有限域算术的日常操作。

a^{p}\equiv a\pmod p\quad(\forall a\in\mathbb{Z})

费马 1640 年致弗勒尼克尔信中陈述（未给证明）；莱布尼茨、欧拉先后补上证明；拉格朗日给出群论视角的祖先形式。

Miller-Rabin 素性检验、RSA 与 Diffie-Hellman 的快速幂运算、哈希校验的费马指纹、伪梅森素数搜索的预筛。

费马小定理：a^(p−1) ≡ 1 (mod p)模 p 圆环上连乘 a：序列绕一圈回到 1

p 素数7a 底数3