高等算术习题(1) - 整数分解和质数

高等算术习题(1) - 整数分解和质数

Sun Dec 19, 2021

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

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

---

1.8 如果 p≥5 是质数，证明 1,2,⋯p−1 里所有不相等的两数的乘积之和能被 p 整除。

证明： ∑1≤i<j≤p−1ij=12[(∑k=1p−1k)2−∑k=1p−1k2]=12{[p(p−1)2]2−p(p−1)(2p−1)6}=p(p−1)(p+1)(3p−2)24

所以 p|24∑1≤i<j≤p−1ij.

因为 24=23×3 而 p≥5，所以 p∤24。 根据欧几里得引理，p∣∑1≤i<j≤p−1ij。

---

1.11 如果 2n−1 是质数，证明 n 是质数。反之是否成立？

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

2ab−1=xb−1=(x−1)(xb−1+xb−2+⋯+1)

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

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

反之不成立，举一反例即可：211−1=2047=23×89。

---

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

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

2(2r+1)s+1=x2r+1+1=(x+1)(x2r−x2r−1+⋯−x+1) 易知 1<x+1<x2r+1+1，所以 2n+1 有一个既不是 1 也不是它自身的因数，所以它不是质数。

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

反之不成立，举一反例即可： 225+1=4294967297=641×6700417。

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

---

1.13 如果 P1,P2 是两个偶完全数且 6<P1<P2，证明 P2>16P1。

补充说明：

1. 一个数的因子可以由这个数的质因子分解确定：N=p1c1p2c2⋯pncn 每个因子 pi 都可以取 0,1,2,…,ci 次方。因子之和 σ(N)=(1+p1+⋯+p1c1)⋯(1+pn+⋯+pncn)
2. 完全数 (perfect number) 指一个数的真因子之和等于这个数本身，即 σ(N)=2N。它的定义见于 I.5。对于偶完全数，它一定是 2k−1(2k−1) 的形式，其中 (2k−1) 为质数。书上未给出证明细节；可参考欧拉给出的证明，其中利用了 σ 函数的性质。

证明： 根据上述内容，可设 P1=2p−1(2p−1), P2=2q−1(2q−1)，其中 2p−1 和 2q−1 均为质数。由 6<P1<P2 可知 2<p<q。对两数作商：

P2P1=2q−p2q−12p−1>2q−p2q2p=4q−p

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

因此， P2P1>4q−p≥16，于是 P2>16P1。这就是所要证明的。

---

1.14 如果 p,q 是奇数质数，证明 paqb 不可能是完全数。

证明：不失一般性，设 p<q，则 p≥3,q≥5。

用反证法。假设 paqb 是完全数，由定义可知 σ(paqb)=(1+p+⋯+pa)(1+q+⋯+qb)=2paqb.

两边同时除以 paqb 得 (1)(1+1p+⋯+1pa)(1+1q+⋯+1qb)=2.

因为 1+1p+⋯+1pa≤1+13+⋯+13a<11−13=32,1+1q+⋯+1qb≤1+15+⋯+15b<11−15=54,

所以 (1) 式的左边 <3254=158<2= 右边，矛盾！所以假设不成立， paqb 不是完全数。证明完毕。

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

---

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

解： 使用欧几里得算法。

(1)355=113×3+16(2)113=16×7+1

由 (1) 得 16=355−113×3，代入 (2) 得 113×22−355×7=1.

所以一个解是 x0=22,y0=7。 设另一个解是 (x,y)，则 x−x0:y−y0=355:113，所以通解是

x=22+355n,y=7+113n.

---

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

解： 2501≈502=2500。取 512=2601=2501+100，所以 2501=512−102=61×41。

---

1.24 证明有无穷个质数具有 6k−1 的形式。

证明：用反证法。假设有 6k−1 形式的质数只有有限个，分别是 p1,p2,…,pn。设 N=6(p1p2⋯pn)−1,易知 N 不能被 2、3 或任意 pi 整除。

凡是大于 3 的质数只能是 6k±1 的形式，因为其他形式可以被 2 或 3 整除。 形如 6k+1 的数相乘总是得到形如 6k+1 的数，所以 N 一定有某个形如 6k−1 的质因子，但它们不是 p1,p2,…,pn 中的任何一个，于是得到了矛盾。

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

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

---