第二章 素数(2)

---

1、First proof of Eucid's second theorem

Euclid(欧几里得) 本人对定理的证明如下：

设全部的素数为 $2,3,5,\cdots,p$ ，令

$q=2\cdot 3\cdot 5 \cdots p +1$

那么 $q$ 不能被 $2,3,5,\cdots,p$ 中任何一个数整除

所以 $q$ 要么是个质数，要么被 $p,q$ 间的一个质数整除

两种情况下都存在一个大于 $p$ 的质数，所以素数是无限的

这个定理等价于

$\pi(x)\rightarrow\infty$

---

2、Further deductions(更深层的探究)

如果 $p$ 是第 $n$ 个质数 $p_n$，$q$ 还是按照上面的定义，那么

$q<p_n^n+1$

当 $n>1$ 时，有

$p_{n+1}\leq q<p_n^n+1$

这个式子启发我们去找到 $p_n$ 的一个上界，以及 $\pi(x)$ 的一个下界

接下来我们用数学归纳法证明

$p_n<2^{2^n}$

首先，$p_1=2<4=2^{2^1}$

其次，假设 $p_k<2^{2^k}$ 成立，那么

$p_{k+1}\leq p_1 p_2 \cdots p_{k}+1<2^{2+4+\cdots+2^k}+1<2^{2^{k+1}}$

这样我们就完成了证明

我们取

$e^{e^{n-1}}<x\leq e^{e^n}$

由于当 $n\geq 4$ 时，有

$e^{n-1}>2^n\Rightarrow e^{e^{n-1}}>2^{2^n}$

所以

$\pi(x)\geq\pi(e^{e^{n-1}})\geq\pi(2^{2^n})\geq\pi(p_n)\geq n$

由于 $\log{\log{x}}\leq n$，所以

$\pi(x)\geq \log{\log{n}}$

对于 $x>e^{e^{3}}$ 都成立，经过验证，我们发现对于 $2\leq x\leq e^{e^{3}}$ 同样成立

因此，我们就证明了下面的定理：

Theorem 10
$\pi(x)\geq \log{\log{n}}\quad (x\geq 2)$

虽然这个下界极其的粗略，但是我们总算找到了一个

---

3、Primes in certain arithmetical progressions(等差序列中的素数)

欧几里得的结论可以从其它方向进行扩展

Theorem 11
形如 $4n+3$ 的素数是无限的

设

$q=2^2\cdot 3\cdot 5\cdots p-1$

那么显然 $q$ 是 $4n+3$ 的形式，且没有小于等于 $p$ 的素因子

由于两个 $4n+1$ 形式的数相乘必然也是 $4n+1$ 的形式，因此 $q$ 不可能仅由 $4n+1$ 形式的数相乘得到，所以 $q$ 有一个 $4n+3$ 形式的大于 $p$ 的素因子，证毕

Theorem 12
形如 $6n+5$ 的素数是无限的

证明是类似的，设

$q=2\cdot 3\cdot 5\cdots p-1$

考察所有的质数，我们发现除了 $2,3$ 之外，都可以写成 $6n+1$ 或 $6n+5$ 的形式

而两个形如 $6n+1$ 的数乘积也是 $6n+1$ 的形式，按照之前的方法推理即可

但是要证明形如 $4n+1$ 的素数的情况就有些困难了

我们要借助接下来的定理，并且我们会在第二十章证明它

Theorem 13
如果 $a,b$ 没有相同的因子，那么 $a^2+b^2$ 的所有奇质因子是 $4n+1$ 的形式

有这个定理作为前提，我们就能证明 $4n+1$ 型质数是无限的，更强的，我们可以证明：

Theorem 14
形如 $8n+5$ 的素数是无限的

我们设

$q=3^2\cdot 5^2\cdot 7^2\cdots p^2+2^2$

加号两边是一对没有相同因子的完全平方数，我们发现

$(2m+1)^2=4m(m+1)+1$

