Appearance
第2章：同余 · 原始习题解析
正文教程：返回 第2章：同余
这页只放原始习题、考试写法和解析。复习时建议先看【考试写法】，那是考试卷面上应该呈现的主线；括号解析负责解释“为什么这样判断、为什么这样变形”。
这页按“原题 → 考试写法 → 胎教版解析”的顺序整理。每道题之间用分割线隔开，复习时不用在答案区和解析区来回跳。
原始练习题扫描
下面是本章对应的原始练习题扫描。建议先把上面的例题看懂，再回到这里按题号练。
逐题解析
判断题 1
原题： 12,15,18,21,24,27 是模 8 的一个完全剩余系
考试写法：
错。
模 8 的完全剩余系必须有 8 个不同余数。题中只有 6 个数，而且余数只出现 0,2,3,4,5,7，缺 1,6。
回看正文：完全剩余系。
胎教版解析（默认隐藏，展开看为什么）
答案：错。
先翻译“完全剩余系”：
模
8的完全剩余系，就是要刚好代表0,1,2,3,4,5,6,7这 8 种余数，而且每种出现一次。
题目给了 6 个数：
12,15,18,21,24,27
第一眼就可以发现：模 8 应该有 8 个代表，但这里只给了 6 个数，数量已经不够。
我们再把余数算出来验证：
12≡4 (mod 8)15≡7 (mod 8)18≡2 (mod 8)21≡5 (mod 8)24≡0 (mod 8)27≡3 (mod 8)
出现的余数是：
0,2,3,4,5,7
缺了：
1,6
所以它不是模 8 的完全剩余系。
回看正文：完全剩余系。
判断题 2
原题： 若 x 遍历模 m 的完全剩余系，则 ax 也遍历模 m 的完全剩余系
考试写法：
错。
只有当 (a,m)=1 时，ax 才会随着 x 遍历完全剩余系。反例：模 4，取 a=2，x=0,1,2,3 时，2x 的余数只有 0,2,0,2，没有遍历全部。
胎教版解析（默认隐藏，展开看为什么）
答案：错。
这句话少了一个关键条件：
(a,m)=1
为什么必须互素？
因为如果 a 和 m 有公因数，乘上 a 之后，很多余数会被“挤到一起”，不可能把所有余数都跑一遍。
看一个最小反例：
取 m=4,a=2。
模 4 的一个完全剩余系可以取：
0,1,2,3
现在乘上 a=2：
2×0=0≡0 (mod 4)2×1=2≡2 (mod 4)2×2=4≡0 (mod 4)2×3=6≡2 (mod 4)
得到的余数只有：
0,2,0,2
它没有出现 1 和 3，所以不是完全剩余系。
真正正确的说法是：
如果
(a,m)=1，并且x遍历模m的完全剩余系，那么ax也遍历模m的完全剩余系。
回看正文：完全剩余系。
判断题 3
原题： 最小非负完全剩余系和绝对值最小完全剩余系中元素个数相等
考试写法：
对。
“最小非负完全剩余系”和“绝对值最小完全剩余系”只是代表选法不同，元素个数都等于 m。
胎教版解析（默认隐藏，展开看为什么）
答案：对。
这题要抓住“换代表，不换余数种类”。
模 m 的完全剩余系，不管你怎么选代表，本质上都要代表：
0,1,2,...,m-1
一共 m 种余数。
“最小非负完全剩余系”通常是：
0,1,2,...,m-1
“绝对值最小完全剩余系”可能长这样：
比如模 5 时，可以取：
-2,-1,0,1,2
你看，数字长得不一样，但仍然是 5 个数，仍然代表模 5 的 5 种余数。
所以二者元素个数相等。
回看正文：完全剩余系。
判断题 4
原题： 若 p 是素数，则模 p 的完全剩余系和简化剩余系中元素个数相等
考试写法：
错。
模素数 p 的完全剩余系有 p 个元素；简化剩余系去掉了和 p 不互素的 0，所以只有 p-1 个元素。
胎教版解析（默认隐藏，展开看为什么）
答案：错。
先看两个集合分别在数什么。
模 p 的完全剩余系：
0,1,2,...,p-1，一共p个。
模 p 的简化剩余系：
只保留和
p互素的余数。
因为 p 是素数，所以 1,2,...,p-1 都和 p 互素。
但是 0 和 p 不互素，因为 (0,p)=p。
所以简化剩余系少了 0，只有：
p-1 个元素。
完全剩余系有 p 个，简化剩余系有 p-1 个，不相等。
回看正文：简化剩余系与欧拉函数。
判断题 5
原题： 模 m 的一个简化剩余系中的元素，可以都为奇数，也可以都为偶数
考试写法：
不一定。
如果 m 是奇数，可以通过加减 m 改变代表元奇偶性，所以可以选成都奇或都偶；但如果 m 是偶数，和 m 互素的数必须是奇数，不可能全偶。
胎教版解析（默认隐藏，展开看为什么）
答案：不一定，所以判断题按“错”处理。
先理解“简化剩余系”：
它要选出所有和
m互素的余数代表。
题目说“可以都为奇数，也可以都为偶数”，这句话对所有 m 都成立吗？不成立。
看 m=8。
和 8 互素的余数只能是：
1,3,5,7
为什么没有偶数？
因为偶数都至少和 8 有公共因子 2，所以不互素。
因此模 8 的简化剩余系不可能全部选成偶数。
所以原命题不能作为普遍结论。
回看正文：简化剩余系与欧拉函数。
综合题 1
原题： 模 55 的简化剩余系中元素的个数
考试写法：
模 55 的简化剩余系中有 40 个元素。
其实就是求 φ(55)。55=5×11，所以 φ(55)=55×(1-1/5)×(1-1/11)=40。
回看正文：简化剩余系 & 欧拉函数。
胎教版解析（默认隐藏，展开看为什么）
答案：
40
这题翻译一下：
简化剩余系有多少个元素，就是求
φ(55)。
第一步，把 55 分解成素因子：
55=5×11
第二步，用欧拉函数公式：
如果：
n=p₁^α¹ p₂^α² ...
那么：
φ(n)=n(1-1/p₁)(1-1/p₂)...
这里的素因子是 5 和 11，所以：
φ(55)=55×(1-1/5)×(1-1/11)
把括号算成人话：
1-1/5=4/5，意思是去掉 5 的倍数。1-1/11=10/11，意思是去掉 11 的倍数。
继续算：
φ(55)=55×4/5×10/11
先约分：
55÷5=11
于是：
φ(55)=11×4×10/11
再约掉 11：
φ(55)=4×10=40
所以模 55 的简化剩余系有 40 个元素。
回看正文：欧拉函数 φ(n)。
综合题 2
原题： 计算 5³⁰ (mod 23)
考试写法：
5³⁰ ≡ 16 (mod 23)。
因为 23 是素数，5²²≡1 (mod 23)，所以 5³⁰≡5⁸。平方表：5²≡2，5⁴≡4，5⁸≡16。
回看正文：费马小定理。
胎教版解析（默认隐藏，展开看为什么）
答案：
5³⁰≡16 (mod 23)
第一步，先判断能不能用费马小定理。
费马小定理说：
如果
p是素数，且(a,p)=1，那么a^(p-1)≡1 (mod p)。
这里 23 是素数，5 和 23 互素，所以：
5²²≡1 (mod 23)
第二步，把指数 30 拆成“22 的倍数 + 剩下的”：
30=22+8
所以：
5³⁰=5²²×5⁸≡1×5⁸≡5⁸ (mod 23)
第三步，算 5⁸。不要硬算 390625，用平方表：
5²=25≡2 (mod 23)
再平方：
5⁴≡2²=4 (mod 23)
再平方：
5⁸≡4²=16 (mod 23)
所以：
5³⁰≡16 (mod 23)
回看正文：费马小定理。
综合题 3
原题： 计算 φ(3000)
考试写法：
φ(3000)=800。3000=2³×3×5³，所以φ(3000)=3000×1/2×2/3×4/5=800。
回看正文：欧拉函数 φ(n)。
胎教版解析（默认隐藏，展开看为什么）
答案：
φ(3000)=800
第一步，先分解 3000。
3000=3×1000
而：
1000=10³=(2×5)³=2³×5³
所以：
3000=2³×3×5³
第二步，只看不同的素因子：
2,3,5
欧拉函数公式是：
φ(3000)=3000×(1-1/2)×(1-1/3)×(1-1/5)
把每一项换成分数：
1-1/2=1/21-1/3=2/31-1/5=4/5
所以：
φ(3000)=3000×1/2×2/3×4/5
一步一步约分：
3000×1/2=1500
1500×2/3=1000
1000×4/5=800
所以：
φ(3000)=800
回看正文：欧拉函数 φ(n)。
综合题 4
原题： 计算 7¹⁰⁰⁰ (mod 47)
考试写法：
7¹⁰⁰⁰ ≡ 36 (mod 47)。47 是素数，所以 7⁴⁶≡1。1000=46×21+34，所以只要算 7³⁴。用重复平方化简，结果是 36。
回看正文：模重复平方算法。
胎教版解析（默认隐藏，展开看为什么）
答案：
7¹⁰⁰⁰≡36 (mod 47)
第一步，先降指数。
47 是素数，7 和 47 互素，所以费马小定理给出：
7⁴⁶≡1 (mod 47)
第二步，把 1000 除以 46：
1000=46×21+34
所以：
7¹⁰⁰⁰≡7³⁴ (mod 47)
第三步，用重复平方算 7³⁴。
先列平方表：
7²=49≡2 (mod 47)
7⁴≡2²=4 (mod 47)
7⁸≡4²=16 (mod 47)
7¹⁶≡16²=256
256=47×5+21，所以：
7¹⁶≡21 (mod 47)
继续平方：
7³²≡21²=441
441=47×9+18，所以：
7³²≡18 (mod 47)
第四步，把 34 拆成：
34=32+2
所以：
7³⁴=7³²×7²
代入平方表：
7³⁴≡18×2=36 (mod 47)
所以答案是 36。
回看正文：模重复平方算法。
综合题 5
原题： 计算 5²⁸ (mod 22)
考试写法：
5²⁸ ≡ 15 (mod 22)。φ(22)=10，所以 5¹⁰≡1 (mod 22)。28=2×10+8，只要算 5⁸。平方表：5²≡3，5⁴≡9，5⁸≡15。
胎教版解析（默认隐藏，展开看为什么）
答案：
5²⁸≡15 (mod 22)
第一步，这里模数 22 不是素数，所以不能直接用费马小定理。
但可以用欧拉定理。
欧拉定理要求：
(5,22)=1
确实成立，因为 22=2×11，5 不含因子 2 或 11。
第二步，求 φ(22)：
22=2×11
所以：
φ(22)=22×(1-1/2)×(1-1/11)=10
于是：
5¹⁰≡1 (mod 22)
第三步，降指数：
28=10×2+8
所以：
5²⁸≡5⁸ (mod 22)
第四步，算 5⁸：
5²=25≡3 (mod 22)
5⁴≡3²=9 (mod 22)
5⁸≡9²=81
81=22×3+15
所以：
5⁸≡15 (mod 22)
最终：
5²⁸≡15 (mod 22)
回看正文：欧拉定理。
综合题 6
原题： RSA 中 p=19,q=31,e=17，求 d
考试写法：
d=413。φ(n)=(19-1)(31-1)=540，要求 17d≡1 (mod 540)。扩展欧几里得解得 d=413。
回看正文：RSA 里求私钥 d。
胎教版解析（默认隐藏，展开看为什么）
答案：
d=413
RSA 里这道题的本质是：
找
d，使ed≡1 (mod φ(n))。
第一步，先算 φ(n)。
因为：
n=pq=19×31
所以：
φ(n)=(p-1)(q-1)=(19-1)(31-1)
也就是：
φ(n)=18×30=540
第二步，把题目变成一次同余：
17d≡1 (mod 540)
这就是求 17 在模 540 下的逆元。
第三步，用扩展欧几里得倒推。
先辗转相除：
540=17×31+1317=13×1+413=4×3+14=1×4+0
最后一个非 0 余数是 1，说明 17 和 540 互素，逆元存在。
开始倒推：
1=13-4×3
而：
4=17-13
代入：
1=13-(17-13)×3
拆括号：
1=13×4-17×3
而：
13=540-17×31
继续代入：
1=(540-17×31)×4-17×3
拆开：
1=540×4-17×124-17×3
合并 17：
1=540×4-17×127
也就是：
17×(-127)+540×4=1
所以：
17×(-127)≡1 (mod 540)
把负数变成 0 到 539 之间的正代表：
-127+540=413
所以：
d=413
回看正文：RSA 里求私钥 d。
综合题 7
原题： 证明 11、4、8 的整除判别法
考试写法：
整除判别法证明思路。
设十进制数 n=a_k...a_1a_0。
- 对
11：因为10≡-1 (mod 11)，所以10²≡1，奇偶位会交替变号，因此11|n当且仅当奇偶位数字和之差能被 11 整除。 - 对
4：因为100能被4整除，所以百位以上都不影响余数，只看最后两位a_1a_0。 - 对
8：因为1000能被8整除，所以只看最后三位a_2a_1a_0。
回看正文：整除判别法速查。
胎教版解析（默认隐藏，展开看为什么）
题目设十进制整数：
n=a_k10^k+a_{k-1}10^{k-1}+...+a_1×10+a_0
这里的 a_0 是个位，a_1 是十位，a_2 是百位。
（1）证明 11|n 的判别法
关键只看一句：
10≡-1 (mod 11)
所以：
10²≡(-1)²=1 (mod 11)10³≡(-1)³=-1 (mod 11)10⁴≡1 (mod 11)
也就是说，10^i 在模 11 下会一正一负地交替：
偶数次方像 +1，奇数次方像 -1。
于是：
n=a_0+a_1×10+a_2×10²+a_3×10³+...
在模 11 下变成：
n≡a_0-a_1+a_2-a_3+... (mod 11)
这就是：
(a_0+a_2+...)-(a_1+a_3+...)
所以：
11|n
当且仅当：
11 | (a_0+a_2+...)-(a_1+a_3+...)
这就是奇偶位数字和之差判别法。
（2）证明 4|n 当且仅当 4|a_1a_0
这里 a_1a_0 不是乘法，而是最后两位组成的数：
10a_1+a_0
因为：
100≡0 (mod 4)
所以百位、千位、更高位都是 100 的倍数，在模 4 下全部消失。
剩下的只有：
10a_1+a_0
所以：
n≡10a_1+a_0 (mod 4)
因此 n 能不能被 4 整除，只看最后两位。
回看正文：整除判别法速查。
（3）证明 8|n 当且仅当 8|a_2a_1a_0
同理，a_2a_1a_0 表示最后三位：
100a_2+10a_1+a_0
因为：
1000≡0 (mod 8)
所以千位及以上全部是 1000 的倍数，在模 8 下都等于 0。
剩下的只有最后三位：
100a_2+10a_1+a_0
因此：
8|n
当且仅当最后三位能被 8 整除。
回看正文：整除判别法速查。
综合题 8
原题： 证明整数计算结果的弃九法
考试写法：
弃九法证明思路。
核心是 10≡1 (mod 9)，所以一个数模 9 的余数等于它各位数字和模 9 的余数。
如果 c=ab 是正确乘积，那么必有：数字和(a)×数字和(b) ≡ 数字和(c) (mod 9)。
如果这个同余不成立，乘法结果一定错；如果成立，也只能说明“没被弃九法抓出来”，不能保证一定正确。
胎教版解析（默认隐藏，展开看为什么）
这题的核心是：
10≡1 (mod 9)
为什么这句话有用？
因为十进制数：
a=a_k10^k+...+a_1×10+a_0
在模 9 下，每个 10^i 都等于 1：
10≡1 (mod 9)10²≡1²=1 (mod 9)10³≡1³=1 (mod 9)
所以：
a≡a_k+...+a_1+a_0 (mod 9)
也就是说：
一个数模 9 的余数，等于它各位数字和模 9 的余数。
同理：
b≡各位数字和(b) (mod 9)c≡各位数字和(c) (mod 9)
如果计算 c=ab 是正确的，那么同余也必须正确：
c≡ab (mod 9)
把 a,b,c 换成各位数字和，就得到：
各位数字和(a)×各位数字和(b)≡各位数字和(c) (mod 9)
所以如果这个同余不成立，原来的乘法结果一定错。
注意最后这个坑：
弃九法只能“发现一部分错误”，不能证明结果一定正确。
因为两个不同的错误结果，也可能模 9 余数碰巧一样。
回看正文：整除判别法速查。
综合题 9
原题： 利用 Miller-Rabin 算法判断 1001 是否为素数
考试写法：
1001 不是素数。
最直接分解：1001=7×11×13。
如果按 Miller-Rabin 思路，1000=2³×125，取底数 2 会在平方链里暴露不符合素数的情况，因此可判为合数。
回看正文：Miller-Rabin 素性测试。
胎教版解析（默认隐藏，展开看为什么）
答案：
1001 不是素数。
先说最直接的检查：
1001=7×143=7×11×13
所以它肯定不是素数。
但题目要求用 Miller-Rabin，我们也按这个流程走一遍。
第一步，把 n-1 写成 2^s×d，其中 d 是奇数。
这里：
n=1001
所以：
n-1=1000
分解：
1000=8×125=2³×125
因此：
s=3,d=125
第二步，选一个底数。取最常用的：
a=2
第三步，先算：
x=2^125 mod 1001
用重复平方算出来：
2^125≡32 (mod 1001)
Miller-Rabin 的素数候选要求：
初始 x 如果是 1 或 n-1=1000，暂时过关。
但这里：
x=32
既不是 1，也不是 1000。
第四步，继续平方，看中途会不会出现 1000。
第一次平方：
32²=1024≡23 (mod 1001)
第二次平方：
23²=529≡529 (mod 1001)
在这个链条里没有出现 1000。
所以底数 2 已经能证明 1001 是合数。
这和前面的直接分解：
1001=7×11×13
互相验证。
回看正文：Miller-Rabin 素性测试。