11 欧拉定理
学习目标
学完这一节，你应该能够：
* 说出欧拉定理的条件和结论；
* 理解“与 nnn 互质的剩余类”是什么；
* 理解为什么把所有互质剩余类乘上 aaa 后只是重新排列；
* 一步一步证明欧拉定理；
* 理解欧拉定理与费马小定理的关系；
* 理解欧拉定理怎样得到一种逆元公式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 欧拉定理
如果：
gcd(a,n)=1\gcd(a,n)=1 gcd(a,n)=1
那么：
aφ(n)≡1(modn)\boxed{a^{\varphi(n)}\equiv1\pmod n} aφ(n)≡1(modn)
这就是欧拉定理。
其中：
φ(n)\varphi(n) φ(n)
表示与 nnn 互质的剩余类数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 先找出所有与 NNN 互质的剩余类
例如：
n=10n=10 n=10
在：
1,2,…,101,2,\dots,10 1,2,…,10
中与 10 互质的是：
1,3,7,91,3,7,9 1,3,7,9
所以：
φ(10)=4\varphi(10)=4 φ(10)=4
一般地，把模 nnn 下所有与 nnn 互质的剩余类代表记成：
r1,r2,…,rφ(n)r_1,r_2,\dots,r_{\varphi(n)} r1 ,r2 ,…,rφ(n)
它们满足：
gcd(ri,n)=1\gcd(r_i,n)=1 gcd(ri ,n)=1
并且任意两个不同的 ri,rjr_i,r_jri ,rj 在模 nnn 下不同余。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 把每一个 RIR_IRI 都乘上 AAA
考虑：
ar1,ar2,…,arφ(n)ar_1,ar_2,\dots,ar_{\varphi(n)} ar1 ,ar2 ,…,arφ(n)
我们想证明：
> 它们模 nnn 后，仍然只是原来这些互质剩余类的一次重新排列。
要证明这一点，需要完成两件事：
1. 每个 ariar_iari 仍然与 nnn 互质；
2. 不同的 ri,rjr_i,r_jri ,rj 乘上 aaa 后不会变成同一个剩余类。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 为什么 ARIAR_IARI 仍然与 NNN 互质
已经知道：
gcd(a,n)=1\gcd(a,n)=1 gcd(a,n)=1
并且：
gcd(ri,n)=1\gcd(r_i,n)=1 gcd(ri ,n)=1
根据裴蜀定理，由：
gcd(a,n)=1\gcd(a,n)=1 gcd(a,n)=1
可知存在整数 u,vu,vu,v，使：
au+nv=1au+nv=1 au+nv=1
两边乘 rir_iri ：
ariu+nriv=riar_i u+nr_i v=r_i ari u+nri v=ri
现在设 *** 是 ariar_iari 与 nnn 的任意公共因子。
那么：
d∣arid\mid ar_i d∣ari
并且：
d∣nd\mid n d∣n
所以：
d∣ariud\mid ar_i u d∣ari u
同时：
d∣nrivd\mid nr_i v d∣nri v
因此：
d∣(ariu+nriv)d\mid(ar_i u+nr_i v) d∣(ari u+nri v)
而：
ariu+nriv=riar_i u+nr_i v=r_i ari u+nri v=ri
所以：
d∣rid\mid r_i d∣ri
现在 *** 同时整除 rir_iri 和 nnn。
但：
gcd(ri,n)=1\gcd(r_i,n)=1 gcd(ri ,n)=1
所以只能：
d=1d=1 d=1
因此：
gcd(ari,n)=1\boxed{\gcd(ar_i,n)=1} gcd(ari ,n)=1
也就是说：
> 每一个 ariar_iari 模 nnn 后仍然属于“与 nnn 互质的剩余类”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 为什么不会出现两个相同的剩余类
假设：
ari≡arj(modn)ar_i\equiv ar_j\pmod n ari ≡arj (modn)
因为：
gcd(a,n)=1\gcd(a,n)=1 gcd(a,n)=1
所以 aaa 在模 nnn 下存在逆元 a−1a^{-1}a−1。
两边同时乘 a−1a^{-1}a−1：
a−1ari≡a−1arj(modn)a^{-1}ar_i\equiv a^{-1}ar_j\pmod n a−1ari ≡a−1arj (modn)
于是：
ri≡rj(modn)r_i\equiv r_j\pmod n ri ≡rj (modn)
但 ri,rjr_i,r_jri ,rj 本来就是不同的剩余类代表。
所以只有在：
i=ji=j i=j
时才可能成立。
因此：
> 乘上 aaa 后，不会有两个不同的互质剩余类变成同一个。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 为什么这就说明只是重新排列
原来一共有：
φ(n)\varphi(n) φ(n)
个与 nnn 互质的剩余类。
乘上 aaa 后：
* 每一个结果仍然与 nnn 互质；
* 这些结果两两不同。
所以我们又得到了 φ(n)\varphi(n)φ(n) 个互不相同的互质剩余类。
而模 nnn 下这样的剩余类总共也只有 φ(n)\varphi(n)φ(n) 个。
因此：
ar1,ar2,…,arφ(n)ar_1,ar_2,\dots,ar_{\varphi(n)} ar1 ,ar2 ,…,arφ(n)
模 nnn 后一定只是：
r1,r2,…,rφ(n)r_1,r_2,\dots,r_{\varphi(n)} r1 ,r2 ,…,rφ(n)
的一次重新排列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 把所有数乘起来
既然两边只是顺序不同，那么乘积同余：
(ar1)(ar2)⋯(arφ(n))≡r1r2⋯rφ(n)(modn)(ar_1)(ar_2)\cdots(ar_{\varphi(n)})\equiv r_1r_2\cdots r_{\varphi(n)}\pmod n (ar1 )(ar2 )⋯(arφ(n) )≡r1 r2 ⋯rφ(n) (modn)
左边有 φ(n)\varphi(n)φ(n) 个因子 aaa，所以：
aφ(n)r1r2⋯rφ(n)≡r1r2⋯rφ(n)(modn)a^{\varphi(n)}r_1r_2\cdots r_{\varphi(n)}\equiv r_1r_2\cdots r_{\varphi(n)}\pmod n aφ(n)r1 r2 ⋯rφ(n) ≡r1 r2 ⋯rφ(n) (modn)
令：
P=r1r2⋯rφ(n)P=r_1r_2\cdots r_{\varphi(n)} P=r1 r2 ⋯rφ(n)
得到：
aφ(n)P≡P(modn)a^{\varphi(n)}P\equiv P\pmod n aφ(n)P≡P(modn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 为什么可以消掉 PPP
每个 rir_iri 都与 nnn 互质，所以每个 rir_iri 在模 nnn 下都存在逆元：
ri−1r_i^{-1} ri−1
也就是说：
riri−1≡1(modn)r_ir_i^{-1}\equiv1\pmod n ri ri−1 ≡1(modn)
把所有这些同余式相乘：
(r1r2⋯rφ(n))(r1−1r2−1⋯rφ(n)−1)≡1(modn)(r_1r_2\cdots r_{\varphi(n)})(r_1^{-1}r_2^{-1}\cdots r_{\varphi(n)}^{-1})\equiv1\pmod n (r1 r2 ⋯rφ(n) )(r1−1 r2−1 ⋯rφ(n)−1 )≡1(modn)
而：
P=r1r2⋯rφ(n)P=r_1r_2\cdots r_{\varphi(n)} P=r1 r2 ⋯rφ(n)
所以：
r1−1r2−1⋯rφ(n)−1r_1^{-1}r_2^{-1}\cdots r_{\varphi(n)}^{-1} r1−1 r2−1 ⋯rφ(n)−1
就是 PPP 在模 nnn 下的一个逆元。
因此 PPP 可以在模 nnn 下消去。
从：
aφ(n)P≡P(modn)a^{\varphi(n)}P\equiv P\pmod n aφ(n)P≡P(modn)
两边同时乘 P−1P^{-1}P−1：
aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n aφ(n)≡1(modn)
所以：
aφ(n)≡1(modn)\boxed{a^{\varphi(n)}\equiv1\pmod n} aφ(n)≡1(modn)
欧拉定理得证。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 一个具体例子
取：
a=3,n=10a=3,\qquad n=10 a=3,n=10
因为：
gcd(3,10)=1\gcd(3,10)=1 gcd(3,10)=1
并且：
φ(10)=4\varphi(10)=4 φ(10)=4
所以：
34≡1(mod10)3^4\equiv1\pmod{10} 34≡1(mod10)
而：
34=813^4=81 34=81
所以：
81≡1(mod10)81\equiv1\pmod{10} 81≡1(mod10)
正确。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 欧拉定理怎样得到逆元公式
欧拉定理：
aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n aφ(n)≡1(modn)
可以写成：
a⋅aφ(n)−1≡1(modn)a\cdot a^{\varphi(n)-1}\equiv1\pmod n a⋅aφ(n)−1≡1(modn)
根据逆元的定义：
aφ(n)−1a^{\varphi(n)-1} aφ(n)−1
就是 aaa 在模 nnn 下的一个逆元代表。
所以：
a−1≡aφ(n)−1(modn)\boxed{a^{-1}\equiv a^{\varphi(n)-1}\pmod n} a−1≡aφ(n)−1(modn)
前提仍然是：
gcd(a,n)=1\gcd(a,n)=1 gcd(a,n)=1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. 欧拉定理和费马小定理是什么关系
如果 ppp 是素数，那么：
φ(p)=p−1\varphi(p)=p-1 φ(p)=p−1
把 n=pn=pn=p 代入欧拉定理：
aφ(p)≡1(modp)a^{\varphi(p)}\equiv1\pmod p aφ(p)≡1(modp)
得到：
ap−1≡1(modp)a^{p-1}\equiv1\pmod p ap−1≡1(modp)
这正是费马小定理。
所以：
> 费马小定理是欧拉定理在模数为素数时的特殊情况。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12. 小练习
练习 1
为什么欧拉定理要求：
gcd(a,n)=1\gcd(a,n)=1 gcd(a,n)=1
练习 2
已知：
φ(9)=6\varphi(9)=6 φ(9)=6
验证：
26≡1(mod9)2^6\equiv1\pmod9 26≡1(mod9)
练习 3
为什么从：
ari≡arj(modn)ar_i\equiv ar_j\pmod n ari ≡arj (modn)
可以推出：
ri≡rj(modn)r_i\equiv r_j\pmod n ri ≡rj (modn)
练习 4
为什么费马小定理是欧拉定理的特殊情况？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
13. 答案
练习 1
因为证明中需要 aaa 存在逆元，并且需要乘上 aaa 后仍然在互质剩余类之间形成一一对应。
练习 2
26=64=9×7+12^6=64=9\times7+1 26=64=9×7+1
所以：
26≡1(mod9)2^6\equiv1\pmod9 26≡1(mod9)
练习 3
因为 aaa 有逆元。两边同时乘 a−1a^{-1}a−1 即可消去 aaa。
练习 4
因为素数 ppp 满足：
φ(p)=p−1\varphi(p)=p-1 φ(p)=p−1
代入欧拉定理就得到费马小定理。
