1.简单
用欧几里得算法求 gcd(600, 408)。
a = 600b = 408
gcd(600, 408) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(741, 221)。先用欧几里得算法求最大公约数。
a = 741b = 221
lcm(741, 221) =
3.中等
求 45 模 47 的逆元：满足 0 < x < 47 且 45·x ≡ 1 (mod 47) 的数 x。
a = 45n = 47
45−1 mod 47 =
4.中等
求 11 模 19 的逆元：满足 0 < x < 19 且 11·x ≡ 1 (mod 19) 的数 x。
a = 11n = 19
11−1 mod 19 =
5.困难
用反复平方法求 4377 mod 57。
a = 43k = 77n = 57
4377 mod 57 =
6.困难
79 是素数。用费马小定理求 2695431 mod 79。
p = 79k = 95431
2695431 mod 79 =
答案
- 1. gcd(600, 408) = 24
- 2. lcm(741, 221) = 12597
- 3. 45−1 mod 47 = 23
- 4. 11−1 mod 19 = 7
- 5. 4377 mod 57 = 28
- 6. 2695431 mod 79 = 9
完整分步解答：请在 examproblems.com 上练习本主题。