1.简单
求最小公倍数 lcm(245, 189)。先用欧几里得算法求最大公约数。
a = 245b = 189
lcm(245, 189) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(294, 240)。先用欧几里得算法求最大公约数。
a = 294b = 240
lcm(294, 240) =
3.中等
求欧拉函数 φ(51)，即 1 到 51 中与 51 互素的整数个数。
n = 51 = 3·17
φ(51) =
4.中等
求 59 模 64 的逆元：满足 0 < x < 64 且 59·x ≡ 1 (mod 64) 的数 x。
a = 59n = 64
59−1 mod 64 =
5.困难
用 RSA 公钥 (n, e) = (115, 5) 加密消息 m = 112。求密文 c。
n = 115e = 5m = 112
c =
6.困难
用反复平方法求 68142 mod 73。
a = 68k = 142n = 73
68142 mod 73 =
答案
- 1. lcm(245, 189) = 6615
- 2. lcm(294, 240) = 11760
- 3. φ(51) = 32
- 4. 59−1 mod 64 = 51
- 5. c = 102
- 6. 68142 mod 73 = 38
完整分步解答：请在 examproblems.com 上练习本主题。