素数漫谈

——兼谈最大的素数

素数(Prime number)是具有这样性质的大于1的正整数P。除了1和自身P以外,再找不到其他小于他的正数能整除它。

我们在小学时就知道小于10的素数有:2357这四个素数。在这之后,小于20的素数有:11131719四个。在这之后小于30的素数有:2329两个。如果你试试找在这之后到40之间的素数,你发现共有两个,它们是:31 37

你如果看以上的实际例子,你可能会猜想每十个整数间隔,会有两个或四个的素数出现。让我们看看你的猜想是否正确?

40 50之间我们有:414347三个素数!哎呀!我们的猜想是错了。实际上,我们是可能找到十个整数间隔,没有一个数是素数。素数的分布是杂乱无章,像是没有规律可寻,可是数学家却发现它们有许多奇妙的性质。

2500百多年前,希腊有一个叫欧几里得(Euclid)的数学家发现了在正整数的集合里素数的个数是有无穷多。在他的著名的著作《几何原本》一书里,他证明了算术基本原理:“任何自然数都能唯一的表示成为素数的乘积。”

例如 4=2×26=2×39=3×318=2×3×310005= 3×5×23×29

因此对于自然数以及乘法运算来说:素数是建立自然数的基本成分,它是不能再分解的最小的基本粒子 elementary Parti  cle)。

两千多年来,有无数喜欢探索数字世界奥秘的数学家竟为素数而折腰。我们这里就说古道今,讲一点这方面的故事和最近的一些新结果。

首先我们看小于10的三个素数:357后面的数和前面的数相差为2,因此我们可以这样写:5=327=52=32 2=32×2,我们说357组成一个等差级数,它们的公差是2,首项是3

现在请看另外一大串的素数:7376797127157,这是以首项为7,公差为30的等差级数,如果用Tn)表示第n项,我们可以用公式Tn=30n-23来表示。

我们再看另外一串的由素数组成的等差级数:199409619829103912491459166918792089。我们的首项是199,公差是210。如果我们写

T1=199

T2=199210=T1)+210

Tn=Tn-1)+210

把这等式的左边及右边各加起来,我们得到:

T1)+T2)+…+Tn

=199[T1)+210]+…+[Tn-1+210]

Tn=199+(n-1)×210=210n-11

因此我们很自然会想到是否能找到一个公式fn=anb 这里ab都是整数,使到我们用任何正整数n代进公式都能得到一个素数,这样我们就可以取得任意长的由素数组成的等差级数了,而这也证明了素数的个数有无穷。很不幸,事与愿违,我们没法子找到这样的公式!因为假定存在这样的公式:fn=anb,第1f1=ab是一个素数P,我们看f1p =a1p)+b=aapb=pap=p1a),很明显的这项 不会是素数!

既然我们找不到能生成素数的一元一次方程式,是否我们能找到 ab c三个整数,及公式 fn=an2bnc,使得当我 们用所有的正整数n代进去,我们都能得素数?

让我们看几个例子:

1 如果fn=n221n1,我们分别用123,…,17代进去,可以分别得f1=23f2=47f3=73 …,f17=647这些都是素数。可是当您用n=18代进公式,你得到f18=703=37×19这不是素数了!

2 著名的数学家欧拉(LEuler 17071783)发现公式  fn=n2n41123,…,39代进去都得到素数,如 果用-40-39-38,…,-10来代入也能得到素数。可  是当n=40时,我们有 

f40=40×(401)+41=41×41这不是素数! 

很难猜想是否能找到 fn=an2bnc,使得对所有的正 整数nfn)都是素数?假定存在这样的二次方程,我们用1 代入得

f1=abc=p 

现在我们以n1p代入得 

a1p2b1p)+c

=a12pp2)+b1p)+c 

=ap22apbp+(abc 

=pap2ab1

因此f1p)不是素数,这和我们的假设矛盾。因此我们 不可能找到一元二次方程使得fn)对任何n都能给出素数。

事实上欧拉后来发现了下面的欧拉定理。

欧拉定理 对于任何k2,不存在一元k次元方程式 fn),使得fn)对所有的正整数都是素数。

这个证明不太难,读者可以模仿一次、二次方程的证明,试试找出一般证明。

2欧拉给出的公式,我们从n=-40,一直增加到  n=39,总共可以连续得到80个素数。有人曾经想找类似欧拉的  公式,像

gn=n2nAA41

是否能有从n=01,一直到A-2都能给出素数来?在1967  有人证明这是不可能的。

德国数学家狄利克雷(Drichlet 18051859)在1837年证 明了给定任何两个整数ab,如果ab没有公共因子(即其最大公约数GCDab=1)那么由公式 fn=anb生成的  数列会包含无穷多素数。这是数论中一个非常美丽的结果。

〔未解决问题1公式 gn=n21生成的数列是否能包  含无穷多素数呢? 

