08 费马小定理
学习目标
学完这一节，你应该能够：
* 说出费马小定理的条件和结论；
* 理解为什么把 1,2,…,p−11,2,\dots,p-11,2,…,p−1 全部乘上 aaa 后，只是把这些非零剩余类重新排列；
* 一步一步证明费马小定理；
* 理解为什么费马小定理能够得到素数模下的逆元公式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 费马小定理
设 ppp 是素数，并且：
p∤ap\nmid a p∤a
也就是 aaa 不是 ppp 的倍数。
那么：
ap−1≡1(modp)\boxed{a^{p-1}\equiv1\pmod p} ap−1≡1(modp)
这就是费马小定理。
因为 ppp 是素数且 p∤ap\nmid ap∤a，所以：
gcd(a,p)=1\gcd(a,p)=1 gcd(a,p)=1
因此前面已经知道：
> aaa 在模 ppp 下存在乘法逆元。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 先观察一个例子
取：
p=7,a=3p=7,\qquad a=3 p=7,a=3
模 7 的非零余数是：
1,2,3,4,5,61,2,3,4,5,6 1,2,3,4,5,6
把它们全部乘 3：
3,6,9,12,15,183,6,9,12,15,18 3,6,9,12,15,18
分别模 7：
3,6,2,5,1,43,6,2,5,1,4 3,6,2,5,1,4
可以发现：
3,6,2,5,1,43,6,2,5,1,4 3,6,2,5,1,4
虽然顺序改变了，但仍然恰好是：
1,2,3,4,5,61,2,3,4,5,6 1,2,3,4,5,6
每个出现一次。
证明费马小定理的关键，就是证明这种现象对于任意满足条件的 a,pa,pa,p 都成立。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 为什么乘上 AAA 后不会出现 0
考虑：
a,2a,3a,…,(p−1)aa,2a,3a,\dots,(p-1)a a,2a,3a,…,(p−1)a
假设其中某一项 aiaiai 模 ppp 后等于 0：
ai≡0(modp)ai\equiv0\pmod p ai≡0(modp)
因为：
gcd(a,p)=1\gcd(a,p)=1 gcd(a,p)=1
所以 aaa 在模 ppp 下存在逆元 a−1a^{-1}a−1。
两边同时乘 a−1a^{-1}a−1：
a−1ai≡a−1⋅0(modp)a^{-1}ai\equiv a^{-1}\cdot0\pmod p a−1ai≡a−1⋅0(modp)
得到：
i≡0(modp)i\equiv0\pmod p i≡0(modp)
但是：
1≤i≤p−11\le i\le p-1 1≤i≤p−1
这个范围中没有任何整数模 ppp 等于 0。
产生矛盾。
所以：
> a,2a,…,(p−1)aa,2a,\dots,(p-1)aa,2a,…,(p−1)a 模 ppp 后都不会得到 0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 为什么不会出现两个相同的余数
假设：
ai≡aj(modp)ai\equiv aj\pmod p ai≡aj(modp)
因为 aaa 在模 ppp 下存在逆元，所以两边同时乘 a−1a^{-1}a−1：
a−1ai≡a−1aj(modp)a^{-1}ai\equiv a^{-1}aj\pmod p a−1ai≡a−1aj(modp)
于是：
i≡j(modp)i\equiv j\pmod p i≡j(modp)
但：
1≤i,j≤p−11\le i,j\le p-1 1≤i,j≤p−1
两个都在同一个完整的非零余数范围中。
所以：
i=ji=j i=j
因此：
> 不同的 i,ji,ji,j 不可能在乘上 aaa 后得到相同的模 ppp 余数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 为什么这就说明只是重新排列
一共有：
p−1p-1 p−1
个数：
a,2a,…,(p−1)aa,2a,\dots,(p-1)a a,2a,…,(p−1)a
前面已经证明：
* 它们模 ppp 后都不是 0；
* 它们模 ppp 后两两不同。
而模 ppp 的非零余数总共也只有：
1,2,…,p−11,2,\dots,p-1 1,2,…,p−1
这 p−1p-1p−1 个。
因此：
> 这 p−1p-1p−1 个结果不可能多出别的非零余数，也不可能漏掉某个非零余数。
所以它们恰好只是：
1,2,…,p−11,2,\dots,p-1 1,2,…,p−1
的一次重新排列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 把两边所有数乘起来
既然两边只是顺序不同，那么乘积在模 ppp 下相同：
a⋅2a⋅3a⋯(p−1)a≡1⋅2⋅3⋯(p−1)(modp)a\cdot2a\cdot3a\cdots(p-1)a\equiv1\cdot2\cdot3\cdots(p-1)\pmod p a⋅2a⋅3a⋯(p−1)a≡1⋅2⋅3⋯(p−1)(modp)
左边共有 p−1p-1p−1 个因子 aaa，所以：
a⋅2a⋯(p−1)a=ap−1(p−1)!a\cdot2a\cdots(p-1)a=a^{p-1}(p-1)! a⋅2a⋯(p−1)a=ap−1(p−1)!
右边：
1⋅2⋯(p−1)=(p−1)!1\cdot2\cdots(p-1)=(p-1)! 1⋅2⋯(p−1)=(p−1)!
因此：
ap−1(p−1)!≡(p−1)!(modp)a^{p-1}(p-1)!\equiv(p-1)!\pmod p ap−1(p−1)!≡(p−1)!(modp)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 为什么可以消掉 (P−1)!(P-1)!(P−1)!
这里不能直接使用普通除法。
我们需要先说明：
(p−1)!(p-1)! (p−1)!
在模 ppp 下存在逆元。
对于：
1,2,…,p−11,2,\dots,p-1 1,2,…,p−1
中的任意一个数 iii，都有：
1≤i<p1\le i<p 1≤i<p
因为 ppp 是素数，所以：
gcd(i,p)=1\gcd(i,p)=1 gcd(i,p)=1
因此每个 iii 在模 ppp 下都有逆元 i−1i^{-1}i−1：
ii−1≡1(modp)ii^{-1}\equiv1\pmod p ii−1≡1(modp)
把这些等式全部相乘：
(1⋅2⋯(p−1))(1−1⋅2−1⋯(p−1)−1)≡1(modp)(1\cdot2\cdots(p-1))(1^{-1}\cdot2^{-1}\cdots(p-1)^{-1})\equiv1\pmod p (1⋅2⋯(p−1))(1−1⋅2−1⋯(p−1)−1)≡1(modp)
其中：
1⋅2⋯(p−1)=(p−1)!1\cdot2\cdots(p-1)=(p-1)! 1⋅2⋯(p−1)=(p−1)!
所以：
1−1⋅2−1⋯(p−1)−11^{-1}\cdot2^{-1}\cdots(p-1)^{-1} 1−1⋅2−1⋯(p−1)−1
就是 (p−1)!(p-1)!(p−1)! 的一个逆元。
因此 (p−1)!(p-1)!(p−1)! 确实可以在模 ppp 下消去。
从：
ap−1(p−1)!≡(p−1)!(modp)a^{p-1}(p-1)!\equiv(p-1)!\pmod p ap−1(p−1)!≡(p−1)!(modp)
两边同时乘 ((p−1)!)−1((p-1)!)^{-1}((p−1)!)−1：
ap−1≡1(modp)a^{p-1}\equiv1\pmod p ap−1≡1(modp)
所以：
ap−1≡1(modp)\boxed{a^{p-1}\equiv1\pmod p} ap−1≡1(modp)
费马小定理得证。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 用例子检查
取：
p=7,a=3p=7,\qquad a=3 p=7,a=3
费马小定理告诉我们：
37−1≡1(mod7)3^{7-1}\equiv1\pmod7 37−1≡1(mod7)
也就是：
36≡1(mod7)3^6\equiv1\pmod7 36≡1(mod7)
而：
36=7293^6=729 36=729
并且：
729=7×104+1729=7\times104+1 729=7×104+1
所以：
729≡1(mod7)729\equiv1\pmod7 729≡1(mod7)
与定理一致。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 为什么费马小定理能得到逆元公式
费马小定理：
ap−1≡1(modp)a^{p-1}\equiv1\pmod p ap−1≡1(modp)
因为：
ap−1=a⋅ap−2a^{p-1}=a\cdot a^{p-2} ap−1=a⋅ap−2
所以：
a⋅ap−2≡1(modp)a\cdot a^{p-2}\equiv1\pmod p a⋅ap−2≡1(modp)
而乘法逆元的定义是：
如果：
ax≡1(modp)ax\equiv1\pmod p ax≡1(modp)
那么 xxx 就是 aaa 在模 ppp 下的逆元。
现在：
ap−2a^{p-2} ap−2
正好满足这个条件。
因此：
a−1≡ap−2(modp)\boxed{a^{-1}\equiv a^{p-2}\pmod p} a−1≡ap−2(modp)
使用这个公式的前提是：
* ppp 是素数；
* p∤ap\nmid ap∤a。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 例子：求 3 在模 7 下的逆元
因为 7 是素数，并且：
7∤37\nmid3 7∤3
所以：
3−1≡37−2(mod7)3^{-1}\equiv3^{7-2}\pmod7 3−1≡37−2(mod7)
也就是：
3−1≡35(mod7)3^{-1}\equiv3^5\pmod7 3−1≡35(mod7)
计算：
35=2433^5=243 35=243
而：
243=7×34+5243=7\times34+5 243=7×34+5
所以：
35≡5(mod7)3^5\equiv5\pmod7 35≡5(mod7)
因此：
3−1≡5(mod7)\boxed{3^{-1}\equiv5\pmod7} 3−1≡5(mod7)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. 现在还剩下一个计算问题
公式：
a−1≡ap−2(modp)a^{-1}\equiv a^{p-2}\pmod p a−1≡ap−2(modp)
已经告诉我们逆元可以通过幂来得到。
但是如果 ppp 很大，例如接近 10910^9109，那么指数 p−2p-2p−2 也非常大。
如果真的连续乘 p−2p-2p−2 次，会非常慢。
下一章学习快速幂，把计算：
ap−2 mod pa^{p-2}\bmod p ap−2modp
的乘法次数降到大约：
O(logp)O(\log p) O(logp)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12. 小练习
练习 1
为什么费马小定理要求：
p∤ap\nmid a p∤a
练习 2
当 p=5,a=2p=5,a=2p=5,a=2 时，验证费马小定理。
练习 3
为什么证明中不能直接从：
ap−1(p−1)!≡(p−1)!(modp)a^{p-1}(p-1)!\equiv(p-1)!\pmod p ap−1(p−1)!≡(p−1)!(modp)
说“把 (p−1)!(p-1)!(p−1)! 约掉”？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
13. 答案
练习 1
因为需要：
gcd(a,p)=1\gcd(a,p)=1 gcd(a,p)=1
这样 aaa 才存在逆元，乘上 aaa 后才能在非零剩余类之间形成一一对应。
练习 2
24=16≡1(mod5)2^4=16\equiv1\pmod5 24=16≡1(mod5)
练习 3
因为模运算中的约分不是无条件成立的。必须先确认被消去的因子与模数互质，也就是它存在逆元。
