神奇的素数

正一华光 2018-11-16

展开全文

数学里面最有趣的问题可能就得说是素数了。世界上最难的问题很多都与素数有关，而且素数又是如此简单的一个概念，只要是学过乘除法的人都能理解什么是素数。如果评选一个非常简单但又极端复杂的数学概念，估计非素数莫属。今天，我们就来谈谈素数到底为什么复杂、有趣，为什么上千年来引无数数学家竞折腰。

素数，就是除了1和它自身外，再没有其它因子的自然数。如果把1也看作一个特殊的素数，写出来素数的集合为{1，2，3，5，7，11，13，17，19，23，......}。下面开始谈谈有关素数的有趣且复杂的问题，这些问题有的早就得到了解决，有的则至今也没有解决，还有的很可能永远无法解决。

一、素数有无穷多个

从历史上人们认识到素数开始，第一个引发人们思考的问题就是素数到底有多少个？因为人们在从小到大不断列举素数的时候，很快就发现越大的素数越不容易找到，而且也相对越稀疏。那么是不是大到一定程度后，就不再有素数了呢？

熟悉数学的朋友们大概都知道，2000多年前的欧几里得就已经解决了这个问题，答案是素数有无穷多个。欧几里得的证明方法简单而优美，是数学历史上的非常经典的证明之一。证明思路如下（如果熟悉的朋友完全可以跳过不看）：

反证法，假设素数只有有限个，不妨设全部的素数为、、......、。
然后欧几里得构造了一个新的自然数M= $p_1\cdot p_2\cdot p_3\cdot ...\cdot p_n+1$ ，
显然M不能够被、、......、中的任何一个素数整除。
那么，要么M是一个素数，要么M可以被一个不在、、......、中的素数整除。
无论是哪种情况，说明都存在、、......、以外的新的素数。
这与假设、、......、为全部的素数矛盾。
这个矛盾说明，素数有有限个的假设是错误的，素数必然有无穷多个。

欧几里得是一个大数学家，他的这个证明相当的简捷优美，如果评选数学历史上最优美的十大证明，我想这个证明可以入选。

虽然我这个专栏中的文章还不算多，但是读过我的一些文章的朋友一定会知道，我不会只普及这么简单的知识和证明的。这个问题的证明方法现在超过100种，大部分证明只给出了“素数有无穷多个”这么一个普通的结论。我倒是愿意和大家分享一下下面这个证明方法，它给出了一个包含更多信息的结论。

熟悉级数基本知识的朋友肯定知道，全部自然数的倒数和是不收敛的，也就是说

$\sum_{i=1}^{\infty}{\frac{1}{i}}\rightarrow\infty$ ，可是对于完全平方数、完全立方数等数的倒数之和是收敛的，即

$\sum_{i=1}^{\infty}{\frac{1}{i^2}}$ 、 $\sum_{i=1}^{\infty}{\frac{1}{i^3}}$ 等都存在。事实上， $\forall s>1,\ \sum_{i=1}^{\infty}{\frac{1}{i^s}}$ 都收敛。我们现在要问的是，既然素数在很大后也日渐稀疏，虽然未必比 n^2 稀疏得快，全体素数的倒数之和是否收敛呢？如果不收敛，那么素数一定不会只有有限个。

200多年前的伟大数学家欧拉最早给出并证明了这个结论，全体素数的倒数之和不收敛。当然，欧拉的证明过于晦涩了一些，我们给出一个二十世纪匈牙利著名数学家Erdos关于全体素数倒数之和不收敛的优美证明。如果你愿意在阅读下面的证明之前认真思考一下这个问题，就会知道Erdos给出的证明真漂亮。

仍然是反证法。设 $i\in \{1,2,3,...\}\ ,\ p_i$ 为素数，且当i ，也就是说这个数列从小到大排列了全部素数。
假设 $\sum_{i=1}^{\infty}{\frac{1}{p_i}}$ 收敛，由于 $\frac{1}{p_i}$ 这个数列是递减的，因此一定可以找到一个足够大的自然数k满足 $\sum_{i\geq k+1}^{}{\frac{1}{p_i}}<\frac{1}{2}$ 。
我们把、、......、称为小素数，把 $p_{k+1}$ 、 $p_{k+2}$ 、...... 称为大素数。
下面我们任取一个自然数N，并把小于等于N的自然数分成两部分，一部分只有小素数作为其素因子，这样的数的个数记为；另一部分是包含有至少一个大素数作为其素因子的，这样的数的个数记为。显然，。

