1.简单
求 271 mod 4，即满足 0 ≤ r < 4 的余数 r。
a = 271n = 4
271 mod 4 =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(945, 609)。
a = 945b = 609
gcd(945, 609) =
3.中等
解 9x ≡ 29 (mod 31)。给出满足 0 < x < 31 的解 x。
9x ≡ 29 (mod 31)
x =
4.中等
求满足 x ≡ 2 (mod 10) 和 x ≡ 1 (mod 13) 的最小正整数 x。
x ≡ 2 (mod 10)x ≡ 1 (mod 13)
x =
5.困难
43 是素数。用费马小定理求 1116356 mod 43。
p = 43k = 16356
1116356 mod 43 =
6.困难
解 15x ≡ 10 (mod 40)。给出最小的正解 x。
15x ≡ 10 (mod 40)
x =
答案
- 1. 271 mod 4 = 3
- 2. gcd(945, 609) = 21
- 3. x = 17
- 4. x = 92
- 5. 1116356 mod 43 = 21
- 6. x = 6
完整分步解答：请在 examproblems.com 上练习本主题。