1.简单
用欧几里得算法求 gcd(132, 57)。
a = 132b = 57
gcd(132, 57) =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(351, 333)。
a = 351b = 333
gcd(351, 333) =
3.中等
求欧拉函数 φ(221)，即 1 到 221 中与 221 互素的整数个数。
n = 221 = 13·17
φ(221) =
4.中等
求满足 x ≡ 6 (mod 7) 和 x ≡ 4 (mod 13) 的最小正整数 x。
x ≡ 6 (mod 7)x ≡ 4 (mod 13)
x =
5.困难
在 {0, 1, …, 31} 中，6x ≡ 24 (mod 32) 有多少个解 N？
6x ≡ 24 (mod 32)
N =
6.困难
用反复平方法求 45103 mod 79。
a = 45k = 103n = 79
45103 mod 79 =
答案
- 1. gcd(132, 57) = 3
- 2. gcd(351, 333) = 9
- 3. φ(221) = 192
- 4. x = 69
- 5. N = 2
- 6. 45103 mod 79 = 76
完整分步解答：请在 examproblems.com 上练习本主题。