下面我们分别估计与，
（1）先来估计。设 $n\leq N$ 是一个只有小素数作为其素因子的自然数，把n进行质因数分解，然后将n写成两部分的乘积，一部分是单个小素数的乘积，另一部分是一个完全平方数，即 $n=a_n\cdot {b_n}^2$ 。这里面的就是单个小素数的乘积， ${b_n}^2$ 是那个完全平方数。
因为小素数一共有k个，因此可能的情况有种（即每个小素数要么有要么没有）；
又因为 ${b_n}^2\leq n\leq N$ ，所以 $b_n\leq \sqrt{N}$ ，也即至多有 $\sqrt{N}$ 种情况。
于是n最多可能的个数为 $2^k\cdot \sqrt{N}$ ，即
$N_s\leq 2^k\cdot \sqrt{N}$
（2）再来估计。在小于等于N的自然数中，包含有素因子 $p_{k+1}$ 的数有 $p_{k+1}$ 、 $2\cdot p_{k+1}$ 、 $3\cdot p_{k+1}$ 、......、 $m\cdot p_{k+1}$ ，其个数是 $\left[ \frac{N}{p_{k+1}} \right]$ （方括号表示取整数部分），其它大素数也一样。于是
$N_b\leq \sum_{i\geq k+1}^{}{\left[ \frac{N}{p_i} \right]} < \sum_{i\geq k+1}^{}{ \frac{N}{p_i} } = N\cdot\sum_{i\geq k+1}^{}{ \frac{1}{p_i} } < \frac{N}{2}$

由于 $N_b<\frac{N}{2}$ ，如果我们能够找到合适的N，使得 $N_s\leq \frac{N}{2}$ ，那么就会出现，这样与矛盾。
于是我们令 $N_s\leq 2^k\cdot \sqrt{N}\leq \frac{N}{2}$ ，得到
$\sqrt{N}\geq 2^{k+1}\Leftrightarrow N\geq 2^{2k+2}$
这样的N显然存在，取 $N=2^{2k+2}$ 即可。

这个矛盾说明假设错误，即全体素数的倒数之和不收敛。

既然全体素数的倒数之和不收敛，素数当然不会只有有限个。而且通过这个结论，我们还可以大概判断，素数分布大概的稀疏程度要比任意s>1时的 n^s 的分布还要密集些。这个结论其实是关于素数分布研究的一个非常重要的进展。

二、相邻素数的间隔

人们对素数的研究，最关键的就是希望得到素数分布的规律。最理想的情况是给出第n个素数的通项公式P(n)，起码也要知道素数分布大概的稀疏程度。那么我们从最基础的分布关系入手，看一下两个相邻素数的间隔会有多大？

一个很容易得到的结论就是，两个相邻素数的间隔是可以任意大的。这很容易证明。

构造一个连续自然数的数列，n!+2、n!+3、......、n!+(n-1)、n!+n，这个数列一共有n-1个连续自然数，而且这n-1个数必然都不是素数。
由于n是任取的，这说明两个连续素数的间隔可以任意大。

那么是不是说，两个相邻素数的间隔就完全不受控制，没有任何限制了呢？还真不是，否则素数分布就没有那么复杂了。100多年前的法国数学家Joseph Bertrand给出了一个猜想，那就是“到下一个素数的距离不可能大于我们出发的这个数”。换句话说，随便给出一个自然数n，从n+1开始到2n之间一定存在至少一个素数。

这个结论在1850年被俄罗斯数学家切比雪夫（Pafnuty Chebyshev）证明，后来的一些数学家给出过不断简化、精炼的证明方法。可遗憾的是，我认为所有的证明方法都不够简捷优美，考虑到我专栏的名字叫做“数学与逻辑之美”，既然这些证明都不够美，我就不在这里和大家赘述了。总之，这个结论是正确的，标准的数学表述如下：

对每个 $n\geq 1$ ，存在素数p满足 $n<p\leq 2n$ 。

关于素数的间隔，最有名的是孪生素数猜想。孪生素数是相差为2的两个素数，这是素数可能的最小间隔。孪生素数猜想说的是“孪生素数有无穷多组”。我们想象一下，素数分布越来越稀疏（前面已经说了，两个相邻素数的间隔可以任意的大），但是相差为最小间隔2的素数却总会不断出现，有无穷多对，是不是一种很神奇的现象！当然，孪生素数猜想尚未得到证明。目前最接近的进展是著名华人数学家张益唐于2013年证明的，存在无穷多对相差小于7000万的素数（当然，这个7000万是可以被优化的，据说现在已经优化到1000以内了）。如果我们认真思考一下素数分布，就会理解，无穷多对相差为有限间隔的素数同素数分布逐渐会无穷稀疏相比，无论这个间隔是2还是7000万，都同样令人震惊。

