1.简单
用欧几里得算法求 gcd(833, 221)。
a = 833b = 221
gcd(833, 221) =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(111, 45)。
a = 111b = 45
gcd(111, 45) =
3.中等
求 76 模 97 的逆元：满足 0 < x < 97 且 76·x ≡ 1 (mod 97) 的数 x。
a = 76n = 97
76−1 mod 97 =
4.中等
求欧拉函数 φ(196)，即 1 到 196 中与 196 互素的整数个数。
n = 196 = 22·72
φ(196) =
5.困难
解 36x ≡ 54 (mod 63)。给出最小的正解 x。
36x ≡ 54 (mod 63)
x =
6.困难
某个 RSA 密钥使用素数 p = 23 和 q = 29，公钥指数 e = 5。求私钥指数 d（0 < d < φ(n)）。
p = 23q = 29e = 5
d =
答案
- 1. gcd(833, 221) = 17
- 2. gcd(111, 45) = 3
- 3. 76−1 mod 97 = 60
- 4. φ(196) = 84
- 5. x = 5
- 6. d = 493
完整分步解答：请在 examproblems.com 上练习本主题。