1.简单
用欧几里得算法求 gcd(403, 221)。
a = 403b = 221
gcd(403, 221) =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(46, 43)。
a = 46b = 43
gcd(46, 43) =
3.中等
求 45 模 47 的逆元：满足 0 < x < 47 且 45·x ≡ 1 (mod 47) 的数 x。
a = 45n = 47
45−1 mod 47 =
4.中等
求 47 模 61 的逆元：满足 0 < x < 61 且 47·x ≡ 1 (mod 61) 的数 x。
a = 47n = 61
47−1 mod 61 =
5.困难
用 RSA 公钥 (n, e) = (559, 11) 加密消息 m = 200。求密文 c。
n = 559e = 11m = 200
c =
6.困难
用反复平方法求 1789 mod 19。
a = 17k = 89n = 19
1789 mod 19 =
答案
- 1. gcd(403, 221) = 13
- 2. gcd(46, 43) = 1
- 3. 45−1 mod 47 = 23
- 4. 47−1 mod 61 = 13
- 5. c = 528
- 6. 1789 mod 19 = 9
完整分步解答：请在 examproblems.com 上练习本主题。