1.简单
求最小公倍数 lcm(1008, 342)。先用欧几里得算法求最大公约数。
a = 1008b = 342
lcm(1008, 342) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(1224, 528)。先用欧几里得算法求最大公约数。
a = 1224b = 528
lcm(1224, 528) =
3.中等
求 10 模 47 的逆元：满足 0 < x < 47 且 10·x ≡ 1 (mod 47) 的数 x。
a = 10n = 47
10−1 mod 47 =
4.中等
解 21x ≡ 20 (mod 61)。给出满足 0 < x < 61 的解 x。
21x ≡ 20 (mod 61)
x =
5.困难
用反复平方法求 59174 mod 74。
a = 59k = 174n = 74
59174 mod 74 =
6.困难
用 RSA 公钥 (n, e) = (697, 13) 加密消息 m = 248。求密文 c。
n = 697e = 13m = 248
c =
答案
- 1. lcm(1008, 342) = 19152
- 2. lcm(1224, 528) = 26928
- 3. 10−1 mod 47 = 33
- 4. x = 30
- 5. 59174 mod 74 = 11
- 6. c = 402
完整分步解答：请在 examproblems.com 上练习本主题。