1.简单
用欧几里得算法求 gcd(495, 341)。
a = 495b = 341
gcd(495, 341) =
数论与模运算练习卷（附答案）
2.简单
不要把大数乘开来求 394² mod 6：先取模化简。
n = 6
394² mod 6 =
3.中等
解 37x ≡ 29 (mod 41)。给出满足 0 < x < 41 的解 x。
37x ≡ 29 (mod 41)
x =
4.中等
解 66x ≡ 28 (mod 73)。给出满足 0 < x < 73 的解 x。
66x ≡ 28 (mod 73)
x =
5.困难
在 {0, 1, …, 83} 中，45x ≡ 12 (mod 84) 有多少个解 N？
45x ≡ 12 (mod 84)
N =
6.困难
某个 RSA 密钥使用素数 p = 29 和 q = 41，公钥指数 e = 23。求私钥指数 d（0 < d < φ(n)）。
p = 29q = 41e = 23
d =
答案
- 1. gcd(495, 341) = 11
- 2. 394² mod 6 = 4
- 3. x = 3
- 4. x = 69
- 5. N = 3
- 6. d = 487
完整分步解答：请在 examproblems.com 上练习本主题。