1.简单
用欧几里得算法求 gcd(799, 459)。
a = 799b = 459
gcd(799, 459) =
数论与模运算练习卷（附答案）
2.简单
不要把大数乘开来求 485² mod 9：先取模化简。
n = 9
485² mod 9 =
3.中等
求满足 x ≡ 3 (mod 11) 和 x ≡ 11 (mod 12) 的最小正整数 x。
x ≡ 3 (mod 11)x ≡ 11 (mod 12)
x =
4.中等
解 33x ≡ 73 (mod 83)。给出满足 0 < x < 83 的解 x。
33x ≡ 73 (mod 83)
x =
5.困难
71 是素数。用费马小定理求 295743 mod 71。
p = 71k = 5743
295743 mod 71 =
6.困难
用反复平方法求 9180 mod 98。
a = 9k = 180n = 98
9180 mod 98 =
答案
- 1. gcd(799, 459) = 17
- 2. 485² mod 9 = 1
- 3. x = 47
- 4. x = 50
- 5. 295743 mod 71 = 36
- 6. 9180 mod 98 = 71
完整分步解答：请在 examproblems.com 上练习本主题。