数论08_费马小定理

吴老师

2026-08-23 13:31:46

发布于：广东

8阅读

0回复

0点赞

08 费马小定理

学习目标

学完这一节，你应该能够：

说出费马小定理的条件和结论；
理解为什么把 $1,2,\dots,p-1$ 全部乘上 $a$ 后，只是把这些非零剩余类重新排列；
一步一步证明费马小定理；
理解为什么费马小定理能够得到素数模下的逆元公式。

1. 费马小定理

设 $p$ 是素数，并且：

$p\nmid a$

也就是 $a$ 不是 $p$ 的倍数。

那么：

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

这就是费马小定理。

因为 $p$ 是素数且 $p\nmid a$ ，所以：

$\gcd(a,p)=1$

因此前面已经知道：

$a$ 在模 $p$ 下存在乘法逆元。

2. 先观察一个例子

取：

$p=7,\qquad a=3$

模 7 的非零余数是：

$1,2,3,4,5,6$

把它们全部乘 3：

$3,6,9,12,15,18$

分别模 7：

$3,6,2,5,1,4$

可以发现：

$3,6,2,5,1,4$

虽然顺序改变了，但仍然恰好是：

$1,2,3,4,5,6$

每个出现一次。

证明费马小定理的关键，就是证明这种现象对于任意满足条件的 $a,p$ 都成立。

3. 为什么乘上 $a$ 后不会出现 0

考虑：

$a,2a,3a,\dots,(p-1)a$

假设其中某一项 $ai$ 模 $p$ 后等于 0：

$ai\equiv0\pmod p$

因为：

$\gcd(a,p)=1$

所以 $a$ 在模 $p$ 下存在逆元 $a^{-1}$ 。

两边同时乘 $a^{-1}$ ：

$a^{-1}ai\equiv a^{-1}\cdot0\pmod p$

得到：

$i\equiv0\pmod p$

但是：

$1\le i\le p-1$

这个范围中没有任何整数模 $p$ 等于 0。

产生矛盾。

所以：

$a,2a,\dots,(p-1)a$ 模 $p$ 后都不会得到 0。

4. 为什么不会出现两个相同的余数

假设：

$ai\equiv aj\pmod p$

因为 $a$ 在模 $p$ 下存在逆元，所以两边同时乘 $a^{-1}$ ：

$a^{-1}ai\equiv a^{-1}aj\pmod p$

于是：

$i\equiv j\pmod p$

但：

$1\le i,j\le p-1$

两个都在同一个完整的非零余数范围中。

所以：

$i=j$

因此：

不同的 $i,j$ 不可能在乘上 $a$ 后得到相同的模 $p$ 余数。

5. 为什么这就说明只是重新排列

一共有：

$p-1$

个数：

$a,2a,\dots,(p-1)a$

前面已经证明：

它们模 $p$ 后都不是 0；
它们模 $p$ 后两两不同。

而模 $p$ 的非零余数总共也只有：

$1,2,\dots,p-1$

这 $p-1$ 个。

因此：

这 $p-1$ 个结果不可能多出别的非零余数，也不可能漏掉某个非零余数。

所以它们恰好只是：

$1,2,\dots,p-1$

的一次重新排列。

6. 把两边所有数乘起来

既然两边只是顺序不同，那么乘积在模 $p$ 下相同：

$a\cdot2a\cdot3a\cdots(p-1)a\equiv1\cdot2\cdot3\cdots(p-1)\pmod p$

左边共有 $p-1$ 个因子 $a$ ，所以：

$a\cdot2a\cdots(p-1)a=a^{p-1}(p-1)!$

右边：

$1\cdot2\cdots(p-1)=(p-1)!$

因此：

$a^{p-1}(p-1)!\equiv(p-1)!\pmod p$

7. 为什么可以消掉 $(p-1)!$

这里不能直接使用普通除法。

我们需要先说明：

$(p-1)!$

在模 $p$ 下存在逆元。

对于：

$1,2,\dots,p-1$

