最近在阅读 Harold Davenport 的《高等算术》。选做其中的一些习题加以巩固，并将解答记录在这里。凡是做了新的习题，只需更新这个页面。

第一章主要介绍了整数的一些运算性质、数学归纳法、整除、质数、唯一分解定理、欧几里得算法。

1.8 如果 \(p\ge5\) 是质数，证明 \(1,2,\cdots p-1\) 里所有不相等的两数的乘积之和能被 \(p\) 整除。

证明： \begin{align*} \sum_{1 \le i < j \le p-1} ij &= \frac{1}{2}\left[\left(\sum_{k=1}^{p-1} k\right)^2 - \sum_{k=1}^{p-1} k^2\right] \\ &= \frac{1}{2}\left\{\left[\frac{p(p-1)}{2}\right]^2 - \frac{p(p-1)(2p-1)}{6}\right\} \\ &= \frac{p(p-1)(p+1)(3p-2)}{24} \\ \end{align*}

所以 \[ p \mathrel{\Bigg|} 24\sum_{1 \le i < j \le p-1} ij. \]

因为 \(24=2^3\times3\) 而 \(p\ge 5\)，所以 \(p\not\mid 24\)。 根据欧几里得引理，\(p \mid \sum_{1 \le i < j \le p-1} ij\)。

1.11 如果 \(2^n-1\) 是质数，证明 \(n\) 是质数。反之是否成立？

解：\(n=1\) 时显然有 \(2^1-1=1\) 不是质数。 假设 \(n\) 是合数，那么 \(n=ab\), \(a,b>1\)。另设 \(x=2^a\)，则有

\begin{align*} 2^{ab}-1 &= x^b - 1 \\ &= \left(x-1\right)\left(x^{b-1}+x^{b-2}+\cdots+1\right) \\ \end{align*}

易知式中两个因子都是大于 1 的整数，所以 \(2^n-1\) 不是质数。

综上所述，当 \(n\) 不是质数时， \(2^n-1\) 不是质数。其逆否命题就是所要证明的。

反之不成立，举一反例即可：\(2^{11}-1 = 2047 = 23 \times 89\)。

1.12[+] 如果 \(2^n+1\) 是质数，证明 \(n\) 是 2 的幂。反之是否成立？

解：假设 \(n\) 不是 2 的幂，那么它一定有一个大于 1 的奇数因子。设 \(n=(2r+1)s\)，其中 \(r,s\ge1\)。另设 \(x=2^s\)，则有

\begin{align*} 2^{(2r+1)s} + 1 &= x^{2r+1} + 1 \\ &= (x+1)\left(x^{2r} - x^{2r-1} + \cdots - x + 1\right) \end{align*} 易知 \(1 < x+1 < x^{2r+1} + 1\)，所以 \(2^n+1\) 有一个既不是 1 也不是它自身的因数，所以它不是质数。

综上所述，当 \(n\) 不是 2 的幂时，\(2^n+1\) 不是质数。其逆否命题就是所要证明的。

反之不成立，举一反例即可： \(2^{2^5} + 1 = 4294967297 = 641 \times 6700417\)。

注：

1. \(n\) 不是 2 的幂并非只有这一种设法。通过研究若干个例子后找到规律，才选择了这样的设法使得证明可以进行下去。
2. 也可以用数学归纳法或者同余理论证明 \(x^{2r+1} + 1\) 能被 \(x + 1\) 整除。本章尚未讲到同余理论。
3. 寻找本问题的反例手工计算较为困难（尽管欧拉在 1732 年便给出了这样的反例），使用计算机则不难得到。

1.13 如果 \(P_1, P_2\) 是两个偶完全数且 \(6 < P_1 < P_2\)，证明 \(P_2 > 16P_1\)。

补充说明：

1. 一个数的因子可以由这个数的质因子分解确定：\(N = p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}\) 每个因子 \(p_i\) 都可以取 \(0, 1, 2, \ldots, c_i\) 次方。因子之和 \[\sigma(N) = \left(1+p_1+\cdots+p_1^{c_1}\right) \cdots \left(1+p_n+\cdots+p_n^{c_n}\right)\]
2. 完全数 (perfect number) 指一个数的真因子之和等于这个数本身，即 \(\sigma(N)=2N\)。它的定义见于 I.5。对于偶完全数，它一定是 \(2^{k-1}(2^k-1)\) 的形式，其中 \((2^k-1)\) 为质数。书上未给出证明细节；可参考欧拉给出的证明，其中利用了 \(\sigma\) 函数的性质。

证明： 根据上述内容，可设 \(P_1 = 2^{p-1}(2^p-1)\), \(P_2 = 2^{q-1}(2^q-1)\)，其中 \(2^p-1\) 和 \(2^q-1\) 均为质数。由 \(6 < P_1 < P_2\) 可知 \(2 < p < q\)。对两数作商：

