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

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

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

根据 \(a \equiv b \pmod{kn}\) 可设 \begin{align*} a &= q_1(kn) + r\\ b &= q_2(kn) + r\\ \end{align*}

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

同理可证 \[ b^k \equiv r^k \pmod{k^2n} \]

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

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

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

\begin{align*} x \equiv 2 \pmod 3\tag1\\ x \equiv 3 \pmod 4\tag2\\ x \equiv 4 \pmod 5\tag3\\ x \equiv 5 \pmod 6\tag4\\ \end{align*}

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

所以 \[x = 60r+59.\]

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

\begin{align*} x + 1\equiv 0 \pmod 3\\ x + 1\equiv 0 \pmod 4\\ x + 1\equiv 0 \pmod 5\\ x + 1\equiv 0 \pmod 6\\ \end{align*}

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

2.4 求解同余方程 \(97x \equiv 13 \pmod{105}\)。

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

\begin{align} 105 = 97 \times 1 + 8 \tag1\\ 97 = 8 \times 12 + 1 \tag2\\ \end{align}

由 \((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 \pmod{105}\).

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

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

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

根据 \((1)\) 设 \(x=3q+1\)，代入 \((2)\) 得 \[3q\equiv 8\pmod {37}\]

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

2.11 求证： \(n\) 是质数当且仅当\[\sigma(n) + \phi(n) = nd(n).\]

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

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

设 \(n_i = p_i ^ {c_i}\)，则 \begin{align*} \frac{\sigma(n_i)}{n_i} &= 1+\frac{1}{p}+\cdots+\frac{1}{p^{c_i}} \\ \frac{\phi(n_i)}{n_i} &= 1-\frac{1}{p} \\ d(n_i) &= c_i + 1 \\ \end{align*} 于是 \begin{align*} \frac{\sigma(n_i)+\phi(n_i)}{n_i} &= 2+\frac{1}{p^2}+\cdots+\frac{1}{p^{c_i}} \\ &< 2+\frac{1}{2^2}+\cdots \\ &< 2+1 = 3 \\ \end{align*} 当 \(c_i=1\) 时，\(\frac{\sigma(n_i)+\phi(n_i)}{n_i}=d(n_i)=2\)。 当 \(c_i\ge2\) 时， \(d(n_i)=c_i+1\ge 3\)。 综上可知 \[\sigma(n_i) + \phi(n_i) \le n_i d(n_i) \tag{1}\] 当且仅当 \(c_i=1\) 时取“=”。

考虑 \(\prod_{i=1}^N [\sigma(n_i)+\phi(n_i)]\) 的展开，展开后每项都是正数，如果只保留全是 \(\sigma\) 和全是 \(\phi\) 的两项，可得不等式 \[\prod_{i=1}^N [\sigma(n_i)+\phi(n_i)] \ge \prod_{i=1}^N \sigma(n_i) + \prod_{i=1}^N\phi(n_i)\tag{2}\] 当且仅当 \(N=1\) 时取“=”。

另一方面，根据函数的积性可知 \begin{align*} \prod_{i=1}^N \sigma(n_i) &= \sigma(n)\\ \prod_{i=1}^N \phi(n_i) &= \phi(n)\\ \prod_{i=1}^N n_id(n_i) &= nd(n)\\ \end{align*} 综合 \((1)\)、\((2)\) 得 \[\sigma(n) + \phi(n) \le \prod_{i=1}^N [\sigma(n_i)+\phi(n_i)] \le \prod_{i=1}^N n_i d(n_i) = nd(n).\]

因为 \(n\) 是合数，所以上式中的等号不可能同时取得，所以等式 \(\sigma(n) + \phi(n) = nd(n)\) 不能成立。

证明完毕。

2.12 求证：

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

证明：

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

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

证明：

由 \begin{align*} 1 &\equiv -(p-1) \pmod p \\ 2 &\equiv -(p-2) \pmod p \\ &\vdots\\ a &\equiv -(p-a) \pmod p \\ \end{align*} 得 \[a! \equiv (-1)^a (p-1)(p-2)\cdots (p-a) \pmod p. \tag{1}\]

另一方面， \[b! = (p-1-a)! = \frac{(p-1)!}{(p-1)(p-2)\cdots(p-a)}. \tag{2}\]

综合 \((1)\)、\((2)\) 得 \[a!b! \equiv (-1)^a (p-1)! \pmod p.\]

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

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

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

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

枚举得 \[23^2 = 529 \equiv 17\pmod {128}\] 所以方程的解是 \(x\equiv \pm23,\,x\equiv \pm41 \pmod {128}\)。

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

1. \(x^3\equiv 3\),
2. \(x^3\equiv 7\),
3. \(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|

由此可知：

1. \(x^3\equiv 3\) 无解；
2. \(x^3\equiv 7\) 的解是 \(x\equiv 4,6,9\)；
3. \(x^3\equiv 11\) 的解是 \(x\equiv 5,16,17\)。