即一个奇数的平方可以写成 $8n+1$ 的形式，所以 $q$ 是 $8n+5$ 的形式

由 Theorem 13 可知，$q$ 的所有质因子都是 $4n+1$ 的形式，即 $8n+1$ 或 $8n+5$ 的形式

而两个 $8n+1$ 型的乘积必然是 $8n+1$ 型，所以按照之前的思路就完成了证明

事实上，上面的定理都是 Dirichlet(狄利克雷) 的一个著名定理的特殊情况

Theorem 15（Dirichlet Theorem）
若 $a$ 是正数，且 $a,b$ 没有大于 $1$ 的公共因子，那么形如 $an+b$ 的素数是无限的

这个定理的证明过程非常复杂，所以本书没有给出，不过 $b=\pm 1$ 的情形要简单的多

---

4、Second proof of Euclid's theorem

欧几里得第二定理的第二个证明由 P$\acute{o}$lya 给出，基于 Fermat's numbers(费马数) 的理论

费马数的定义为：

$F_n=2^{2^n}+1$

那么我们可以写出

$F_1=5,\quad F_2=17,\quad F_3=257,\quad F_4=65537$

费马数有不少有趣的用途，比如，Gauss(高斯) 证明了，如果 $F_n$ 是素数，那么 $F_n$ 条边的圆内接 regular polygon(正多边形) 可以通过 Fuclidean method(尺规作图) 作出

费马数有一条非常重要的性质：

Theorem 16
不存在两个具有相同因子（大于1）的费马数

假设存在 $F_n,F_{n+k}(k>0)$ 且

$m|F_n,\quad m|F_{n+k}$

设 $x=2^{2^n}$，那么

$\frac{F_{n+k}-2}{F_n}=\frac{2^{2^{n+k}}-1}{2^{2^n}+1}=\frac{x^{2^k}-1}{x+1}=x^{2^k-1}-x^{2^k-2}+\cdots -1$

所以 $F_n\mid (F_{n+k}-2)$，所以

$m|F_{n+k},\quad m|(F_{n+k}-2)$

因此，$m|2$，由于 $F_n$ 是奇数，所以 $m=1$，证毕

由 Theorem 16 可知，$F_1,F_2,\cdots,F_n$ 每个数都有一个属于自己的奇质因子，这个因子不是其他数的因子，所以不超过 $F_n$ 范围内至少有 $n$ 个奇质因子，这样就证明了欧几里得定理

同样的

$p_{n+1}\leq F_n=2^{2^n}+1$

可以得到一个比 Theorem 10 稍微强一点的下界

---

5、Fermat's and Mersenne's numbers(费马数和梅森数)

开始的四个费马数是素数，所以费马猜测所有的费马数都是质数

不幸的是，Euler(欧拉) 在 1732 年证明了 $F_5=2^{2^5}+1$ 是合数

由于

$641=5^4+2^4=5\times 2^7+1$

因此

$641|(5^4\times 2^{28}+2^{32}),\quad 641|(5^4\times2^{28}-1)$

作差得到：

$641|(2^{32}+1),\quad 641|F_5$

更准确地，

$F_5=2^{2^5}+1=641\times 6700417$

1880 年，Landry 证明了

$F_6=2^{2^6}+1=274177\times 67280421310721$

后来经过计算机证明，许多 $F_n$ 都是合数

随着证明的推进，我们发现从概率学的角度分析，费马素数 $F_n$ 很可能是有限的

根据素数定理，我们知道 $n$ 是素数的概率最大为

$\frac{A}{\log{n}}（A为常数）$

那么费马素数的期望个数最大为

$E(F_n)=A\sum_{n=1}^{+\infty} \frac{1}{\log{(2^{2^n}+1)}}<A\sum_{n=1}^{+\infty}2^{-n}<A$

从期望的角度来讲，费马素数是有限的，但是期望分析并不是严谨的证明

假设这个结论是对的，那么素数 $2^n+1$ 也是有限的，因为我们可以证明下面的定理：

