1.简单
求最小公倍数 lcm(216, 174)。先用欧几里得算法求最大公约数。
a = 216b = 174
lcm(216, 174) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(441, 324)。先用欧几里得算法求最大公约数。
a = 441b = 324
lcm(441, 324) =
3.中等
求 29 模 37 的逆元：满足 0 < x < 37 且 29·x ≡ 1 (mod 37) 的数 x。
a = 29n = 37
29−1 mod 37 =
4.中等
求欧拉函数 φ(11)，即 1 到 11 中与 11 互素的整数个数。
n = 11 = 11
φ(11) =
5.困难
某个 RSA 密钥使用素数 p = 7 和 q = 13，公钥指数 e = 5。求私钥指数 d（0 < d < φ(n)）。
p = 7q = 13e = 5
d =
6.困难
用 RSA 公钥 (n, e) = (943, 23) 加密消息 m = 518。求密文 c。
n = 943e = 23m = 518
c =
答案
- 1. lcm(216, 174) = 6264
- 2. lcm(441, 324) = 15876
- 3. 29−1 mod 37 = 23
- 4. φ(11) = 10
- 5. d = 29
- 6. c = 587
完整分步解答：请在 examproblems.com 上练习本主题。