L02d 费马小定理与欧拉定理:乘够圈数就回到 1
从素数讲起,看清费马小定理、欧拉函数 φ(n) 和欧拉定理各说了什么,再学会用它们把 7 的 134 次方这样的大指数降下来。
一句话版
一个数和模数互素时,拿它反复自乘再取模,乘到一定次数一定会回到 1。模数是素数 p 时,这个次数是 p − 1,叫费马小定理;模数是任意 n 时,这个次数是 φ(n),叫欧拉定理。知道「乘几次回到 1」,再大的指数都能先除掉整圈,只算剩下的零头。
这一页用到 L02a 的取模和 L02b 的互素。RSA 能正确解密,靠的就是这一页的欧拉定理。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 素数 | prime | 只有 1 和自身两个因子的数,如 2、3、5、7 |
| 合数 | composite | 除了 1 和自身还有别的因子,如 4、6 |
| p ∤ a | 读「p 不整除 a」 | a 不是 p 的倍数 |
| φ(n) | 读「phi n」,欧拉函数 | 1 到 n 里和 n 互素的数有几个 |
| 阶 | order | a 自乘多少次第一次回到 1 |
| 原根 | primitive root | 自乘要转满一整圈才回到 1 的数 |
一个类比:在表盘上按乘法走
还是刻了 n 格的表盘,这次换一种走法。从 1 出发,每一步把当前格子的数乘以 a,再折回表盘。
模 19 的表盘上,取 a = 7:1 → 7 → 11 → 1,走三步就回到起点。取 a = 2,要走满 18 步才回来,途中 1 到 18 每一格都踩到了。
不管 a 取哪个,只要 a 和 19 互素,走 18 步一定回到 1。有的数提前回来,回来的步数一定能整除 18。下面这张课件里的表把模 19 下每个 a 的走法都列了出来,最右一列整列都是 1。
类比在哪里失效:
- 表盘只能演示,不能证明。为什么一定会回到 1,要靠第 2 个概念里的证明。
- 模数不是素数时,表盘上有些格子永远走不到,比如和模数不互素的那些格子。这时回到 1 的步数变成 φ(n),不再是 n − 1。
从零讲起
1. 素数与唯一分解
它解决什么问题
后面所有定理都要先问一句:模数是不是素数,能不能拆成素数相乘。φ(n) 的公式也是按素数因子来算的。所以先把素数和分解讲清楚。
直觉
素数是乘法里拆不动的积木。任何大于 1 的整数都能拆成一堆素数相乘,而且不管怎么拆,最后得到的积木种类和块数都一样。
1 不算素数。如果 1 算素数,分解时可以随便乘任意多个 1,「唯一」就不成立了。
一步一步看
目标:把 24 一步步拆成素数,看出不管先拆哪个,最后都是三个 2 和一个 3。
把 24 拆成素数积木。
-
24 是偶数,先拆出一个 2:24 = 2 × 12。
-
12 还是偶数:12 = 2 × 6;6 = 2 × 3。
-
3 是素数,拆不动了。
-
收集起来,得到下表。
素数 出现次数 写法 2 3 次 2³ 3 1 次 3 -
所以 24 = 2³ × 3。换一个顺序拆,比如先拆 3,结果还是三个 2、一个 3。
怎么算
a = p₁^a₁ × p₂^a₂ × … × p_t^a_t,p₁ < p₂ < … < p_t 为素数
意思是:任何大于 1 的整数都能写成若干个素数的幂相乘,并且这种写法只有一种。这条叫算术基本定理。
分解出来以后可以顺手数因子个数:每个指数加 1 再相乘。24 的因子个数是 (3+1) × (1+1) = 8,正好是 1、2、3、4、6、8、12、24。
素数不算稀少。2000 以内有 303 个素数,大约每 6.6 个整数出一个。RSA 要找很大的素数,随机取数再做测试,撞几百次就能撞到一个。反过来,把两个大素数的乘积分解回去却极难,RSA 的安全就压在这个不对称上。
常见误解
以为 1 是素数
1 既不是素数也不是合数。把它算进来,24 也可以写成 1 × 2³ × 3、1 × 1 × 2³ × 3,分解就不唯一了。
以为互素的两个数必须都是素数
互素只看 gcd 是不是 1。8 = 2³ 和 15 = 3 × 5 都是合数,没有共同的素数积木,所以互素。
试一下
把 60 分解成素数幂的乘积,并数出它有几个正因子。
60 = 2² × 3 × 5。因子个数 (2+1) × (1+1) × (1+1) = 12。
91 是素数吗?
不是。91 = 7 × 13。
2. 费马小定理
它解决什么问题
密码学里经常要算 a 的很高次方再取模。费马小定理告诉你:模数是素数 p 时,a 的 p − 1 次方一定余 1。于是指数里所有整圈的 p − 1 都可以直接扔掉。
从哪来(补充)
费马在 1640 年 10 月 18 日写给 Frénicle de Bessy 的信里提出这个结论,没有给证明。欧拉在 1736 年发表了第一个证明。莱布尼茨在 1683 年之前写过几乎相同的证明,但没有发表。
出处:Wikipedia: Fermat’s little theorem
直觉
模 7 下,把 1 到 6 每个数都乘 3 再取模,得到的还是 1 到 6,只是顺序打乱了。两排数各自乘起来,乘积一样。差别只在下排多乘了六个 3,所以这六个 3 乘起来必须等于 1。
一步一步看
目标:在模 19 下用 7 和 2 反复相乘,看出两者回到 1 的步数不同,但走满 18 步都会回到 1。
从 1 出发,在模 19 下每次乘 a,看什么时候回到 1。
-
取 a = 7:1 → 7 → 11 → 1。第 3 步回到 1,所以 7 的阶是 3。
-
取 a = 2:1 → 2 → 4 → 8 → 16 → 13 → …,要走满 18 步才回到 1。
-
3 能整除 18,所以 7 走 18 步也会回到 1:转六个小圈。
-
两个数走到第 18 步都回到 1,这就是 p = 19 时的费马小定理。
怎么算
形式一:p 为素数,p ∤ a ⇒ a^(p−1) ≡ 1 (mod p)
形式二:p 为素数,a 为任意整数 ⇒ a^p ≡ a (mod p)
意思是:a 不是 p 的倍数时,a 自乘 p − 1 次后除以 p 余 1;把这条两边再乘一个 a,就得到形式二,而形式二对 p 的倍数也成立,因为两边都是 0。
证明只有三步,骨架是「乘可逆元不改变集合 → 两边取乘积 → 约掉阶乘」:
- a 与 p 互素,所以 a·1、a·2、…、a·(p−1) 模 p 后互不相同,又都不为 0,正好是 1 到 p − 1 的一个重排。
- 两排各自乘起来相等:a^(p−1) × (p−1)! ≡ (p−1)! (mod p)。
- (p−1)! 的每个因子都小于素数 p,和 p 互素,可以约掉,得 a^(p−1) ≡ 1。
第一步用到 p 是素数:只有这样,1 到 p − 1 才全部和 p 互素。
阶和原根:使 a^k ≡ 1 的最小正整数 k 叫 a 的阶。模 19 下各元素的阶如下,它们都整除 18。
| 阶 | 满足该阶的 a |
|---|---|
| 1 | 1 |
| 2 | 18 |
| 3 | 7, 11 |
| 6 | 8, 12 |
| 9 | 4, 5, 6, 9, 16, 17 |
| 18 | 2, 3, 10, 13, 14, 15 |
阶恰好等于 p − 1 的数叫原根,它的幂能走遍 1 到 p − 1 的每一格。后面讲 Diffie-Hellman 密钥交换和 ElGamal 签名时会用到原根。
费马小定理还能反过来用:如果找到某个 a,使 a^(n−1) 模 n 不等于 1,那么 n 一定不是素数。反过来却不成立,有一类叫 Carmichael 数的合数能骗过这个测试,所以实际用的是 Miller-Rabin 测试。
常见误解
以为一定要用 p − 1 降指数
p − 1 是保证够用的次数,实际的阶可能更小。模 19 下 7 的阶是 3,用 3 降指数比用 18 快得多。
以为形式二也要求 p ∤ a
不需要。a 是 p 的倍数时,a^p 和 a 模 p 都是 0,等式照样成立。只有形式一需要这个条件,因为从形式二推回形式一要约掉一个 a,a 必须可逆。
试一下
不用计算器,求 3⁶ mod 7。
7 是素数,3 不是 7 的倍数,由费马小定理 3⁶ ≡ 1 (mod 7)。直接算也对:3⁶ = 729 = 104 × 7 + 1。
求 2²⁰ mod 11。
11 是素数,2¹⁰ ≡ 1 (mod 11)。20 = 2 × 10,所以 2²⁰ = (2¹⁰)² ≡ 1。
3. 欧拉函数 φ(n)
它解决什么问题
费马小定理只管素数模数。RSA 的模数是两个素数的乘积 n = pq,不是素数。要把费马推广到任意 n,先得知道表盘上有几个格子和 n 互素,这个个数就是 φ(n)。
从哪来(补充)
欧拉在 1763 年引入这个函数。φ 这个记号来自高斯 1801 年的《算术研究》,英文名 totient 是 Sylvester 在 1879 年起的。
出处:Wikipedia: Euler’s totient function
直觉
正面一个个数「和 n 互素的有几个」比较慢。反过来数更快:把和 n 有公因数的划掉,剩下的就是。和 n 有公因数,等于是 n 的某个素因子的倍数。
一步一步看
目标:在 1 到 15 里划掉 3 和 5 的倍数数出 φ(15),再看结果和公式对不对得上。
数 φ(15)。
-
15 = 3 × 5,素因子是 3 和 5。
-
在 1 到 15 里划掉 3 的倍数:3、6、9、12、15,共 5 个。
-
再划掉 5 的倍数:5、10、15,共 3 个。15 被划了两次。
-
一共划掉 5 + 3 − 1 = 7 个,剩下 15 − 7 = 8 个,φ(15) = 8。
-
对照公式:(3 − 1) × (5 − 1) = 2 × 4 = 8,对得上。
怎么算
① p 为素数: φ(p) = p − 1
② n = p^k: φ(n) = p^k − p^(k−1)
③ n = pq,p ≠ q 素数:φ(n) = (p − 1)(q − 1)
④ m、n 互素: φ(mn) = φ(m) × φ(n)
意思是:素数和比它小的每个正整数都互素;素数幂要减掉 p 的倍数;两个不同素数相乘,互素的个数等于各自互素个数相乘;一般地,互素的两个数相乘,φ 也相乘。
算任意 n 的流水线:先分解质因数,对每个素数幂套 ②,再用 ④ 乘起来。比如 36 = 2² × 3²,φ(36) = (4 − 2) × (9 − 3) = 12。
φ(1) = 1。课件的定义写的是「小于 n 且与 n 互素」,照字面 n = 1 时一个都数不出来。标准写法是「不超过 n 且与 n 互素」,这样 φ(1) = 1,n > 1 时两种说法结果相同。
公式 ③ 是 RSA 的核心:知道 p、q 就能马上算出 φ(n),只知道 n 就得先把 n 分解开。
常见误解
把 φ(p²) 套成 (p − 1)²
公式 ③ 要求 p ≠ q。p = q 时要用公式 ②:φ(p²) = p² − p。比如 φ(9) = 9 − 3 = 6,不是 (3 − 1)² = 4。
以为可乘性对任意两个数都成立
必须互素。φ(4) = 2,但 φ(2) × φ(2) = 1。4 = 2 × 2 的两个因子不互素,不能直接相乘。
试一下
求 φ(21)。
21 = 3 × 7,φ(21) = 2 × 6 = 12。
求 φ(50)。
50 = 2 × 5²。φ(2) = 1,φ(25) = 25 − 5 = 20,所以 φ(50) = 1 × 20 = 20。
4. 欧拉定理
它解决什么问题
有了 φ(n),就能把费马小定理推广到任意模数。RSA 解密时要算 (m^e)^d mod n,欧拉定理保证算出来正好回到 m。
直觉
费马的证明里用的是「1 到 p − 1 全部和 p 互素」。换成任意 n,只拿和 n 互素的那 φ(n) 个数来做同样的事:每个乘 a,还是那 φ(n) 个数的重排,两边乘积相等再约掉。结论变成 a 自乘 φ(n) 次回到 1。
一步一步看
目标:把 7¹³⁴ 按 12 个一组打包,看出欧拉定理怎样把巨大的指数缩成只算 7²。
算 7¹³⁴ mod 26。
-
验互素:gcd(7, 26) = 1,可以用欧拉定理。
-
算 φ:26 = 2 × 13,φ(26) = 1 × 12 = 12。所以 7¹² ≡ 1 (mod 26)。
-
把 134 个 7 按 12 个一组打包:134 = 11 × 12 + 2。
-
每组乘起来都是 1,11 组还是 1,只剩 7² = 49。
-
49 − 26 = 23,所以 7¹³⁴ mod 26 = 23。
怎么算
形式一:gcd(a, n) = 1 ⇒ a^φ(n) ≡ 1 (mod n)
形式二:gcd(a, n) = 1 ⇒ a^(φ(n)+1) ≡ a (mod n)
意思是:a 和 n 互素时,a 自乘 φ(n) 次后除以 n 余 1;两边再乘 a 就得到形式二。
n 取素数 p 时 φ(p) = p − 1,形式一立刻变成费马小定理。所以只记欧拉定理就够,费马是它的特例。
降大指数的固定三步:
- 验互素,确认能用定理。
- 算 φ(n),必要时先分解 n。
- 指数除以 φ(n) 取余数,只算 a 的余数次方。
形式二就是 RSA 解密正确的原因。RSA 选的 e 和 d 满足 ed = kφ(n) + 1,于是 (m^e)^d = (m^φ(n))^k × m ≡ m (mod n),加密再解密回到原文。这个推导要求 m 和 n 互素;不互素的消息要用下一页的中国剩余定理另外论证。
常见误解
不验互素就套欧拉定理
a 和 n 不互素时定理不成立。比如 n = 4、a = 2:φ(4) = 2,但 2² = 4 ≡ 0 (mod 4),不是 1。
把指数对 n 取模,而不是对 φ(n) 取模
降指数用的是 φ(n)。7¹³⁴ mod 26 里,134 要除以 12,不是除以 26。
试一下
验证 3⁴ ≡ 1 (mod 10)。
gcd(3, 10) = 1,与 10 互素的是 1、3、7、9,φ(10) = 4。3⁴ = 81 = 8 × 10 + 1。
求 5²² mod 9。
gcd(5, 9) = 1,φ(9) = 9 − 3 = 6。22 = 3 × 6 + 4,所以 5²² ≡ 5⁴ = 625 = 69 × 9 + 4,答案 4。
把它们串起来
素数是拆不动的积木,任何数都能唯一地拆成素数相乘。费马小定理说,模素数 p 时,和 p 互素的 a 自乘 p − 1 次回到 1。欧拉函数 φ(n) 数出任意 n 的表盘上有几个互素格子,欧拉定理把费马推广成「自乘 φ(n) 次回到 1」。
这几条合起来,就是降大指数的工具:验互素,算 φ(n),指数对 φ(n) 取余。
放进 RSA 里看:生成密钥时取两个大素数 p、q,用 φ(pq) = (p − 1)(q − 1) 算出 φ(n);再用 L02c 的扩展欧几里得求出 d;欧拉定理保证解密能还原消息。
下一页 L02e 讲最后一块零件:中国剩余定理,它把一个大模数拆成几个小模数分开算。
课件里的坑
- [口径差异] 课件 p.30 在费马小定理形式二后面也加了「(not divisible by p)」→ 这个限制对形式二是多余的,a^p ≡ a (mod p) 对所有整数 a 都成立,p | a 时两边都 ≡ 0(p.30)
- [口径差异] 课件 p.34 的表里 φ(1) = 1,和同页定义「小于 n 且与 n 互素」在 n = 1 处对不上 → 表里的值是通行约定,该改的是定义,标准写法是「不超过 n」(p.34)
- [适用条件] 课件 p.37 开头写明 a、n 互素,形式二沿用这个前提 → 删掉前提就不成立(n = 4、a = 2 是反例);RSA 里不互素的消息要借 CRT 另证(p.37)
- [课件留白] 课件 p.32 费马小定理的证明页只有标题和定理陈述,正文空着 → 证明是当堂推的,期末闭卷,自己补一份,骨架见本页第 2 个概念(p.32)
- [容易漏看] 课件 p.35 只给了 φ(p) 和 φ(p^k) 两条公式 → 可乘性和 φ(pq) 没写在这一页,但 p.36 算 φ(36)、φ(40) 和 p.49 的证明都离不开它(p.35)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写费马小定理的两种形式和四条 φ 公式;再把课件例题从 p.33 到 p.50 逐道算一遍;最后做变式题,回查最容易错的地方:降指数前忘了验互素。
必背
- 费马小定理 a^(p−1) ≡ 1 (mod p) 要求 p ∤ a;形式二 a^p ≡ a (mod p) 对所有整数 a 成立,不需要 p ∤ a。
- 模 19 的幂表里 a¹⁸ 那一列全是 1;各元素的阶都整除 18,阶恰为 18 的六个数(2, 3, 10, 13, 14, 15)是原根。
- φ(p) = p − 1,φ(p^k) = p^k − p^(k−1),φ(pq) = (p−1)(q−1)(p ≠ q 为素数);可乘性 φ(mn) = φ(m)φ(n) 要求 m、n 互素。
- φ(1) = 1,定义按「不超过 n 且与 n 互素」来读,n > 1 时与「小于 n」结果相同。
- 欧拉定理 gcd(a, n) = 1 ⇒ a^φ(n) ≡ 1 (mod n),n 取素数 p 时退回费马小定理,所以只记欧拉定理即可。
- 大指数降幂三步:验互素 → 算 φ(n) → 指数对 φ(n) 取模;7¹³⁴ mod 26 = 23。
课件例题
例 1(课件 p.28):24 的唯一分解
题面:把 24 写成素数幂的乘积。
提示
反复除以最小的素数 2,除不动了再换 3。
解答
24 = 2³ × 3。可以和 24 的 8 个正因子对上:因子个数 = (3+1) × (1+1) = 8。
例 2(课件 p.33,Exercise-3):用 a = 7、p = 19 验证费马小定理
题面:验证 7¹⁸ ≡ 1 (mod 19)。
提示
可以逐次平方,也可以先算 7³ 模 19 是多少。
解答
逐次平方:7² = 49 ≡ 11;7⁴ ≡ 11² = 121 ≡ 7;7⁸ ≡ 11;7¹⁶ ≡ 7;7¹⁸ = 7¹⁶ × 7² ≡ 7 × 11 = 77 ≡ 1。
更快的办法是先找阶:7³ = 343 = 18 × 19 + 1 ≡ 1,所以 7 的阶是 3。18 = 3 × 6,于是 7¹⁸ = (7³)⁶ ≡ 1。
例 3(课件 p.36,Exercise-4):算 φ(31) 到 φ(40)
题面:写出 n = 31, 32, …, 40 的 φ(n)。
提示
先分解质因数,再对每个素数幂套公式,最后用可乘性乘起来。
解答
| n | 分解 | φ(n) |
|---|---|---|
| 31 | 素数 | 30 |
| 32 | 2⁵ | 32 − 16 = 16 |
| 33 | 3 × 11 | 2 × 10 = 20 |
| 34 | 2 × 17 | 1 × 16 = 16 |
| 35 | 5 × 7 | 4 × 6 = 24 |
| 36 | 2² × 3² | 2 × 6 = 12 |
| 37 | 素数 | 36 |
| 38 | 2 × 19 | 1 × 18 = 18 |
| 39 | 3 × 13 | 2 × 12 = 24 |
| 40 | 2³ × 5 | 4 × 4 = 16 |
例 4(课件 p.38,Exercise-5):用两组数验证欧拉定理
题面:用 (a = 3, n = 10) 和 (a = 2, n = 11) 验证 a^φ(n) ≡ 1 (mod n)。
提示
先验互素,再算 φ(n)。注意第二组的 n 是素数。
解答
第一组:gcd(3, 10) = 1,与 10 互素的是 1, 3, 7, 9,φ(10) = 4。3⁴ = 81 = 8 × 10 + 1 ≡ 1 (mod 10)。
第二组:gcd(2, 11) = 1,11 是素数,φ(11) = 10。2¹⁰ = 1024 = 93 × 11 + 1 ≡ 1 (mod 11)。
两组的用意不同:n = 10 是合数,只能用欧拉定理;n = 11 是素数,欧拉定理和费马小定理给出同一个结论。
例 5(课件 p.49,Exercise-9):证明 φ(pq) = (p−1)(q−1)
题面:p ≠ q 为素数,n = pq,证明 φ(n) = φ(p)φ(q) = (p−1)(q−1)。
提示
反过来数:1 到 pq 里有多少个数和 pq 不互素?
解答
1 到 pq 里,与 pq 不互素的数恰好是含因子 p 或含因子 q 的数。
p 的倍数 p, 2p, …, qp 共 q 个;q 的倍数 q, 2q, …, pq 共 p 个;同时是两者倍数的只有 pq 自己,1 个。
由容斥原理,不互素的共 p + q − 1 个,所以 φ(pq) = pq − p − q + 1 = (p − 1)(q − 1)。
p ≠ q 用在「同时是两者倍数的只有一个」这一步。若 p = q,φ(p²) = p² − p ≠ (p−1)²。具体验证:φ(15) = 8 = 2 × 4。
例 6(课件 p.50,Exercise-10):用欧拉定理算 7¹³⁴ mod 26
题面:用欧拉定理计算 7¹³⁴ mod 26。
提示
三步固定:验互素、算 φ(26)、把 134 对 φ(26) 取余。
解答
① 验互素:gcd(7, 26) = 1。② 算 φ:26 = 2 × 13,φ(26) = 1 × 12 = 12,故 7¹² ≡ 1 (mod 26)。③ 降指数:134 = 11 × 12 + 2,7¹³⁴ = (7¹²)¹¹ × 7² ≡ 49 ≡ 23 (mod 26)。
完整例题
期末这一块的考法是给一个大指数,要求用定理化简。下面这道自拟题把分解、可乘性和降指数三步都用上。
题面:用欧拉定理计算 5¹⁰⁰ mod 21。
解法:
- 验互素:21 = 3 × 7,5 不是 3 或 7 的倍数,gcd(5, 21) = 1,可以用欧拉定理。
- 算 φ:3 和 7 互素,用可乘性,φ(21) = φ(3) × φ(7) = 2 × 6 = 12。所以 5¹² ≡ 1 (mod 21)。
- 降指数:100 = 8 × 12 + 4,5¹⁰⁰ = (5¹²)⁸ × 5⁴ ≡ 5⁴ (mod 21)。
- 算零头:5⁴ = 625 = 29 × 21 + 16,所以 5¹⁰⁰ ≡ 16 (mod 21)。
- 验算:5² = 25 ≡ 4,5⁴ ≡ 4² = 16 ✓。
答题格式:三步各写一行依据。「gcd = 1」交代为什么能用定理,「φ(21) = 12」交代用了哪条公式,「100 = 8 × 12 + 4」交代怎么降的指数。
变式题(先自己做)
改编自课件 p.50:用欧拉定理计算 3²⁰⁵ mod 40。
提示
40 不是素数,先分解再算 φ。降完指数后剩下的零头还是有点大,想想 3 的几次方模 40 余 1。
判分点与答案(非官方评分标准)
判分点:① 验互素 ② 用可乘性算 φ(40) ③ 指数对 φ(40) 取余 ④ 算出零头并验算。
gcd(3, 40) = 1。40 = 2³ × 5,φ(40) = (8 − 4) × 4 = 16。205 = 12 × 16 + 13,所以 3²⁰⁵ ≡ 3¹³ (mod 40)。
3⁴ = 81 = 2 × 40 + 1 ≡ 1,3 的阶是 4。3¹³ = (3⁴)³ × 3 ≡ 3 (mod 40)。
也可以直接用阶:205 = 51 × 4 + 1,3²⁰⁵ ≡ 3¹ = 3。两种算法答案一致。
闪卡自测
1. 陈述费马小定理的两种形式。第二种真的需要「a 不被 p 整除」吗?
形式一:p ∤ a 时 a^(p−1) ≡ 1 (mod p)。形式二:a^p ≡ a (mod p)。形式二不需要这个条件,p | a 时两边都 ≡ 0,课件加的括号是多余的(p.30)。
2. 什么是一个元素模 p 的「阶」?模 19 下 7 的阶是多少?
阶是使 a^k ≡ 1 的最小正整数 k。7³ = 343 = 18 × 19 + 1,所以 7 的阶是 3。模 19 下阶恰为 18 的六个数 2、3、10、13、14、15 是原根(p.31、p.33)。
3. 费马小定理的证明骨架是什么?哪一步用到了 p 是素数?
乘一个可逆元不改变集合 → 两边取乘积 → 约掉 (p−1)!。p 是素数保证 1 到 p − 1 全都和 p 互素,于是 a·i 都不为 0,(p−1)! 也能约掉。欧拉定理是同一个骨架(p.32)。
4. 为什么 φ(1) = 1,而不是照「小于 n」的字面读成 0?
标准写法把定义写成「不超过 n 且与 n 互素」,n = 1 时只有 1 本身,gcd(1, 1) = 1,所以 φ(1) = 1。n > 1 时两种说法结果相同(p.34)。
5. 欧拉定理的形式二如何推出 RSA 的解密正确性?
RSA 里 ed ≡ 1 (mod φ(n)),即 ed = kφ(n) + 1。于是 (m^e)^d = (m^φ(n))^k × m ≡ m (mod n)。这是互素消息的情形,非互素消息还要借 CRT 论证(p.37)。
6. 如果只能记一个定理,为什么该记欧拉定理?
因为费马小定理是它的特例:n 取素数 p 时 φ(p) = p − 1,欧拉定理立刻退回 a^(p−1) ≡ 1 (mod p)。课件的总结页也把欧拉放在上层、费马放在下层(p.37、p.45)。
下一讲
下一页 L02e:中国剩余定理 讲怎么把模 77 这样的大表盘拆成模 7 和模 11 两个小表盘分开算。去之前把例 6 的三步在纸上独立写一遍。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。