Theorem 17
如果 $a^n+1(a>1)$ 是质数，那么 $a$ 是偶数，且 $n=2^m$

如果 $a$ 是奇数，那么 $a^n+1$ 必是偶数，不可能是质数

如果 $n$ 有一个奇因子 $k$，设 $n=kl$，那么

$\frac{a^{kl+1}}{a^l+1}=a^{(k-1)l}-a^{(k-2)l}+\cdots+1$

即 $a^n+1$ 不是质数，证毕

和该定理形式差不多的另一个定理是：

Theorem 18
如果 $a^n-1(n>1)$ 是质数，那么 $a=2$ 且 $n$ 是质数

如果 $a>2$，那么 $(a-1)|(a^n-1)$

如果 $n=kl$，那么 $(2^k-1)|(2^n-1)$，证毕

由该定理，$a^n-1$ 的素性由 $a^p-1$ 的素性决定，Mersenne(梅森) 定义

$M_p=2^p-1（p是素数）$

1876 年，Lucas(卢卡斯) 发现了一个测试 $M_p$ 素性的方法，并发现了 $M_{127}$ 是质数

1886 年，Pervusin 和 Seelhoff 更正了一个错误，证明 $M_{61}$ 是素数

1951 年，Ferrier 仅仅借助简单计算器发现了一个更大的梅森素数，同时，Miller 和 Wheeler 利用 EDSAC 1 电子计算机发现了更大的梅森素数

$180M_{127}^2+1$

我们将在第十五章介绍卢卡斯的判别法

梅森素数和 Prefect numbers(完美数) 联系紧密，我们将在第十六章介绍

---

6、Third proof of Euclid's theorem

设前 $j$ 个素数为

$2,3,5,\cdots,p_j$

$N(x)$ 表示不超过 $x$ 的且不含大于 $p_j$ 的素因子的数的个数

那么我们可以把 $n$ 表示为

$n=n_1^2 m$

其中 $m$ 是一个 square free(无平方因子) 数，我们有

$m=2^{b_1}3^{b_2}\cdots p_j^{b_j}$

其中 $b_j$ 为 $0$ 或 $1$，那么显然 $m$ 的取值最多有 $2^j$ 种

另外 $n_1\leq \sqrt{x}$，即 $n_1$ 的取值最多有 $\sqrt{x}$ 种

因此

$N(x)\leq 2^j\sqrt{x}$

如果素数是有限的，那么设所有的素数为 $2,3,5,\cdots,p_j$

那么对于所有的 $x$ 都应该有 $N(x)=x$，即

$x=N(x)\leq 2^j\sqrt{x}\Rightarrow x\leq 2^{2^j}$

这对于 $x>2^{2^j}$ 是不成立的，所以素数是无限的

利用这种思想可以证明一些更深刻的定理

Theorem 19
素数级数
$\sum\frac{1}{p}=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\cdots$
是发散的

如果该级数 convergent(收敛)，那么由柯西收敛准则，存在一个 $j$ 使得

$\frac{1}{p_{j+1}}+\frac{1}{p_{j+2}}+\cdots<\frac{1}{2}$

我们知道在 $[1,x]$ 中能被 $p$ 整除的数最多有 $\frac{x}{p}$ 个

所以在 $[1,x]$ 中能被 $p_{j+1},p_{j+2},\cdots$ 中的一个整除的数的个数 $x-N(x)$ 最多为

$x-N(x)<\frac{x}{p_{j+1}}+\frac{x}{p_{j+2}}+\cdots<\frac{1}{2}x$

因此下式恒成立

$\frac{1}{2}x<N(x)\leq 2^j\sqrt{x},\quad x<2^{2j+2}$

而对于 $x\geq 2^{2j+2}$ ，该式子不成立，所以不存在这样的 $j$，级数 diverage(发散)

Theorem 20
$\pi(x)\geq\frac{\log{x}}{2\log{2}}(x\geq 1),\quad p_n\leq 4^n$