一个分布越来越稀疏的数列，居然不断的回到某个有限的间隔，甚至是最小间隔，这种现象很像随机数的特点，可是素数是一种完全确定的数。这也许正是素数的神奇之处吧。

三、素数有公式么

人们非常希望发现素数的规律，当然，素数是确定的，理论上讲必然有其规律，可是到今天为止，人们还无法给出素数的通项公式。或者不说通项公式，即使要求给出一个确保只能得到素数的公式，目前也没有足够有价值的结论。

最经典的一个关于素数公式的猜想是300多年前的民间数学家费马给出的，他猜想 $2^{2^n}+1$ 对于任意自然数n，其结果都是素数。由于这个数增长很快，费马仅仅验证了n为0、1、2、3、4这五种情形，得到的都是素数。1732年，大数学家欧拉证明，n为5时的费马数 $2^{2^5}+1=641×6700417$ 不再是素数。这说明费马的猜想是错误的。

后来不断有数学家试图给出必然得到素数的公式，也确实有一些这样的公式。下面给大家介绍一个相比较而言还挺有趣的素数公式，这个公式是1976年加拿大数学家杭斯伯格给出的，是一个关于自然数的二元函数，

设x，y是自然数，令，定义
$f(x,y)=\frac{y-1}{2}\cdot [\left| B^2-1 \right|-(B^2-1)]+2$

可以证明，这个公式给出的结果一定是素数。

下面，我们来简单分析一下这个公式。首先B肯定是一个整数（可能是负整数），那么 B^2 必然是一个非负整数。如果 $B^2\geq 1$ ，那么结果必然是 f(x,y)=2 ，当然是一个素数，但是没有什么意义。剩下的情况就只能是 B^2=0 ，此时得到的 f(x,y)=y+1 ，这个数会是个素数吗？

这种情况下，B=0，意味着 x(y+1)=y!+1 ，换句话说， y+1 整除 y!+1 。这里，我们引入一个著名的素数判定定理，叫做威尔森定理。

p是素数 $\Leftrightarrow p|(p-1)!+1$

就是说，如果p整除(p-1)!+1，那么p就是素数；否则p就是合数。按照威尔森定理，y+1整除y!+1，意味着y+1是素数，因此杭斯伯格的这个公式确实必然得到素数。

其实这个公式本身没有什么意义，只有你找到一个素数p，并把p-1作为y时，它才会得到这个素数p，否则得到的都是2。所以，这个必然得到素数的公式挺二的。

不过，我们应该更感兴趣的是威尔森定理。为什么p整除(p-1)!+1与p是素数等价呢？下面给出一个本人的证明。这个证明对于学过群理论的朋友们会非常容易理解，但是没有学过群论的朋友也不用着急，我下面的证明不是用群论的概念来表述的，没学过群论的朋友也一样看得懂。

一、先证明两个结论。
对于任意一个大于1的自然数n，将1、2、3、......、n-1这n-1个自然数中与n互质的全部m个数取出来构成集合M， $M=\{a|a\in N,\ 1\leq a<n,\ (a,n)=1\}=\{a_1,a_2,......,a_m\}$ 。
结论1：对于任意 $a_i\in M$ 都存在 $a_j \in M$ ，满足 $a_i\cdot a_j\equiv 1\ \ mod(n)$ 。
我们用去乘集合M中的每一个元素（包括自己）得到新的m个数 $a_1\cdot a_i$ 、 $a_2\cdot a_i$ 、......、 $a_m\cdot a_i$ ，这新m个数中任意两个数之差 $a_s\cdot a_i-a_t\cdot a_i=(a_s-a_t)\cdot a_i$ 都不能被n整除，这是因为与n互质，而且 $a_s-a_t\ne 0$ 。这意味着新得到的m个数除以n的余数各不相同。
同时，新得到的m个数都是两个与n互质的数的乘积，仍然与n互质。这意味着新的m个数除以n的余数也必然与n互质。
于是，这新的m个数除以n的余数应该是两两不同且都与n互质的数，正好构成集合M。因为1必然属于M，所以这新的m个数除以n的余数中必然有一个余数是1。设这个数是 $a_j\cdot a_i$ ，于是我们就找到了这个。
我们把这个对应于的记作 $a_i^{-1}$ 。提醒注意的是，有可能 $a_i={a_i}^{-1}$ 。
结论2：当 $i\neq j$ 时， $a_i^{-1}\neq a_j^{-1}$ 。
否则，设 $a_i^{-1}= a_j^{-1}=a^{-1}$ ，那么就有 $a_i\cdot a^{-1}\equiv a_j\cdot a^{-1}\equiv 1\ \ mod(n)$ ，于是n整除 $(a_i-a_j)\cdot a^{-1}$ 。但由于 $a^{-1}\in M$ ，也就是说 $a^{-1}$ 与n互质，且 $a_i\neq a_j$ ，根据结论一证明过程中的分析，n整除 $(a_i-a_j)\cdot a^{-1}$ 是不可能的。结论2得证。