〔未解决问题2是否存在一个一元二次方程

hn=an2bnc,及一个k使得hk),hk1),hk2),…,hkm 

都是素数,而m80?(即你能否找到一个比欧拉还要好的公式 能连续生出八十个以上的素数。有许多人认为这是不可能的,但是还没法子证明。)

〔未解决问题3公式 fn=2n1有这样的性质;能找出  无穷多素数n23511在这里面)使得fn)也是素数。

〔未解决问题4人们相信公式 fn=n2-2给出无穷多的  素数。

古代的希腊数学家发现有一些整数像6284968128。有这样奇妙的性质:把它的所有小于本身的因子取出然后求和可以还原得回原来的数。如:

6=123 

28=124714 

他们觉得具有这样的美妙性质的数是十全十美,就像没有任何缺点的完人,因此称这类为完全数(Perfect number)欧几里得在2000多年前发现

6=2×3=2×(22-1), 

 28=4×7=22×(22-1),

496=16×31=2425-1 

因此证明了:

〔欧几里得定理〕如果2n-1是素数,则 2n-12n-1)是完全数。

2000年之后欧拉发现反过来说也对;〔欧拉定理〕所有的偶完全数是形如2n-12n-1)的样子,而2n-1是素数。

因此人们对形如 2n-1 的素数产生兴趣,我们看n=23  45时,对应的2n-1是:371531。明显的,15不是素  数。

卡达迪(Cataldi 和法国数学家费马(Fermat)证明:“如果2n-1是素数,则n必须是素数。”但是是否所有的素数n 能给出素数 2n-1 呢?发明微积分的德国数学家莱布尼兹相信这是对的。因此他认为具有无穷多素数是形如 2n-1的样子,可是人们发现2n-1=2047有一个因子23,这证明莱布尼兹是错误。

人们把当n是素数形如2n-1的数用记号Mn来表示称为麦爽数(Mersenne number),麦爽是三百多年前法国一个神父,他 喜欢数论写信给当时法国著名数学家如巴斯卡、笛卡儿、费马等和他们讨论数论的问题,就是他使到费马等对完全数产生兴趣。

究竟有多少麦爽数是素数呢?

〔未解决问题5人们相信会有无穷多麦爽数是素数。

可是目前人们知道是素数的麦爽数却是屈指可数。

2000年前希腊人知道了 M2=3M3=7 M5=31 M7= 127是素数。没有人知道是谁发现M138191是素数,在公元1588年卡达迪发现M17M19是素数,1772年欧拉证明M31是素数,在这之后一百年M31是当时世界所知的最大素数。

由于Mn增大的非常快,对于大的数要检验是否素数并不很容易,以后人们发现了M61M89M107M127都是素数。对于  n=127的情形是法国数学家鲁卡斯(EALucas)在1876 发现一种判别Mn是否素数的快速检验方法而得到。到了1930年美国数学家列默(DHLehmer)把这方法改进成了下面的 有名:

〔鲁卡斯和列默检验法〕我们会s1=4s2=42-2s3=s2- 2,一般si=s2i-2,这样我们得出一序列的整数{s1s2s3s4,…}麦爽数Mp是素数当且仅当Sp-1能被Mp整除。 

以后人们就用以上的检验法利用电子计算机的协助找到了许 多是素数的麦爽数。这方法的好处是只用乘法和加、减法运算,而不用除法运算。

我这里列下了这方面工作的表:

我们讲一讲最近发现的大素数的一些故事:在197810月两位中学生Curt NollLaura Nickel 他们用了当时威力最大的电脑 CRBER 174寻找到了第25个麦爽数,当时是全世界已知的最大素数,轰动世界,他们总共花了四百五十多电脑小时寻找这个素数。第二年Noll孤军奋战,又找到了第二个麦爽数。

这时一种新的威力强大的电脑Cray 2号出现了。Cray 2号是运算速度惊人,称为《超电脑》(就像“超人”(Superman)那样我们有《超电脑》(Super Computer)在 CRAY研究部门工作的一位25岁的小伙子史洛汶斯基,在Noll发现最大素数的六个星期之后,用Cray 1号于19794月,发现了一个一万三千 多位数的新的最大素数。

以后他继续寻找新的大素数,CRAY的运算速度是每秒能做8000万加法和乘法运算!在19832月初史洛汶斯基又找到了最大的新麦爽素数,全部花费200多小时的电脑计算时间。如果不用电脑来计算检验,一个心算很好的数学家也要花几万年以上的时间才能找到这个素数。

史洛汶斯基很喜欢快速度,周末就驾飞机,骑电单车和长跑,他希望在最近的将来能再找到新的大麦爽素数。有些数学家认为在本世纪结束前用鲁卡斯和列默检验法如果能再找到两三个新的麦爽素数,那将是非常幸运的事