Appearance
第5章：原根和离散对数 · 原始习题解析
正文教程：返回 第5章：原根和离散对数
这页只放原始习题、考试写法和解析。复习时建议先看【考试写法】，那是考试卷面上应该呈现的主线；括号解析负责解释"为什么这样判断、为什么这样变形"。
这页按"原题 → 考试写法 → 考场傻瓜版解析"的顺序整理。每道题之间用分割线隔开，复习时不用在答案区和解析区来回跳。
原始练习题扫描
下面是本章对应的原始练习题扫描。建议先把上面的例题看懂，再回到这里按题号练。
逐题解析
判断题 1
原题： 若 g 是模 p 的原根，且 g^x ≡ 1 (mod p)，则 x 是 p 的整数倍
考试写法：
错。
如果 g 是模 p 的原根，其阶为 φ(p) = p-1。因此，当 g^x ≡ 1 (mod p) 时，结论应该是 x 是 p-1 的倍数，而不是 p 的倍数。
考场傻瓜版解析（默认隐藏，展开看为什么）
答案：错。
"原根"就像是一个跑道，跑完一整圈需要走 p-1 步（因为 0 不跑）。
题目说 g^x 跑到终点了（等于 1），说明 x 肯定跑了完整的圈数，也就是说 x 必须是 p-1 的倍数。
这道题故意坑你，说 x 是 p 的倍数，差了个 1，直接判错。
判断题 2
原题： 若 gcd(a,m)=1 且 a^d ≡ 1 (mod m)，则 d | φ(m) （d 能整除 φ(m)）
考试写法：
错。
根据阶的性质，a^d ≡ 1 只能推导出 a 的阶 ordm(a) 能整除 d，且 ordm(a) 能整除 φ(m)。但绝不能推导出 d 必须整除 φ(m)。
考场傻瓜版解析（默认隐藏，展开看为什么）
答案：错。
这题逻辑因果说反了。
比如 a=2，m=5，φ(5)=4。我们知道 2⁴ ≡ 1，所以 2⁸ 也等于 1（跑了两圈）。
在这个例子里，把 d 当成 8，确实 2⁸ ≡ 1。但是 8 能整除 φ(m) 也就是 4 吗？显然不能。
所以结论是不成立的。
判断题 3
原题： 只有 m 是素数时，模 m 的原根才存在
考试写法：
错。
原根存在的模数条件不仅包括素数 p，还包括 2、4、p^k 以及 2p^k（其中 p 为奇素数，k 为正整数）。
考场傻瓜版解析（默认隐藏，展开看为什么）
答案：错。
书上的死记硬背考点：模 m 有原根的情况有四种：2、4、素数的幂、2乘以素数的幂。
不光是只有素数才有。比如 9 是合数，但它（3的平方）也有原根。
判断题 4
原题： 根据费马小定理，2⁶ ≡ 1 (mod 7)，故 ord7(2) = 6
考试写法：
错。
阶的定义是"第一次"达到 1 的正指数。虽然 2⁶ ≡ 1 (mod 7)，但经过验证，2³ = 8 ≡ 1 (mod 7)，因此 2 模 7 的阶是 3，而不是 6。
考场傻瓜版解析（默认隐藏，展开看为什么）
答案：错。
阶的意思是"你第一次回到起点用了几步"。
费马小定理说 2⁶ ≡ 1 没错，但这是跑了两圈的结果。你其实在第 3 步（2³ = 8 ≡ 1）就已经回到起点了。所以阶是 3。
判断题看到这种想当然直接给出最大值的，一般都是错的。
判断题 5
原题： 若 y ≡ g^x (mod p)，则 x ≡ ind_g(y) (mod p)
考试写法：
错。
离散对数表示的是指数，指数是在周期内循环的。如果 g 是原根，其周期是 p-1。所以指数 x 应该满足 x ≡ ind_g(y) (mod p-1)，而不是模 p。
考场傻瓜版解析（默认隐藏，展开看为什么）
答案：错。
只要看到算"指数"（比如离散对数就是算指数 x），它的底座永远是圈长 p-1（或者 φ(m)）。
如果按题目说的模 p，比如 p=5，你指数 5 和 0 就算成同一个了，但其实 5 次方和 0 次方结果根本不一样！应该是模 4（p-1）才对。
综合题 1
原题： 已知 6 是模 41 的原根，9 ≡ 6³⁰ (mod 41)，求 ord41(9)
考试写法：
ord41(9) = 4。
- 已知 6 是模 41 的原根，说明 6 的阶是 φ(41) = 40。
- 要求 9 的阶，即求 6³⁰ 的阶。
- 代入公式：
ordm(gk) = φ(m) / gcd(φ(m), k) = 40 / gcd(40, 30)。 - gcd(40, 30) = 10，所以 40 / 10 = 4。
考场傻瓜版解析（默认隐藏，展开看为什么）
答案：4。
无脑套第 5 章那个唯一重要的公式：要求 g^k 的阶，拿全图格子数除以最大公因数。
全图格子数 φ(41) = 40。
现在的 k 是 30。
40 和 30 的最大公因数是 10。
一除：40 ÷ 10 = 4。就这么一秒出答案。
综合题 2
原题： 写出模 5 的全部原根
考试写法：
模 5 的全部原根为 {2, 3}。
φ(5) = 4，寻找 1 到 4 中与 4 互素的指数 k。满足 gcd(k, 4) = 1 的 k 有 1, 3。
验证 2 是一个原根（2¹=2, 2²=4, 2³=3, 2⁴=1）。
所以全部原根为 2¹ 和 2³，即 {2, 3}。
考场傻瓜版解析（默认隐藏，展开看为什么）
考全部原根，记住口诀：找出一个，乘遍互素指数。
先随便找出一个模 5 的原根：试 2。2, 4, 8(即3), 1。跑遍了 4 个数，2 是原根！
模 5 的 φ 也是 4。在 1 到 4 里找跟 4 互素的数：1 和 3。
把这些互素的数当指数，盖在 2 头上：2¹ = 2；2³ = 8 ≡ 3。
全部原根就是 2 和 3。
综合题 3
原题： 已知模 22 的原根存在，求模 22 的所有原根
考试写法：
模 22 的全部原根为 {7, 13, 17, 19}。
- φ(22) = 10。寻找一个原根，测试 7。7 的阶为 10，因此 7 是原根。
- 在 1~10 中找与 10 互素的 k：k = 1, 3, 7, 9。
- 计算 7 的这些幂次：
7¹ ≡ 7
7³ ≡ 343 ≡ 13 (mod 22)
7⁷ ≡ 17 (mod 22)
7⁹ ≡ 19 (mod 22)
考场傻瓜版解析（默认隐藏，展开看为什么）
和上一题一模一样的套路。
φ(22) = 10。
随便试出一个原根 7（考试时通常会直接告诉你 7 是原根让你算其它的，如果没说只能从2开始自己试）。
在 1 到 10 里找跟 10 不共公约数的数，有 1, 3, 7, 9。
把它们当指数给 7 戴上：算 7¹、7³、7⁷、7⁹ 模 22 的值。
算出来分别是 7、13、17、19。拿分。
综合题 4
原题： 已知模 26 的原根存在，求模 26 的所有原根
考试写法：
模 26 的全部原根为 {7, 11, 15, 19}。
- φ(26) = 12。验证得知 7 是原根。
- 1 到 12 中与 12 互素的 k 为：1, 5, 7, 11。
- 计算：
7¹ ≡ 7
7⁵ ≡ 11 (mod 26)
7⁷ ≡ 19 (mod 26)
7¹¹ ≡ 15 (mod 26)
考场傻瓜版解析（默认隐藏，展开看为什么）
继续复读机套路：
φ(26) = 12。
原根是 7（别问为什么又是 7，因为 2 不是，3 不是，一直试到 7 才是）。
1 到 12 里跟 12 互素的有：1, 5, 7, 11。
分别算 7 的 1 次、5 次、7 次、11 次方模 26。结果就是 7, 11, 15, 19。
综合题 5
原题： 已知 5 对模 17 的阶为 16，列出所有模 17 阶为 8 的整数
考试写法：
模 17 下阶为 8 的整数为 {2, 8, 9, 15}。
使用阶数公式求满足 ord17(5k) = 8 的 k：
即 16 / gcd(16, k) = 8，解得 gcd(16, k) = 2。
在 1 到 16 中，与 16 的最大公因数为 2 的数有：k = 2, 6, 10, 14。
计算对应的 5^k (mod 17)：
5² ≡ 8
5⁶ ≡ 2
5¹⁰ ≡ 9
5¹⁴ ≡ 15
考场傻瓜版解析（默认隐藏，展开看为什么）
来！直接掏出教程里的**"倍数过滤傻瓜法"**：
算步长 S = φ(17) ÷ 目标阶数 8 = 16 ÷ 8 = 2。
我们要找的 k，肯定是步长 2 的倍数：2, 4, 6, 8, 10, 12, 14, 16。也就是 1×2, 2×2, 3×2 ... 8×2。
查户口：只保留乘数（1 到 8）里跟目标阶 8 互素的！
1 到 8 里跟 8 互素的是 1, 3, 5, 7。
所以合格的 k 就是：1×2=2, 3×2=6, 5×2=10, 7×2=14。
拿到 k=2,6,10,14 后，就算 5 的这些次方 mod 17 就行了。答案就出来了。
综合题 6
原题： 已知 6 对模 41 的阶为 40，列出所有模 41 阶为 8 的整数
考试写法：
模 41 下阶为 8 的整数为 {3, 14, 27, 38}。
公式 40 / gcd(40, k) = 8，推得 gcd(40, k) = 5。
满足条件的 k = 5, 15, 25, 35。
计算 6^k (mod 41)：
6⁵ ≡ 27
6¹⁵ ≡ 3
6²⁵ ≡ 14
6³⁵ ≡ 38
考场傻瓜版解析（默认隐藏，展开看为什么）
继续无脑"倍数过滤法"：
算步长 = 40 ÷ 8 = 5。
候选 k 就是 5 的倍数：1×5, 2×5 ... 8×5。
查户口：乘数 1 到 8 里跟 8 互素的还是 1, 3, 5, 7。
合格的 k = 5, 15, 25, 35。
算 6 的这四次方，得到四个数 3, 14, 27, 38。
综合题 7
原题： 已知 6 对模 41 的阶为 40，列出所有模 41 阶为 10 的整数
考试写法：
模 41 下阶为 10 的整数为 {4, 23, 25, 31}。
公式 40 / gcd(40, k) = 10，推得 gcd(40, k) = 4。
满足条件的 k = 4, 12, 28, 36。
计算 6^k (mod 41)：
6⁴ ≡ 25
6¹² ≡ 4
6²⁸ ≡ 31
6³⁶ ≡ 23
考场傻瓜版解析（默认隐藏，展开看为什么）
傻瓜法第三次使用：
算步长 = 40 ÷ 10 = 4。
候选 k = 1×4, 2×4 ... 10×4。
查户口：乘数 1 到 10 里跟 10 互素的！有 1, 3, 7, 9。
合格的 k = 1×4=4, 3×4=12, 7×4=28, 9×4=36。
去算 6⁴、6¹²、6²⁸、6³⁶ 就好了，毫无思考负担。
综合题 8
原题： 已知 m = 13³ 的原根存在，求模 m 的原根个数
考试写法：
模 13³ 的原根个数是 624。
定理：若模 m 有原根，则原根个数等于 φ(φ(m))。
- 先计算 φ(13³) = 13² × (13-1) = 169 × 12 = 2028。
- 再计算 φ(2028)。分解 2028 = 4 × 3 × 169 = 2² × 3 × 13²。
- φ(2028) = 2028 × (1 - 1/2) × (1 - 1/3) × (1 - 1/13) = 2028 × 1/2 × 2/3 × 12/13 = 624。
考场傻瓜版解析（默认隐藏，展开看为什么）
答案：624。
题干问"个数"，直接套双重欧拉函数公式 φ(φ(m))。
先算里层的 φ(13³)：底座 13 是素数，公式是 13的平方乘以(13-1)，就是 169 × 12 = 2028。
再算外层的 φ(2028)：把 2028 质因数分解成 2、3、13。连乘公式 2028 × 1/2 × 2/3 × 12/13。连乘约分一下就是 624。
综合题 9
原题： 求模 101 的原根个数
考试写法：
模 101 的原根个数是 40。
101 是素数，有原根。个数为 φ(φ(101))。
- φ(101) = 100。
- φ(100) = 100 × (1 - 1/2) × (1 - 1/5) = 100 × 1/2 × 4/5 = 40。
考场傻瓜版解析（默认隐藏，展开看为什么）
这题最简单。原根个数就是算两遍 φ。
第一遍：101 是素数，φ(101) = 100。
第二遍：算 φ(100)。100 的质因子有 2 和 5。用口诀"看底不看头"，直接用 100 × (1/2) × (4/5) = 40。
综合题 10
原题： 已知 ord41(18) = 5，快速求 18¹⁸ (mod 41)
考试写法：
18¹⁸ ≡ 10 (mod 41)。
已知阶为 5，说明 18⁵ ≡ 1 (mod 41)。
指数按阶数取模：18 除以 5 余 3。
因此 18¹⁸ ≡ (18⁵)³ × 18³ ≡ 1 × 18³ ≡ 18³ (mod 41)。
18² = 324 ≡ 37 (mod 41)。
18³ ≡ 37 × 18 = 666 ≡ 10 (mod 41)。
考场傻瓜版解析（默认隐藏，展开看为什么）
考"大指数降维"。题目说阶是 5，潜台词就是"只要凑够 5 次方就是个 1"。
18 个次方里能凑出几个 5？3个，还剩 3个。
也就是说一堆 1 乘完以后，只剩下个 18³。
这就变成小学计算题了：18 的平方是 324，除以 41 余 37。再乘一个 18 就是 37 × 18 = 666。666 除以 41 余 10。
答案就是 10。
综合题 11
原题： 编程实现寻找某个小于 10000 的整数的原根
考试写法：
（这是一道算法逻辑描述题）
寻找模 m 的原根算法步骤：
- 检查是否存在原根：判断 m 是否符合 2, 4, p^k, 2p^k 的形式。不符合则直接返回无原根。
- 计算 φ(m) 并求出 φ(m) 的所有不同素因子 q_1, q_2 ... q_r。
- 从 g = 2 开始遍历到 m-1，首先验证 gcd(g, m) == 1。
- 对满足互素的 g，检查其幂次 g^(φ(m)/q_i) mod m。只要有一个结果等于 1，则 g 不是原根，换下一个数。若对所有的素因子都不等于 1，则 g 即为所求的原根。
考场傻瓜版解析（默认隐藏，展开看为什么）
这道题是考你怎么用最高效的办法搜原根，而不是让你真写个 C++。
笨办法是试 g^1, g^2 ... 一直试到 φ(m)，这在电脑里也极慢。
聪明的办法是：阶必须整除 φ(m)。所以只要挑 φ(m) 的那几个"最大因数"（也就是除以素因子的结果）去验。只要在那些关键点上不是 1，它就只能乖乖跑到最后一步才等于 1。这就是这个算法的核心思想。