中的任意一个数 $i$ ，都有：

$1\le i<p$

因为 $p$ 是素数，所以：

$\gcd(i,p)=1$

因此每个 $i$ 在模 $p$ 下都有逆元 $i^{-1}$ ：

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

把这些等式全部相乘：

$(1\cdot2\cdots(p-1))(1^{-1}\cdot2^{-1}\cdots(p-1)^{-1})\equiv1\pmod p$

其中：

$1\cdot2\cdots(p-1)=(p-1)!$

所以：

$1^{-1}\cdot2^{-1}\cdots(p-1)^{-1}$

就是 $(p-1)!$ 的一个逆元。

因此 $(p-1)!$ 确实可以在模 $p$ 下消去。

从：

$a^{p-1}(p-1)!\equiv(p-1)!\pmod p$

两边同时乘 $((p-1)!)^{-1}$ ：

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

所以：

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

费马小定理得证。

8. 用例子检查

取：

$p=7,\qquad a=3$

费马小定理告诉我们：

$3^{7-1}\equiv1\pmod7$

也就是：

$3^6\equiv1\pmod7$

而：

$3^6=729$

并且：

$729=7\times104+1$

所以：

$729\equiv1\pmod7$

与定理一致。

9. 为什么费马小定理能得到逆元公式

费马小定理：

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

因为：

$a^{p-1}=a\cdot a^{p-2}$

所以：

$a\cdot a^{p-2}\equiv1\pmod p$

而乘法逆元的定义是：

如果：

$ax\equiv1\pmod p$

那么 $x$ 就是 $a$ 在模 $p$ 下的逆元。

现在：

$a^{p-2}$

正好满足这个条件。

因此：

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

使用这个公式的前提是：

$p$ 是素数；
$p\nmid a$ 。

10. 例子：求 3 在模 7 下的逆元

因为 7 是素数，并且：

$7\nmid3$

所以：

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

也就是：

$3^{-1}\equiv3^5\pmod7$

计算：

$3^5=243$

而：

$243=7\times34+5$

所以：

$3^5\equiv5\pmod7$

因此：

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

11. 现在还剩下一个计算问题

公式：

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

已经告诉我们逆元可以通过幂来得到。

但是如果 $p$ 很大，例如接近 $10^9$ ，那么指数 $p-2$ 也非常大。

如果真的连续乘 $p-2$ 次，会非常慢。

下一章学习快速幂，把计算：

$a^{p-2}\bmod p$

的乘法次数降到大约：

$O(\log p)$

12. 小练习

练习 1

为什么费马小定理要求：

$p\nmid a$

练习 2

当 $p=5,a=2$ 时，验证费马小定理。

练习 3

为什么证明中不能直接从：

$a^{p-1}(p-1)!\equiv(p-1)!\pmod p$

说“把 $(p-1)!$ 约掉”？

13. 答案

练习 1

因为需要：

$\gcd(a,p)=1$

这样 $a$ 才存在逆元，乘上 $a$ 后才能在非零剩余类之间形成一一对应。

练习 2

$2^4=16\equiv1\pmod5$

练习 3

因为模运算中的约分不是无条件成立的。必须先确认被消去的因子与模数互质，也就是它存在逆元。

有帮助，赞一个

去预览

0/2000

这里空空如也

08 费马小定理

学习目标

1. 费马小定理

2. 先观察一个例子

3. 为什么乘上 aaa 后不会出现 0

4. 为什么不会出现两个相同的余数

5. 为什么这就说明只是重新排列

6. 把两边所有数乘起来

7. 为什么可以消掉 (p−1)!(p-1)!(p−1)!

8. 用例子检查

9. 为什么费马小定理能得到逆元公式

10. 例子：求 3 在模 7 下的逆元

11. 现在还剩下一个计算问题

12. 小练习

练习 1

练习 2

练习 3

13. 答案

练习 1

练习 2

练习 3

热门讨论

3. 为什么乘上 $a$ 后不会出现 0

7. 为什么可以消掉 $(p-1)!$