1.简单
不要把大数乘开来求 183² mod 11：先取模化简。
n = 11
183² mod 11 =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(141, 63)。
a = 141b = 63
gcd(141, 63) =
3.中等
求欧拉函数 φ(40)，即 1 到 40 中与 40 互素的整数个数。
n = 40 = 23·5
φ(40) =
4.中等
解 30x ≡ 36 (mod 47)。给出满足 0 < x < 47 的解 x。
30x ≡ 36 (mod 47)
x =
5.困难
某个 RSA 密钥使用 p = 43，q = 47，e = 11。解密密文 c = 2004：求消息 m。
p = 43q = 47e = 11c = 2004
m =
6.困难
解 30x ≡ 27 (mod 33)。给出最小的正解 x。
30x ≡ 27 (mod 33)
x =
答案
- 1. 183² mod 11 = 5
- 2. gcd(141, 63) = 3
- 3. φ(40) = 16
- 4. x = 20
- 5. m = 1947
- 6. x = 2
完整分步解答：请在 examproblems.com 上练习本主题。