高等算术习题(2) - 同余

Fri Dec 24, 2021

这是《高等算术》习题系列的第二篇。第二章讲了同余关系、同余方程、费马小定理、欧拉函数等。

2.1 求证：如果 $a \equiv b (\mod 2 n)$ ，则 $a^{2} \equiv b^{2} (\mod 4 n)$ 。更一般地，如果 $a \equiv b (\mod k n)$ ，则 $a^{k} \equiv b^{k} (\mod k^{2} n)$ 。

证明：仅对第二个命题给出证明；取 $k = 2$ 就可得到第一个命题。

根据 $a \equiv b (\mod k n)$ 可设 $\begin{aligned} a & = q_{1} (k n) + r \\ b & = q_{2} (k n) + r \end{aligned}$

则对 $a^{k}$ 用二项式定理展开有 $a^{k} = \sum_{i = 0}^{k} (\binom{k}{i}) [q_{1} (k n)]^{k - i} r^{i}$ 式中的每项 $(\binom{k}{i}) [q_{1} (k n)]^{k - i} r^{i}$ 当 $0 \leq i \leq k - 2$ 时具有因子 $(k n)^{2}$ ，因此可以被 $k^{2} n$ 整除；当 $i = k - 1$ 时为 $k q_{1} k n$ 也可以被 $k^{2} n$ 整除。所以写成同余式只留下最后一项 $a^{k} \equiv r^{k} (\mod k^{2} n)$

同理可证 $b^{k} \equiv r^{k} (\mod k^{2} n)$

所以 $a^{k} \equiv b^{k} (\mod k^{2} n)$ ，证明完毕。

2.2 哪些数字除以 3、4、5、6 得到相应的余数分别是 2、3、4、5？

解法一：设满足条件的数字为 $x$ ，则

$\begin{array}{r} (1) & x \equiv 2 (\mod 3) \\ (2) & x \equiv 3 (\mod 4) \\ (3) & x \equiv 4 (\mod 5) \\ (4) & x \equiv 5 (\mod 6) \end{array}$

由 $(1)$ 可知 $x = 3 p + 2$ ，代入 $(2)$ 得 $3 p \equiv 1 (\mod 4)$ 解得 $p \equiv 3 (\mod 4)$ 即 $x = 3 (4 q + 3) + 2 = 12 q + 11$ ，代入 $(3)$ 得 $12 q \equiv 3 (\mod 5)$ 解得 $q \equiv 4 (\mod 5)$ 即 $x = 12 (5 r + 4) + 11 = 60 r + 59$ ，代入 $(4)$ 得 $60 r \equiv 0 (\mod 6)$ 此为恒等式， $r$ 取任意整数皆可。

所以 $x = 60 r + 59.$

解法二：设满足条件的数字为 $x$ ，则

$\begin{array}{r} x + 1 \equiv 0 (\mod 3) \\ x + 1 \equiv 0 (\mod 4) \\ x + 1 \equiv 0 (\mod 5) \\ x + 1 \equiv 0 (\mod 6) \end{array}$

由此可知 3、4、5、6 都是 $(x + 1)$ 的因子，任何满足条件的 $x + 1$ 一定是 60 （3、4、5、6的最小公倍数）的整数倍，所以通解可以写成 $60 k - 1$ 。

2.4 求解同余方程 $97 x \equiv 13 (\mod 105)$ 。

解：方程等价于不定方程 $97 x - 105 y = 13$ ，可用欧几里得算法求解。

$\begin{array}{r} (1) & 105 = 97 \times 1 + 8 \\ (2) & 97 = 8 \times 12 + 1 \end{array}$

由 $(1)$ 得 $8 = 105 - 97$ ，代入 $(2)$ 得 $97 \times 13 - 105 \times 12 = 1.$ 方程两边同乘以 13 得 $97 \times 169 - 105 \times 156 = 13.$ 所以 $x \equiv 169 \equiv 64 (\mod 105)$ .