二、证明p为素数时，p整除(p-1)!+1
对于素数p来说，从1到p-1这p-1个数都与p互质，因此对于一个素数p，集合M={1, 2, ......, p-1}。
根据结论1和结论2，集合M中的任意一个数都存在一个唯一对应的数，使得这两个数的乘积除以p的余数是1。于是，我们可以将M中的数按照这个条件配对组合，形成若干组数对。但是，由于一种特殊情况的存在，我们无法保证这些数对覆盖了M中的全部数。这种特殊情况就是对于某些元素a， $a^{-1}=a$ 。下面我们针对素数p，分析这样的元素a的各种情况。
当 $a=a^{-1}$ 时，意味着 $a^2\equiv 1\ \ mod(p)$ ，也就是p能够整除。
由于p是素数，所以要么p整除a+1，要么p整除a-1。考虑到a是自然数且 $1\leq a<p$ ，那么只存在两种可能，要么a+1=p，要么a-1=0。也就是说，这样的元素a只能是1和p-1。
(p-1)!是集合M中全体元素的乘积，除了1和p-1以外，其它数正好可以配成若干对乘积除以p余1的数，根据同余关系，有
$(p-1)!\equiv (a_1\cdot a_1^{-1})(a_2\cdot a_2^{-1})...(a_k\cdot a_k^{-1})(p-1)\equiv p-1\ \ mod(p)$
上式中的 $a_1、a_1^{-1}$ 到 $a_k、a_k^{-1}$ 就是乘积模p余1的数对。
于是， $(p-1)!+1\equiv p\equiv 0\ \ mod(p)$ ，也就是说，p整除(p-1)!+1。

三、证明p整除(p-1)!+1时，p必为素数
假设p为合数，那么从1到p-1中，必有若干个不与p互质的数，设这些数为、、...、。其它的数都与p互质，为到。
由于与p互质的数之积仍然与p互质，与p互质的数除以p的余数也与p互质，所以我们得到 $a_1\cdot a_2\cdot ...\cdot a_m\equiv a_k\ \ mod(p)$ ，其中是一个与p互质且小于p的正整数，也即是到中的某个数。
已知p整除(p-1)!+1，也就是
$(p-1)!+1=b_1\cdot b_2\cdot ... \cdot b_s\cdot a_1\cdot a_2\cdot ...\cdot a_m+1\equiv b_1\cdot b_2\cdot ... \cdot b_s\cdot a_k+1\equiv 0\ \ mod(p)$
即p整除 $b_1\cdot b_2\cdot ... \cdot b_s\cdot a_k+1$ ，也就是存在整数r，使得
$r\cdot p=b_1\cdot b_2\cdot ... \cdot b_s\cdot a_k+1$
由于与p不互质，设它们有大于1的公因子u，在上式两边同时除以u，等式左边得到的必然是一个整数，而右边得到的是一个整数再加上 $\frac{1}{u}$ 。这显然是矛盾的。
于是我们知道p为合数的假设不正确，p必为素数。

综上，p整除(p-1)!+1等价于p是素数，威尔森定理得证。

威尔森定理其实最早是由德国数学家莱布尼兹（就是与牛顿争夺微积分发明权的那位）发现的（1671年发表），但是莱布尼兹没有给出证明。100年后的1771年，拉格朗日首先给出了证明。看起来这个定理的发现与证明都与威尔森没有任何关系，但为什么要叫做威尔森定理呢？

这是因为18世纪60年代，威尔森给他的一个朋友、剑桥大学数学家华林写信说他发现了一个素数判别法，就是这个定理。华林于是在1770年出版的《代数沉思录》中公布了威尔森的这个发现，并把它命名为威尔森定理。华林还“讨好”威尔森说，这个定理永远不可能被证明，因为人类还没有好的符号来处理素数。这话传到高斯耳朵里时，高斯只用了5分钟就告诉他人，自己已经证明了威尔森定理，并批评华林和威尔森“缺乏的不是符号，而是概念”。