\begin{align*} \frac{P_2}{P_1} &= 2^{q-p}\frac{2^q-1}{2^p-1} \\ &> 2^{q-p}\frac{2^q}{2^p} \\ &= 4^{q-p} \end{align*}

下面证明 \(q-p \ge 2\)。只须证明 \(q-p \ne 1\) 即可。使用反证法，假设 \(q-p = 1\)，那么 \(p\) 和 \(q\) 一定有一个是大于 2 的偶数，设它是 \(2m\;(m>1)\)，则 \(2^{2m}-1=(2^m+1)(2^m-1)\) 有两个大于 1 的因子，因此是一个合数，这样就和已知条件矛盾。所以 \(q-p \ne 1\)。

因此， \(\frac{P_2}{P_1} > 4^{q-p} \ge 16\)，于是 \(P_2 > 16P_1\)。这就是所要证明的。

1.14 如果 \(p, q\) 是奇数质数，证明 \(p^aq^b\) 不可能是完全数。

证明：不失一般性，设 \(p < q\)，则 \(p \ge 3,\,q \ge 5\)。

用反证法。假设 \(p^aq^b\) 是完全数，由定义可知 \[\sigma{\left(p^aq^b\right)} = \left(1+p+\cdots+p^a\right) \left(1+q+\cdots+q^b\right) = 2p^aq^b.\]

两边同时除以 \(p^aq^b\) 得 \begin{equation} \left(1+\frac{1}{p}+\cdots+\frac{1}{p^a}\right) \left(1+\frac{1}{q}+\cdots+\frac{1}{q^b}\right) = 2. \tag{1} \end{equation}

因为 \begin{align*} 1+\frac{1}{p}+\cdots+\frac{1}{p^a} &\le 1+\frac{1}{3}+\cdots+\frac{1}{3^a} < \frac{1}{1-\frac{1}{3}} = \frac{3}{2}, \\ 1+\frac{1}{q}+\cdots+\frac{1}{q^b} &\le 1+\frac{1}{5}+\cdots+\frac{1}{5^b} < \frac{1}{1-\frac{1}{5}} = \frac{5}{4}, \\ \end{align*}

所以 \((1)\) 式的左边 \(< \frac{3}{2}\frac{5}{4} = \frac{15}{8} < 2 =\) 右边，矛盾！所以假设不成立， \(p^aq^b\) 不是完全数。证明完毕。

注：

1. 这题我原本的想法是用反证法推出整除性或奇偶性的矛盾，但是我的证明中间犯了一个错误。按原来的思路，暂时找不到可行的证明。我没有往不等式放缩的方向考虑，所以没有自己想出正确的证明。看来 \(\sigma(p^a)/p^a < 1/(1-1/p)\) 是一个有用的不等式。
2. 题意应隐含了 \(p \ne q\)，否则质因子分解可以直接写成 \(p^{a+b}\)，并且只需要第一个不等式的放缩即可证明。

1.20 找出一个公式给出方程 \(113x-355y=1\) 的所有整数解。

解： 使用欧几里得算法。

\begin{align} 355&=113 \times 3 + 16 \tag 1\\ 113&=16 \times 7 + 1 \tag 2\\ \end{align}

由 \((1)\) 得 \(16=355-113\times3\)，代入 \((2)\) 得 \[113 \times 22 - 355 \times 7 = 1.\]

所以一个解是 \(x_0=22,\, y_0=7\)。 设另一个解是 \((x, y)\)，则 \(x-x_0 : y-y_0 = 355 : 113\)，所以通解是

\begin{align*} x &= 22 + 355n,\\ y &= 7 + 113n. \end{align*}

1.21 使用 Fermat 平方差法分解 2501。

解： \(2501 \approx 50^2 = 2500\)。取 \(51^2=2601=2501+100\)，所以 \(2501=51^2-10^2=61\times41\)。

1.24 证明有无穷个质数具有 \(6k-1\) 的形式。

证明：用反证法。假设有 \(6k-1\) 形式的质数只有有限个，分别是 \(p_1,p_2,\ldots,p_n\)。设 \[N=6(p_1p_2\cdots p_n)-1,\]易知 \(N\) 不能被 2、3 或任意 \(p_i\) 整除。

凡是大于 3 的质数只能是 \(6k \pm 1\) 的形式，因为其他形式可以被 2 或 3 整除。 形如 \(6k+1\) 的数相乘总是得到形如 \(6k+1\) 的数，所以 \(N\) 一定有某个形如 \(6k-1\) 的质因子，但它们不是 \(p_1,p_2,\ldots,p_n\) 中的任何一个，于是得到了矛盾。

综上所述，假设不成立，原命题成立。

注：

1. 这题和书上的例子的证明思路完全一样。
2. “形如 \(6k-1\)”也可以表述为“和 -1 同余\(\pmod6\)”。