1.简单
用欧几里得算法求 gcd(399, 343)。
a = 399b = 343
gcd(399, 343) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(697, 510)。先用欧几里得算法求最大公约数。
a = 697b = 510
lcm(697, 510) =
3.中等
求欧拉函数 φ(49)，即 1 到 49 中与 49 互素的整数个数。
n = 49 = 72
φ(49) =
4.中等
求满足 x ≡ 1 (mod 3) 和 x ≡ 5 (mod 7) 的最小正整数 x。
x ≡ 1 (mod 3)x ≡ 5 (mod 7)
x =
5.困难
解 28x ≡ 56 (mod 58)。给出最小的正解 x。
28x ≡ 56 (mod 58)
x =
6.困难
解 34x ≡ 28 (mod 66)。给出最小的正解 x。
34x ≡ 28 (mod 66)
x =
答案
- 1. gcd(399, 343) = 7
- 2. lcm(697, 510) = 20910
- 3. φ(49) = 42
- 4. x = 19
- 5. x = 2
- 6. x = 28
完整分步解答：请在 examproblems.com 上练习本主题。