2.5 计算 (102⁷³+55)³⁷ 除以 111 的余数。

解： $111 = 3 \times 37$ 。首先考察该式除以 3 的余数。因为 102 能被 3 整除，所以 $102^{73} \equiv 0 (\mod 3)$ ，因此 $\begin{matrix} (1) & (102^{73} + 55)^{37} \equiv 55^{37} \equiv 1^{37} \equiv 1 (\mod 3) \end{matrix}$

然后考察原式除以 37 的余数。因为 $102 \equiv 28, 55 \equiv 18 (\mod 37)$ ，得 $\begin{matrix} (2) & (102^{73} + 55)^{37} \equiv 28 + 18 \equiv 9 (\mod 37) \end{matrix}$ 这里应用了费马小定理： $a^{72} \equiv a^{36} \equiv 1 (\mod 37)$ 。

根据 $(1)$ 设 $x = 3 q + 1$ ，代入 $(2)$ 得 $3 q \equiv 8 (\mod 37)$

注意到 $3 \times 12 \equiv - 1$ ，所以 $q \equiv - 12 \times 8 \equiv 15 (\mod 37)$ 。设 $q = 37 r + 15$ ，则 $x = 3 (37 r + 15) + 1 = 111 r + 46$ ，所以所要求的余数为 46。

2.11 求证： $n$ 是质数当且仅当 $σ (n) + ϕ (n) = n d (n) .$

证明：首先证明必要性。如果 $n$ 是质数，那么 $\begin{aligned} σ (n) & = n + 1 \\ ϕ (n) & = n - 1 \\ d (n) & = 2 \end{aligned}$ 由此可见等式成立。

下面证明充分性。当 $n = 1$ 时易知等式不成立。只须证明当 $n$ 是合数时等式不成立即可。根据算术基本定理可设 $n = \prod_{i = 1}^{N} p_{i}^{c_{i}}$ 其中 $p_{i}$ 是质数， $c_{i} \geq 1$ 。

设 $n_{i} = p_{i}^{c_{i}}$ ，则 $\begin{aligned} \frac{σ (n_{i})}{n_{i}} & = 1 + \frac{1}{p} + \dots + \frac{1}{p^{c_{i}}} \\ \frac{ϕ (n_{i})}{n_{i}} & = 1 - \frac{1}{p} \\ d (n_{i}) & = c_{i} + 1 \end{aligned}$ 于是 $\begin{aligned} \frac{σ (n_{i}) + ϕ (n_{i})}{n_{i}} & = 2 + \frac{1}{p^{2}} + \dots + \frac{1}{p^{c_{i}}} \\ < 2 + \frac{1}{2^{2}} + \dots \\ < 2 + 1 = 3 \end{aligned}$ 当 $c_{i} = 1$ 时， $\frac{σ (n_{i}) + ϕ (n_{i})}{n_{i}} = d (n_{i}) = 2$ 。当 $c_{i} \geq 2$ 时， $d (n_{i}) = c_{i} + 1 \geq 3$ 。综上可知 $\begin{matrix} (1) & σ (n_{i}) + ϕ (n_{i}) \leq n_{i} d (n_{i}) \end{matrix}$ 当且仅当 $c_{i} = 1$ 时取“=”。

考虑 $\prod_{i = 1}^{N} [σ (n_{i}) + ϕ (n_{i})]$ 的展开，展开后每项都是正数，如果只保留全是 $σ$ 和全是 $ϕ$ 的两项，可得不等式 $\begin{matrix} (2) & \prod_{i = 1}^{N} [σ (n_{i}) + ϕ (n_{i})] \geq \prod_{i = 1}^{N} σ (n_{i}) + \prod_{i = 1}^{N} ϕ (n_{i}) \end{matrix}$ 当且仅当 $N = 1$ 时取“=”。

