哈代数论读书笔记(二)——素数(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 年,PervusinSeelhoff 更正了一个错误,证明 $M_{61}$ 是素数

1951 年,Ferrier 仅仅借助简单计算器发现了一个更大的梅森素数,同时,MillerWheeler 利用 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(数的模系统)

值得注意的是,在英文中,modulimodulus 的复数形式

一个模系统 $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}$ 不可能成立,所以奇异数是不存在的,证毕

此条目发表在数学, 数论分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注