1.简单
用欧几里得算法求 gcd(645, 255)。
a = 645b = 255
gcd(645, 255) =
数论与模运算练习卷（附答案）
2.简单
求最小公倍数 lcm(1026, 630)。先用欧几里得算法求最大公约数。
a = 1026b = 630
lcm(1026, 630) =
3.中等
求 32 模 67 的逆元：满足 0 < x < 67 且 32·x ≡ 1 (mod 67) 的数 x。
a = 32n = 67
32−1 mod 67 =
4.中等
求满足 x ≡ 3 (mod 7) 和 x ≡ 4 (mod 13) 的最小正整数 x。
x ≡ 3 (mod 7)x ≡ 4 (mod 13)
x =
5.困难
在 {0, 1, …, 65} 中，28x ≡ 8 (mod 66) 有多少个解 N？
28x ≡ 8 (mod 66)
N =
6.困难
某个 RSA 密钥使用 p = 19，q = 37，e = 23。解密密文 c = 96：求消息 m。
p = 19q = 37e = 23c = 96
m =
答案
- 1. gcd(645, 255) = 15
- 2. lcm(1026, 630) = 35910
- 3. 32−1 mod 67 = 44
- 4. x = 17
- 5. N = 2
- 6. m = 647
完整分步解答：请在 examproblems.com 上练习本主题。