1.简单
不要把大数乘开来求 989² mod 5：先取模化简。
n = 5
989² mod 5 =
数论与模运算练习卷（附答案）
2.简单
用欧几里得算法求 gcd(324, 264)。
a = 324b = 264
gcd(324, 264) =
3.中等
求欧拉函数 φ(441)，即 1 到 441 中与 441 互素的整数个数。
n = 441 = 32·72
φ(441) =
4.中等
求 29 模 75 的逆元：满足 0 < x < 75 且 29·x ≡ 1 (mod 75) 的数 x。
a = 29n = 75
29−1 mod 75 =
5.困难
解 49x ≡ 21 (mod 70)。给出最小的正解 x。
49x ≡ 21 (mod 70)
x =
6.困难
某个 RSA 密钥使用 p = 43，q = 47，e = 5。解密密文 c = 832：求消息 m。
p = 43q = 47e = 5c = 832
m =
答案
- 1. 989² mod 5 = 1
- 2. gcd(324, 264) = 12
- 3. φ(441) = 252
- 4. 29−1 mod 75 = 44
- 5. x = 9
- 6. m = 599
完整分步解答：请在 examproblems.com 上练习本主题。