1.简单
用欧几里得算法求 gcd(84, 50)。
a = 84b = 50
gcd(84, 50) =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(204, 150)。
a = 204b = 150
gcd(204, 150) =
3.中等
求 31 模 67 的逆元：满足 0 < x < 67 且 31·x ≡ 1 (mod 67) 的数 x。
a = 31n = 67
31−1 mod 67 =
4.中等
求 19 模 83 的逆元：满足 0 < x < 83 且 19·x ≡ 1 (mod 83) 的数 x。
a = 19n = 83
19−1 mod 83 =
5.困难
73 是素数。用费马小定理求 781546 mod 73。
p = 73k = 81546
781546 mod 73 =
6.困难
用反复平方法求 9197 mod 41。
a = 9k = 197n = 41
9197 mod 41 =
答案
- 1. gcd(84, 50) = 2
- 2. gcd(204, 150) = 6
- 3. 31−1 mod 67 = 13
- 4. 19−1 mod 83 = 35
- 5. 781546 mod 73 = 27
- 6. 9197 mod 41 = 9
完整分步解答：请在 examproblems.com 上练习本主题。