1.简单
求 173 mod 6，即满足 0 ≤ r < 6 的余数 r。
a = 173n = 6
173 mod 6 =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(472, 136)。
a = 472b = 136
gcd(472, 136) =
3.中等
求 3 模 17 的逆元：满足 0 < x < 17 且 3·x ≡ 1 (mod 17) 的数 x。
a = 3n = 17
3−1 mod 17 =
4.中等
求满足 x ≡ 5 (mod 6) 和 x ≡ 0 (mod 11) 的最小正整数 x。
x ≡ 5 (mod 6)x ≡ 0 (mod 11)
x =
5.困难
53 是素数。用费马小定理求 756230 mod 53。
p = 53k = 56230
756230 mod 53 =
6.困难
71 是素数。用费马小定理求 759096 mod 71。
p = 71k = 59096
759096 mod 71 =
答案
- 1. 173 mod 6 = 5
- 2. gcd(472, 136) = 8
- 3. 3−1 mod 17 = 6
- 4. x = 11
- 5. 756230 mod 53 = 47
- 6. 759096 mod 71 = 19
完整分步解答：请在 examproblems.com 上练习本主题。