← COMP5521 全部讲次
L02d · 第 2 周

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。

模 19 的幂表,行是底数 a 从 1 到 18,列是指数从 a 到 a 的 18 次方。每一行用方框圈出它开始重复之前的那一段,绿色底是重复出现的部分。最右一列 a 的 18 次方整列都是 1,没有例外
图片来源:COMP5521 Lecture 2 Number Theory, p.31

类比在哪里失效:

  • 表盘只能演示,不能证明。为什么一定会回到 1,要靠第 2 个概念里的证明。
  • 模数不是素数时,表盘上有些格子永远走不到,比如和模数不互素的那些格子。这时回到 1 的步数变成 φ(n),不再是 n − 1。

从零讲起

1. 素数与唯一分解

它解决什么问题

后面所有定理都要先问一句:模数是不是素数,能不能拆成素数相乘。φ(n) 的公式也是按素数因子来算的。所以先把素数和分解讲清楚。

直觉

素数是乘法里拆不动的积木。任何大于 1 的整数都能拆成一堆素数相乘,而且不管怎么拆,最后得到的积木种类和块数都一样。

1 不算素数。如果 1 算素数,分解时可以随便乘任意多个 1,「唯一」就不成立了。

一步一步看

目标:把 24 一步步拆成素数,看出不管先拆哪个,最后都是三个 2 和一个 3。

把 24 拆成素数积木。

  1. 24 是偶数,先拆出一个 2:24 = 2 × 12。

  2. 12 还是偶数:12 = 2 × 6;6 = 2 × 3。

  3. 3 是素数,拆不动了。

  4. 收集起来,得到下表。

    素数 出现次数 写法
    2 3 次 2³
    3 1 次 3
  5. 所以 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。

  1. 取 a = 7:1 → 7 → 11 → 1。第 3 步回到 1,所以 7 的阶是 3。

  2. 取 a = 2:1 → 2 → 4 → 8 → 16 → 13 → …,要走满 18 步才回到 1。

    模 19 下从 1 出发每次乘 a 再取模的两个循环。左边 a = 7,只有 1、7、11 三格连成小圈,3 步回到 1,7 的阶是 3。右边 a = 2,依次经过 1、2、4、8、16、13、7、14、9、18、17、15、11、3、6、12、5、10 共 18 格,18 步才回到 1,每格都踩到,所以 2 是原根

  3. 3 能整除 18,所以 7 走 18 步也会回到 1:转六个小圈。

  4. 两个数走到第 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。

证明只有三步,骨架是「乘可逆元不改变集合 → 两边取乘积 → 约掉阶乘」:

上排是 1 到 6,每个数乘 3 再取模 7,下排依次得到 3、6、2、5、1、4,还是 1 到 6 这六个数,一个不多一个不少,只是换了顺序。底部写着两排各自全乘起来相等,3 的 6 次方乘 6 的阶乘同余 6 的阶乘,约掉 6 的阶乘得 3 的 6 次方同余 1

  1. a 与 p 互素,所以 a·1、a·2、…、a·(p−1) 模 p 后互不相同,又都不为 0,正好是 1 到 p − 1 的一个重排。
  2. 两排各自乘起来相等:a^(p−1) × (p−1)! ≡ (p−1)! (mod p)。
  3. (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)。

  1. 15 = 3 × 5,素因子是 3 和 5。

  2. 在 1 到 15 里划掉 3 的倍数:3、6、9、12、15,共 5 个。

  3. 再划掉 5 的倍数:5、10、15,共 3 个。15 被划了两次。

    1 到 15 排成一行格子。3 的倍数 3、6、9、12、15 和 5 的倍数 5、10、15 被划掉,格子下方小字注明被哪个素数划掉,15 同时标了 3 和 5。剩下 1、2、4、7、8、11、13、14 共 8 个,底部写着 φ(15) = 8 = 2 × 4

  4. 一共划掉 5 + 3 − 1 = 7 个,剩下 15 − 7 = 8 个,φ(15) = 8。

  5. 对照公式:(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。

  1. 验互素:gcd(7, 26) = 1,可以用欧拉定理。

  2. 算 φ:26 = 2 × 13,φ(26) = 1 × 12 = 12。所以 7¹² ≡ 1 (mod 26)。

  3. 把 134 个 7 按 12 个一组打包:134 = 11 × 12 + 2。

    134 个 7 排成 11 个方块,每个方块写着 7 的 12 次方同余 1,最后剩一个小方块 7 的平方。说明文字:11 组,每组 12 个 7,φ(26) = 12,欧拉定理说每组乘起来同余 1 (mod 26);134 = 11 × 12 + 2,只剩最后 2 个 7 有用;7 的 134 次方同余 1 的 11 次方乘 7 的平方,等于 49,同余 23

  4. 每组乘起来都是 1,11 组还是 1,只剩 7² = 49。

  5. 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,形式一立刻变成费马小定理。所以只记欧拉定理就够,费马是它的特例。

降大指数的固定三步:

  1. 验互素,确认能用定理。
  2. 算 φ(n),必要时先分解 n。
  3. 指数除以 φ(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 逐道算一遍;最后做变式题,回查最容易错的地方:降指数前忘了验互素。

必背

  1. 费马小定理 a^(p−1) ≡ 1 (mod p) 要求 p ∤ a;形式二 a^p ≡ a (mod p) 对所有整数 a 成立,不需要 p ∤ a。
  2. 模 19 的幂表里 a¹⁸ 那一列全是 1;各元素的阶都整除 18,阶恰为 18 的六个数(2, 3, 10, 13, 14, 15)是原根。
  3. φ(p) = p − 1,φ(p^k) = p^k − p^(k−1),φ(pq) = (p−1)(q−1)(p ≠ q 为素数);可乘性 φ(mn) = φ(m)φ(n) 要求 m、n 互素。
  4. φ(1) = 1,定义按「不超过 n 且与 n 互素」来读,n > 1 时与「小于 n」结果相同。
  5. 欧拉定理 gcd(a, n) = 1 ⇒ a^φ(n) ≡ 1 (mod n),n 取素数 p 时退回费马小定理,所以只记欧拉定理即可。
  6. 大指数降幂三步:验互素 → 算 φ(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。

解法:

  1. 验互素:21 = 3 × 7,5 不是 3 或 7 的倍数,gcd(5, 21) = 1,可以用欧拉定理。
  2. 算 φ:3 和 7 互素,用可乘性,φ(21) = φ(3) × φ(7) = 2 × 6 = 12。所以 5¹² ≡ 1 (mod 21)。
  3. 降指数:100 = 8 × 12 + 4,5¹⁰⁰ = (5¹²)⁸ × 5⁴ ≡ 5⁴ (mod 21)。
  4. 算零头:5⁴ = 625 = 29 × 21 + 16,所以 5¹⁰⁰ ≡ 16 (mod 21)。
  5. 验算: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 的三步在纸上独立写一遍。

下一讲 →
L02e L02e 中国剩余定理:一个大表盘拆成几个小表盘

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。