1.简单
用欧几里得算法求 gcd(192, 68)。
a = 192b = 68
gcd(192, 68) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(527, 221)。先用欧几里得算法求最大公约数。
a = 527b = 221
lcm(527, 221) =
3.中等
求 3 模 23 的逆元：满足 0 < x < 23 且 3·x ≡ 1 (mod 23) 的数 x。
a = 3n = 23
3−1 mod 23 =
4.中等
解 23x ≡ 12 (mod 67)。给出满足 0 < x < 67 的解 x。
23x ≡ 12 (mod 67)
x =
5.困难
11 是素数。用费马小定理求 2735664 mod 11。
p = 11k = 35664
2735664 mod 11 =
6.困难
解 30x ≡ 12 (mod 69)。给出最小的正解 x。
30x ≡ 12 (mod 69)
x =
答案
- 1. gcd(192, 68) = 4
- 2. lcm(527, 221) = 6851
- 3. 3−1 mod 23 = 8
- 4. x = 18
- 5. 2735664 mod 11 = 9
- 6. x = 5
完整分步解答：请在 examproblems.com 上练习本主题。