1.简单
用欧几里得算法求 gcd(102, 16)。
a = 102b = 16
gcd(102, 16) =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(342, 60)。
a = 342b = 60
gcd(342, 60) =
3.中等
求欧拉函数 φ(88)，即 1 到 88 中与 88 互素的整数个数。
n = 88 = 23·11
φ(88) =
4.中等
求 10 模 67 的逆元：满足 0 < x < 67 且 10·x ≡ 1 (mod 67) 的数 x。
a = 10n = 67
10−1 mod 67 =
5.困难
解 6x ≡ 12 (mod 27)。给出最小的正解 x。
6x ≡ 12 (mod 27)
x =
6.困难
用反复平方法求 4141 mod 49。
a = 41k = 41n = 49
4141 mod 49 =
答案
- 1. gcd(102, 16) = 2
- 2. gcd(342, 60) = 6
- 3. φ(88) = 40
- 4. 10−1 mod 67 = 47
- 5. x = 2
- 6. 4141 mod 49 = 6
完整分步解答：请在 examproblems.com 上练习本主题。