另一方面，根据函数的积性可知 $\begin{aligned} \prod_{i = 1}^{N} σ (n_{i}) & = σ (n) \\ \prod_{i = 1}^{N} ϕ (n_{i}) & = ϕ (n) \\ \prod_{i = 1}^{N} n_{i} d (n_{i}) & = n d (n) \end{aligned}$ 综合 $(1)$ 、 $(2)$ 得 $σ (n) + ϕ (n) \leq \prod_{i = 1}^{N} [σ (n_{i}) + ϕ (n_{i})] \leq \prod_{i = 1}^{N} n_{i} d (n_{i}) = n d (n) .$

因为 $n$ 是合数，所以上式中的等号不可能同时取得，所以等式 $σ (n) + ϕ (n) = n d (n)$ 不能成立。

证明完毕。

2.12 求证：

如果 $p$ 是奇质数，那么 $(p - 2)! \equiv 1 (\mod p)$ ；
如果 $p > 3$ 是质数，那么 $(p - 3)! \equiv (p - 1) / 2 (\mod p)$ 。

证明：

根据 Wilson 定理， $(p - 1)! \equiv p - 1 (\mod p)$ 。因为 $(p - 1)$ 和 $p$ 互质，所以可以约去 $(p - 1)$ ，得 $(p - 2)! \equiv 1 (\mod p)$ 。
因为 $(p - 2) \frac{p - 1}{2} = \frac{p - 3}{2} p + 1 \equiv 1 (\mod p)$ 所以在前一问的基础上两边同乘以 $(p - 1) / 2$ 即可。

2.13 如果 $p$ 是奇质数，且 $a + b = p - 1$ ，证明 $a! b! + (- 1)^{a} \equiv 0 (\mod p)$ 。

证明：

由 $\begin{aligned} 1 & \equiv - (p - 1) (\mod p) \\ 2 & \equiv - (p - 2) (\mod p) \\ ⋮ \\ a & \equiv - (p - a) (\mod p) \end{aligned}$ 得 $\begin{matrix} (1) & a! \equiv (- 1)^{a} (p - 1) (p - 2) \dots (p - a) (\mod p) . \end{matrix}$

另一方面， $\begin{matrix} (2) & b! = (p - 1 - a)! = \frac{(p - 1)!}{(p - 1) (p - 2) \dots (p - a)} . \end{matrix}$

综合 $(1)$ 、 $(2)$ 得 $a! b! \equiv (- 1)^{a} (p - 1)! (\mod p) .$

根据 Wilson 定理， $(p - 1)! \equiv - 1$ ，所以 $a! b! \equiv - (- 1)^{a}$ ，即 $a! b! + (- 1)^{a} \equiv 0 (\mod p)$ 。

2.15 求解同余方程 $x^{2} \equiv 17 (\mod 128)$ 。

解：枚举 64 以内所有自然数即可（一个正数解对应一个负数解）。为了缩小枚举范围，可以考虑以下条件：

17 不是完全平方数，所以不必枚举 12 以下的数。
只须枚举奇数即可，偶数显然不满足条件。
如果 $x$ 是一个解，那么 $(64 - x)$ 也是一个解，所以枚举不超过 32 的数即可。

枚举得 $23^{2} = 529 \equiv 17 (\mod 128)$ 所以方程的解是 $x \equiv \pm 23, x \equiv \pm 41 (\mod 128)$ 。

2.16 求解模 19 的同余方程（或证明方程无解）：

$x^{3} \equiv 3$ ,
$x^{3} \equiv 7$ ,
$x^{3} \equiv 11$ .

解：列出 $y = x^{3}$ 在模 19 算术下的表格：

x| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|17|18|
y| 0| 1| 8| 8| 7|11| 7| 1|18| 7|12| 1|18|12| 8|12|11|11|18|

由此可知：

$x^{3} \equiv 3$ 无解；
$x^{3} \equiv 7$ 的解是 $x \equiv 4, 6, 9$ ；
$x^{3} \equiv 11$ 的解是 $x \equiv 5, 16, 17$ 。