我们取 $j=\pi(x)$，那么 $p_{j+1}>x$，所以 $N(x)=x$，故有

$x=N(x)\leq 2^{\pi(x)}\sqrt{x}$

$2^{\pi(x)}\geq x$

两边取对数就证明了 $\pi(x)$ 的下界，取 $x=p_n$ 就证明了 $p_n$ 的上界

该定理给出的上下界比 $Theorem 10$ 精致了不少，但依旧用处不大

---

7、Further results on prime formules(素数公式的更多结果)

回顾上一章提出的问题，我们要寻求生成素数的几种公式

（1）寻求一个函数 $f(n)=p_n$，这个问题上一章讨论过了

（2）寻求一个函数 $f(n)$，函数值都是素数，目前该问题没有解决

但是一个可能的想法是构造一个多元多项式函数，其正值都是素数，负值都是合数

关于这个问题，我们已经取得了一些结果：

Theorem 21
不存在整系数多项式函数 $f(n)$（不是常函数），使得所有函数值都是素数

不妨设最高次项系数为正，那么 $f(n)\rightarrow +\infty(n\rightarrow +\infty)$

因此存在一个 $N$ ，当 $n>N$ 时，$f(n)>1$

设 $x>N$，且

$f(x)=a_0 x^k+\cdots =y>1$

那么

$f(x+ry)=a_0 (x+ry)^k+\cdots$

对于所有 $r$ ，有 $y|f(x+ry)$ ，因此 $f(n)$ 的函数值有无限多的合数

更一般的，我们将在第六章证明如下定理：

Theorem 22
若
$f(n)=P(n,2^n,3^n,\cdots,k^n)$
是整系数多元多项式函数，且 $f(n)\rightarrow\infty(n\rightarrow\infty)$，那么 $f(n)$ 的函数值中有无穷多个合数

如果不满足 $f(n)\rightarrow\infty(n\rightarrow\infty)$，比如说

$f(n)=2^n 3^n-6^n+5$

它的函数值是一个常数，不满足该定理

---

8、Unsolved problems(悬而未决的难题)

有很多命题，我们以经验为依据判断它们是正确的，但是我们尚未给出严格的证明

（1）形如 $n^2+1$ 的素数是无限的

更一般地问题是

（2）若 $a,b,c$ 没有公因子，$a$ 是正数，$a+b$ 和 $c$ 不同时为偶数，$b^2-4ac$ 不是完全平方数，那么形如 $an^2+bn+c$ 的素数是无限的

解释一下这些限制条件：

设

$N=an^2+bn+c$

如果 $a+b$ 和 $c$ 都是偶数，那么 $N$ 必为偶数，不可能为 $2$ 以外的质数

如果 $b^2-4ac=k^2$，那么

$4aN=(2an+b)^2-k^2$

只有当 $2an+b+k$ 和 $2an+b-k$ 中有一个整除 $4a$ 时，$N$ 才有可能是素数，而这样的 $n$ 是有限的

（3）$n^2$ 与 $(n+1)^2$ 之间至少有一个素数

接下来是著名的 Goldbach's theorem(哥德巴赫定理)

（4）大于 $4$ 的偶数总能表示为两个奇素数的和

（5）大于 $9$ 的奇数总能表示为三个奇素数的和

（6）费马素数 $F_n$ 是有限的

---

9、Moduli of integers(整数的模系统)

我们现在给出 Theorem 2 和 3 的证明，证明过程依赖于 modulus of numbers(数的模系统)

值得注意的是，在英文中，moduli 是 modulus 的复数形式

一个模系统 $S$ 是满足下面条件的运算系统

$m\in S,n\in S\rightarrow(m\pm n)\in S$

模系统中的数不必是整数或有理数，它们可以是复数，甚至 quaternions(四元数)

但是接下来我们仅仅考虑整数的模系统

仅由 $0$ 组成的模系统为 null modulus(空模系统)

