1.简单
用欧几里得算法求 gcd(715, 403)。
a = 715b = 403
gcd(715, 403) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(238, 91)。先用欧几里得算法求最大公约数。
a = 238b = 91
lcm(238, 91) =
3.中等
求欧拉函数 φ(169)，即 1 到 169 中与 169 互素的整数个数。
n = 169 = 132
φ(169) =
4.中等
求欧拉函数 φ(363)，即 1 到 363 中与 363 互素的整数个数。
n = 363 = 3·112
φ(363) =
5.困难
用反复平方法求 16156 mod 69。
a = 16k = 156n = 69
16156 mod 69 =
6.困难
用反复平方法求 35110 mod 43。
a = 35k = 110n = 43
35110 mod 43 =
答案
- 1. gcd(715, 403) = 13
- 2. lcm(238, 91) = 3094
- 3. φ(169) = 156
- 4. φ(363) = 220
- 5. 16156 mod 69 = 49
- 6. 35110 mod 43 = 41
完整分步解答：请在 examproblems.com 上练习本主题。