1.简单
求最小公倍数 lcm(342, 243)。先用欧几里得算法求最大公约数。
a = 342b = 243
lcm(342, 243) =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(1008, 777)。
a = 1008b = 777
gcd(1008, 777) =
3.中等
解 47x ≡ 15 (mod 73)。给出满足 0 < x < 73 的解 x。
47x ≡ 15 (mod 73)
x =
4.中等
求 43 模 73 的逆元：满足 0 < x < 73 且 43·x ≡ 1 (mod 73) 的数 x。
a = 43n = 73
43−1 mod 73 =
5.困难
11 是素数。用费马小定理求 611405 mod 11。
p = 11k = 11405
611405 mod 11 =
6.困难
用 RSA 公钥 (n, e) = (85, 13) 加密消息 m = 77。求密文 c。
n = 85e = 13m = 77
c =
答案
- 1. lcm(342, 243) = 9234
- 2. gcd(1008, 777) = 21
- 3. x = 64
- 4. 43−1 mod 73 = 17
- 5. 611405 mod 11 = 10
- 6. c = 42
完整分步解答：请在 examproblems.com 上练习本主题。