就这样，这个很有价值的定理即没有用它的最早发现者莱布尼兹来命名，也没有用最早的证明者拉格朗日来命名，而是用了一个“缺乏概念”的后来发现者威尔森命名了。

威尔森定理是数论中的一个重要定理，是素数判别方法中一个基础的判别法。当然，这个判别法并没有提升素数判别的效率，计算阶乘和是否能够整除对于大数来说仍然是非常困难的。不过，这个判别法在很多时候还是有其价值的，研究数轮的学者绝大多数都会接触到这个定理。

虽然人们尚未发现有价值的素数公式，但是还是发现了关于素数的一些蛛丝马迹的规律。本文的文题图片就是一例，这张图片叫做乌拉姆表。

1963年，美籍波兰物理学家乌拉姆在参加一个学术会议时比较无聊，就信手把自然数按照逆时针方向排成螺旋状以消磨时间。没想到，乌拉姆意外的发现画出来的数字螺旋中，素数都排列在一条条直线上。后来，他和同事们一起用计算机计算了1000万以内的自然数，发现素数仍然在直线上。当然，这不能叫做一个数学规律，只能叫做某种蛛丝马迹，成因尚不清楚。其实，类似的现象还有萨克斯螺旋。

奇妙的素数啊，让世界上的数学家们百思不得其解，又痴迷于其中不可自拔。

四、关于素数的一些知名世界级数学难题

素数这么简单的一个概念，引发了大量的数学问题。关于素数的分布，最有名的成果就是素数定理。

如果我们用 $\pi(n)$ 表示小于等于n的素数的个数，那么素数定理告诉我们

$n\rightarrow \infty$ 时， $\pi(n)\rightarrow Li(n)=\int_{2}^{n}\frac{1}{ln(x)}dx$

根据素数定理，我们可以简单理解为，当n很大的时候，素数分布的密度接近 $\frac{1}{ln(n)}$ 。对比前面说过的完全平方数的分布，平均来说在 (n+1)^2 与 n^2 之间存在一个完全平方数，因此完全平方数的分布密度接近 $\frac{1}{2n}$ ，这要比素数分布稀疏得多，所以完全平方数的倒数和是收敛的，而素数的倒数之和不收敛。

素数定理最早由高斯提出猜想，切比雪夫曾经为证明素数定理作出了巨大贡献。最终于1896年，两位年轻的数学家阿达马(J.Hadamard)和德·拉·瓦莱布桑(C. J. de la Vallée Poussin)证明了素数定理。神奇的是，1949年，另外两位年轻的数学家——31岁的赛尔伯格(A. Selberg)和35岁的爱多士(P. Erdös)分别独立地使用初等数学证明了素数定理。

和素数定理有关的还有一个有趣的事情。人们在大量观察 $\pi(n)$ 和 Li(n) 之间的关系时发现， $\pi(n)$ 总是小于 Li(n) ，虽然越来越趋近，但是在人们验证过的上10亿个素数以内， $\pi(n)$ 都小于 Li(n) 。很自然的，人们就猜想 $\pi(n)$ 永远小于 Li(n) 。不过大数学家利特尔伍德运用分析的力量证明了，不仅这个不等关系不成立，而且存在无穷多个n违反这个关系，只不过其中最小的n也至少大于 $10^{316}$ 。这个结论还提醒我们，不要认为大量计算机验证过的未证明数学猜想都是正确的， $\pi(n)$ 与 Li(n) 的关系就是一个反例。

关于素数的最著名的一些猜想包括哥德巴赫猜想、孪生素数猜想、黎曼猜想等等。这里面黎曼猜想是最吸引数学家兴趣的。如果谁能够证明黎曼猜想，一定会成为比证明了费马大定理的安德鲁.怀尔斯还著名的大数学家。关于这些猜想，内容太多，限于本文篇幅，就不再详细介绍了。

素数，一个简单的定义给出的概念，但是却蕴含着无比复杂而深刻的数学思想。一组完全确定的数列，但却只能使用类似研究随机的方式来研究它。我愿意用中国数学家陈景润在《中国大百科全书.数学卷》的条目“素数分布”中所写的那段话来作为本文的结尾，“素数在自然数中占有极其重要的地位，但是它的变化非常不规则。人们至今没有找到，大概也不可能找到一个可以表示全体素数的有用公式”。