1.简单
用欧几里得算法求 gcd(333, 189)。
a = 333b = 189
gcd(333, 189) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(1392, 312)。先用欧几里得算法求最大公约数。
a = 1392b = 312
lcm(1392, 312) =
3.中等
求 39 模 67 的逆元：满足 0 < x < 67 且 39·x ≡ 1 (mod 67) 的数 x。
a = 39n = 67
39−1 mod 67 =
4.中等
求欧拉函数 φ(28)，即 1 到 28 中与 28 互素的整数个数。
n = 28 = 22·7
φ(28) =
5.困难
用反复平方法求 47124 mod 75。
a = 47k = 124n = 75
47124 mod 75 =
6.困难
某个 RSA 密钥使用 p = 19，q = 31，e = 13。解密密文 c = 565：求消息 m。
p = 19q = 31e = 13c = 565
m =
答案
- 1. gcd(333, 189) = 9
- 2. lcm(1392, 312) = 18096
- 3. 39−1 mod 67 = 55
- 4. φ(28) = 12
- 5. 47124 mod 75 = 31
- 6. m = 307
完整分步解答：请在 examproblems.com 上练习本主题。