根据 $S$ 的定义，我们发现

$a\in S\rightarrow 0=a-a\in S,2a=a+a\in S$

重复这一过程得到 $na\in S(n\in Z)$

所以更一般地定义即为

$a\in S,b\in S\rightarrow xa+by\in S(x,y\in Z)$

另一方面，如果给定了 $a,b$，那么我们可以用 $ax+by$ 描述一个模系统

我们发现，任何一个模系统（除了空模系统）都有一些数是正的

设 $d$ 是这些正数中最小的，$n$ 是 $S$ 中的一个数，那么 $n-zd\in S$

如果 $c$ 是 $n$ 除以 $d$ 的余数，即

$n=zd+c(0\leq c<d)$

那么显然 $c\in S$，由于 $d$ 是 $S$ 中最小的正数，所以 $c=0$，因此 $d|n$，所以我们有

Theorem 23
除了空模系统的任何模系统，都是一个正整数 $d$ 的整数倍的集合

我们定义最大公约数 $d=(a,b)$ 表示 $a,b$ 的最大公因子，特别地，$(0,a)=|a|$

对于更多的数也是类似的定义为

$(a,b,c,\cdots,k)$

那么 Theorem 23 可以更准确地描述为

Theorem 24
任何模系统 $ax+by$ 都是 $d=(a,b)$ 的整数倍的集合

顺便的，我们可以得到

Theorem 25
方程
$ax+by=n$
有整数解 $x,y$，当且仅当 $d|n$

以及

Theorem 26
$a,b$ 的任何一个公因数都是最大公因数 $d$ 的倍数

---

10、Proof of the Fundamental theorem of arithmetic

通过第一章我们知道只要证明了 Theorem 3，就可以证明 Theorem 2

接下来我们来证明 Theorem 3

设质数 $p|ab$，若$p\nmid a$，那么 $(a,p)=1$，所以方程

$xa+yp=1\Rightarrow xab+ypb=b$

有整数解，而 $p|ab,p|pb$，所以 $p|b$

用同样的方法我们可以证明

Theorem 27
$(a,b)=d\Rightarrow (ac,bc)=dc（c>0）$

由于方程 $ax+by=d$ 有整数解，所以 $acx+bcy=dc$ 有整数解，因此 $(ac,bc)|dc$

另一方面

$d|a,d|b\Rightarrow dc|ac,dc|bc$

根据 Theorem 26，$dc|(ac,bc)$，因此 $(ac,bc)=dc$

---

11、Another proof of the Fundamental theorem

我们定义一个数是 abnormal(奇异的) 表示该数有两种及以上质因子分解式

设 $n$ 是最小的奇异的数，那么素数 $P$ 不能同时出现在 $n$ 的两种质因子分解式中，否则 $n/P$ 也是奇异的，且小于 $n$，那么我们有

$n=p_1 p_2 p_3\cdots=q_1 q_2 q_3\cdots$

其中 $p,q$ 都是质数，且 $p,q$ 无交集

设 $p_1,q_1$ 分别是 $p,q$ 中最小的，由于 $n$ 是合数，所以 $p_1,q_1\leq \sqrt{n}$，且 $p_1\neq q_1$

故 $p_1 q_1<n$，设

$N=n-p_1q_1$

那么 $0<N<n$，由于 $n$ 是最小的奇异数，所以 $N$ 是非奇异的，只有一种分解式

由于 $p_1|n,q_1|n$，所以 $p_1|N,q_1|N$，所以 $p_1q_1|N$，所以 $p_1q_1|n$，所以 $p_1|\frac{n}{q_1}$

因为 $\frac{n}{q_1}<n$，所以 $\frac{n}{q_1}$ 只有一种分解式

$\frac{n}{q_1}=p_2 p_3\cdots$

由于 $p,q$ 没有交集，所以 $p_1|\frac{n}{q_1}$ 不可能成立，所以奇异数是不存在的，证毕