数论与模运算：练习题及分步解答

1余数与同余

用 n 除 a 得到商 q 和余数 r：a = q·n + r，0 ≤ r < n。余数记作 a mod n。对于负数，商也为负：−3 = −1·7 + 4，所以 −3 mod 7 = 4。

当两个数除以 n 的余数相同，即 n 整除 a − b 时，它们对模 n 同余，记作 a ≡ b (mod n)。

每一步都可以对余数取模，使数字保持较小：

例如 47·58 mod 9：47 ≡ 2，58 ≡ 4，所以 47·58 ≡ 8 (mod 9)。

2欧几里得算法

最大公约数 gcd(a, b) 是同时整除两数的最大的数。欧几里得算法使用 gcd(a, b) = gcd(b, a mod b)：

1. 做除法：a = q·b + r。
2. 用 (b, r) 替换 (a, b)。
3. 重复直到余数为 0。最后一个非零余数就是最大公约数。

最小公倍数由此得出：lcm(a, b) = a·b / gcd(a, b)。

3逆元与扩展算法

a 模 n 的逆元是满足 a·x ≡ 1 (mod n) 的数 x。它存在当且仅当 gcd(a, n) = 1。

扩展欧几里得算法对 (n, a) 运行欧几里得算法，并为每个余数保留一个系数 t，使每个余数 r ≡ t·a (mod n)。开始时 n 的 t = 0，a 的 t = 1；每个新的 t 等于上两行的 t 减去 q 乘以上一行的 t。出现余数 1 时，它的 t 就是逆元。

有了逆元，同余式 a·x ≡ b (mod n) 的解为 x ≡ a⁻¹·b。当 d = gcd(a, n) 大于 1 时，若 d 整除 b 则有 d 个解，否则无解。

模数互素的两个同余式 x ≡ r₁ (mod m₁) 和 x ≡ r₂ (mod m₂) 在模 m₁·m₂ 下恰有一个解（中国剩余定理）。写成 x = r₁ + m₁k 并求解 k。

4模幂与 RSA

反复平方法可以快速计算 aᵏ mod n：把 k 写成二进制，通过平方并取模求出 a、a²、a⁴、a⁸、… mod n，再把对应二进制位为 1 的幂相乘。

费马小定理：对于不整除 a 的素数 p，aᵖ⁻¹ ≡ 1 (mod p)。因此指数可以对 p − 1 取模。

RSA 由两个素数 p 和 q 构造密钥：

1. n = p·q，φ(n) = (p − 1)(q − 1)。
2. 选取满足 gcd(e, φ(n)) = 1 的 e；(n, e) 是公钥。
3. 计算 d = e⁻¹ mod φ(n)：这是私钥。
4. 加密 c = mᵉ mod n；解密 m = cᵈ mod n。

欧拉函数 φ(n) 表示 1 到 n 中与 n 互素的数的个数：对素数 φ(p) = p − 1，φ(pᵏ) = pᵏ − pᵏ⁻¹，对互素的因数 φ 是积性的。

5常见错误

• 对负数给出负的余数：−17 mod 5 是 3，而不是 −2。
• 在第一个余数处就停止欧几里得算法，而不是在最后一个非零余数处。
• 忘记给扩展算法得到的负系数加上 n。
• 把 RSA 指数 d 对 n 取模，而不是对 φ(n) 取模。
• 用费马定理时，把指数对 p 取模，而不是对 p − 1 取模。

6考试题是什么样的

• 简单：最大公约数与余数。你要用欧几里得算法求最大公约数或最小公倍数，求负数的余数，并对和与积取模 n。
• 中等：逆元与同余式。你要用扩展算法求模逆元，解线性同余方程，用中国剩余定理合并两个同余式，并计算欧拉函数 φ(n)。
• 困难：模幂与 RSA。你要使用反复平方法和费马定理，解有多个解的同余方程，并求 RSA 的私钥指数、密文和解密后的消息。