注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ad0415的博客

欢迎来作客!ad0415@yeah.net

 
 
 

日志

 
 

中国的数学家在素数研究方面的成就  

2007-12-24 13:26:25|  分类: 数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

  自然数列1234,…,应该是人类最早认识的数列。老子的书里就有:“一生二,二生三,三生万物”的记载,反映了中国人民很早对它认识了。

在自然数里,根据能否被2整除的性质,而分成偶数和奇数。一个大于1的数如除了1和它本身以外,再没有其他自然数能整除它,我们就称它为素数(或者也叫质数 Prime number)。因此根据这定义,读者很容易找出小于10的素数有四个即2357

在欧几里得的《几何原本》一书里,他介绍了素数的概念,然后用反证法很巧妙的证明了在自然数列里素数的个数是有无穷多个。

西方的数学家一般都认为希腊人是最早懂得素数的民族。可是由最近在非洲出土的一些6000多年前非洲人的骨具,证明了希腊人并不是最早知道素数的民族。

从两块骨头谈起 

现在藏在比利时布鲁塞尔的自然历史博物馆的二块骨头很受考古学家的重视。这些骨头是最近在刚果的爱德华湖畔的一个伊珊郭(Ishango)渔村所发掘出来的。

根据科学方法检定,它们是在公元前9000年到公元前6500年间非洲人的骨具。把手有规则的凹下刻痕,在顶端有附上一小块的石英。考古学家猜想这是当地的原居民用来作为雕刻或者书写的工具。

这骨具的刻痕引起了人们的兴趣,它们代表什么呢?有什么特殊的涵义?我们现在来看看吧!

左边那块骨头有八组刻痕,是由364810557的线组成。36很靠近,隔一段空间就是48,然后是10及两个5。再下就是一个7。很可能刻这刻痕的无名氏想要说明的是6810分别是345的二倍。

右边那块骨具在左右二侧有不同的刻痕,在左侧有1121199的线的刻痕。在右侧有11131719的刻痕。有人解释这无名氏是要说明 10+120+120-110-1的结果。

不过令我们产生兴趣的是右侧的刻痕,这些数字都是大于10和小于20之间的所有素数,我们现在同时看这二块骨具的右侧,出现了5711131719有一种次序,这样看来差不多在一万年前非洲人民就认识到素数的存在了! 

怎样寻找素数

我们在小学时学到任何整数可以唯一分解成为素因子的乘积。素数对乘法来讲就像是组成“整数分子”的“原子”。因此素数是很重要的。

可是人们怎样找出素数呢?

2000年前在埃及有一个叫伊拉托斯丁纳(Eratosthenes公元前276—公元前194)的希腊学者,他是阿历山大图书馆的管理员,发现了后来以他的名字命名的筛法(Sieve Method)可以把素数从像砂子那么多的整数里筛出来。

他的方法是这样:将1234,…直到N写下。将这数列中划去所有2的倍数,在2之后第一个没划去的数是3,于是就在这数列中除了3之外删去所有3的倍数。按着3之后的第一个没有被划去的数目是5,然后再划去除了5以外的所有5的倍数。以此类推,一直到不

读者试试用这个方法来寻找所有小于100的素数,可以得到像图一那样的情形。

现在有一个问题产生,如果给出一个整数,怎样判断它是素数?如果我们知道所有小于这数的开方的素数不能整除这数,那么这给出的数是素数。可是当这数太大时,比方说有一亿个位数,那么这方法是太累赘了。目前都是利用电子计算机来帮忙检验一个数是否素数。

我们目前所知道的最大素数*是美国人杜克曼(BryantTuckerman)在 1971年利用电子计算机找到,它是219937-1这个素数共有6002位数,开头是4315424797…,结尾是…968041471。杜克曼用电子计算机检验它是素数共花去了半个钟头,如果这个工作由一个年青人去用笔算来检验,可能等他老掉了牙,还不能查出它是素数。

  素数的一个古怪脾气

  素数有许多奇妙的性质,引起数学家的注意和研究。比方说在1963年美国著名数学家乌兰教授(SUlam)在参加一次科* 19969月初,美国科学家找到一个新的最大素数21257787-1,它是一个378632位数。学会议时,因为对演讲者报告的一篇又长又臭的论文不感兴趣,为了打发时间,他就在纸上纵横划线打出一些方格子来。

他最初想要考虑一些象棋的问题,可是后来改变想法,就以中心的1做出发点,以反时针方向划螺旋线(如图二)。不知怎么样他把凡是素数的格子圈出来,他看看有什么趣味的东西出现。

突然间他觉得素数好像是很喜欢挤成直线!如311以及132953等等可以联成直线。

他想要知道这种现象在100以后的数是否会出现,于是他和几个朋友利用 Los Alamos的电子计算机打出从1 6 5千的螺旋图。

实在奇怪,这种现象仍旧出现。我们这里附上图三是电子计算机打出的该图的一部份,包含的数是从11万。每一个白点代表一个素数,读者从图中很容易看到这种乌兰现象。这个图很好用,数学家从这里找出了一些素数的新性质。

素数在自然数列中的分布 

素数在自然数列中分布好像没有什么规则,为了很好的研究它的分布一些规律,数学家引进了一种重要的数论函数π(x)(读作派x):它是代表不超过实数x1的素数的个数。例如π(1.9=0,因为没有一个素数P1.9;π(10=4,读者早知道了不超过10的素数有四个。

这个函数是递增的,即随着x的增大,π(x)值也跟着不断增大。例如π(10万万)=50847478,由欧几里得的定理,我们知道当x趋向于无穷大时,π(x)的值也跟着趋向无穷大。

18世纪的最伟大的数学家欧拉(Euler)他发现当x趋向无穷大时,

世纪的最伟大的数学家欧拉(Euler)他发现当x趋向无穷大时,

为了能更深刻地知道这个素数函数的性质,在19世纪以前的数学家想找出一个他们较熟悉的简单的解析函数近似相等于π(x)。即找出

几个法国、德国和俄国的数学家如勒让德(Legendre)、高斯(Gauss)、狄利克雷(Dirichlet)、车比雪夫(Chebysev)和黎曼

这个问题到了100年以后才在1896年同时候由法国数学家哈达玛(JHadamard)和比利时数学家瓦莱·布善(CJdelaValleé——Pousin)解决。他们都用到了复变函数理论的黎曼齐塔函数(Riemann Zeta function)。

这个定理在素数理论中是非常重要,因此数学家通常称它为“素数定理”(Prime number theorem),哈达玛和布善的证明是非常的漂亮,长期以来很多人都认为不可能有不用复变函数理论为工具而证明这个定理的初等方法。在本世纪初,匈牙利数学家厄多斯(Erdos)和西柏(ASelberg)用初等微积分的理论给出了这个定理的另外证明。

关于这个素数函数,还有许多问题直到现在还没有彻底地解决。例如对于所有的x1y1,人们猜想π(x+y)≥π(x+π(y),可是到目前为止只有美国数学家SLSegalxy同时小于10181的情形获得证明。

 表面简单实际困难的素数问题

  和素数有关的问题,许多是很容易明白的,表面看起来是不困难的,但解决起来都是很困难,下面我们举几个还未解决的问题说明:

1)是否有无穷多素数是形如n2+2

2)是否有无穷多素数是形如n2+1

31111 111 111 111 111 111 111 111,都是素数,它们分别可以写成(102-1)÷9,和(l023-1)÷9,现在知道一个数(10k-1)÷9是素数,则必须是k是素数。

反过来不一定成立,例如(103-1)÷9=111=3×37,同样(105-1)÷9也不是素数。

由于素数的个数有无穷多,因此是否形如(10k-1)÷9的素数也是有无穷多个?

4)读者请写下一个很长的自然数列1234,…。然后对任何x1,在x2x之间一定会找到一个素数。比方说你现在挑出x=4,你发现在48之间就有57这个素数,你多试验几次,每次都是有这个结果。

俄国19世纪的大数学家车比雪夫,证到了一个定理可以推到以上的结果。

好,我们现在看看一个类似的问题:我们把自然数列每一项取平方,我们得到1491625,…。我们发现到在14之间自然数列有二个素数23。在49之间自然数列有二个素数57,在916之间有二个素数1113,在1625之间有三个素数171923

因此你提出了这样的想法:对任意整数n,我们一定可以在n2和(n12之间找到一个素数。

这是数学上的一个难题,很早就有人提出了。可是到现在还没有全部解决。

5)把自然数列排成下面的梯阶形:

4        5        6

7        8        9       10

11      12      13     14       15

16      17      18     19       20       21

…………………………………

等等。从第二阶开始,最初的几阶每一阶最少都出现一个素数。这种现象以后是否一直出现呢?很多人认为应该是这样。

6)我们称满足代数方程x2+y2=z2的数组{xyz}为商高数组,商高数组一般是由{m2-n22mnm2+n2}给出。这里m是大于n的整数。美国数学家IABarnett猜想存在有无穷多的mn,它们的最大公约数是1,而使得x+yx-y同时是素数。

今年初美国俄亥俄州大学的数学家利用电子计算机对m小于46000的情形检验,发现了许多有这样性质的商高数组,看来Barnett的猜想是会对的,你不妨试试找出一个证明出来。

孪生素数问题

  35这二个素数相差是2。读者很容易找到{57}{1113}{1719}{2931}等等素数对有这样的性质。

在数学里,数学家称这样的素数对为孪生素数(twinPrimes)。有一个很出名的问题叫着“孪生素数猜想”,它是这样叙述的:存在着无穷多的n,使得n-1n+1同时是素数。这问题提出有1000多年的历史了。

现知 n=46121830,…,1000000000062140737488353700都给出孪生素数。现在知道在100万内有多于8000的孪生素数对。

欧拉发现如果对每个素数取倒数,然后再把它们全部加起来,这个和是无穷大。可是在1919年挪威数学家Brun发现如取所有的孪生素数对的倒数的和,这个级数却是收敛的(Conver-gent),即和是一个有限值。

我们类似素数函数π(x)定义一个孪生素数函数Tx),令x1Tx)是定义为不超过x的所有孪生素数的个数。有人猜想存

目前最接近解决孪生素问题是由中国数学工作者陈景润得出。要介绍他的工作,我们先从一个著名的数学问题谈起。

哥德巴赫问题

  歌德巴赫(CGoldbach 16901764)是德国数学家,他曾是俄国莫斯科学院的秘书。他和他的好朋友欧拉常通信讨论他们研究所发现的东西。在174267日哥德巴赫由莫斯科写了一封德文信给欧拉:“……我认为把一些可能对的命题,尽管是还不能证明写下来还是适合的。因为即使是以后发现它们是错误的,可是它们仍提供了发现新真理的机会。费马认为22n-1+1可以给出一序列的素数,事实上——如你所知——是错误的。然而这还是可贵,如果这序列供给了唯一表示二个整数平方和的数。因此我想冒险提出这样的猜想:任何数如果是二个素数的和,也是许多素数的和(1也算作素数),直到所有的和因子是1*例如

[哥德巴赫]*:又当我在读这信时,我发现如果能对n证明而且n+1是能表示二个素数的和时则能对n+1也证明。证明是容易。最少看来所有大于1的数是三个素数的和。

欧拉在630日从柏林回信给哥德巴赫指出了:“任何数如能表示成二个素数的和,同时也可以表示成许多素数的和,这可以由你以前告诉我的一个观察结果:任何偶数是二个素数的和来证明出来。因为如果提出的数是偶数,则它是二个素数的和,而因为n-2也是二个素数的和,因此n是三个素数的和,因而是四个素数的和,依此类推下去。然而,如果n是奇数,则它明显是三个素数的和,因为n-1是二个素数的和,因此也可以分解成许多素数的和。然而所有的偶数是二个素数的和,我认为这是一个肯定的定理。尽管我还不能证明出来。”

事实上,哥德巴赫在以前的信提到了二个猜想:

A)任何大于2的偶数是二个素数的和。

B)任何大于5的奇数是三个奇素数的和。

如果(A)是对,(B)则很容易证明:

因为如果N是奇数,我们取一个小于N的奇素数P1,则N-P1是偶数,由(A)知道它是可以表示成P2+P3,因此N=P1+P2+P3

200年来这问题引起许多数学家的研究。哥德巴赫的猜想看来不难验证,如:

6=3+3 8=3+5 10=3+7 12=5+7 14=3+11 16=3+1318=5+13 20=3+17以及40=3+37=11+29=17+23等等。

有人曾对十万以下的偶数检验都发现哥德巴赫的猜想是对的。可是怎样对所有的偶数证明呢?

1937年苏联数学家维诺格拉朵夫(IVinogradov)用分析方法证明了:对于相当大的奇数,是可以表示成三个奇素数的和。因此对于哥德巴赫猜想(B)这是最好的结果。

 

中国数学家在这方面的研究

 

目前最接近解决哥德巴赫猜想(A)是由中国数学家陈景润获得。他是福建省福州人,是中国解放后厦门大学数学系的第一届毕业生。解放前他父亲是邮局职员,一家七口靠那点微薄的公务员薪水,有时不得温饱,他高中未毕业就失学在家。新中国成立后他才有机会继续读书。

他从厦大毕业后,就留在原校工作。在两年的业余时间,对数论非常兴趣,阅读了华罗庚大部份的著作,第三年提出一篇关于“Tarry问题”的论文,对华罗庚在堆垒素数论的研究成果有一些推进。

1957年,他在华罗庚的提拔下调到北京科学院数学研究所工作,在这里他有机会从闵嗣鹤教授、吴方、王元、潘承洞等学习到了一些新的理论。

匈牙利数学家Renyi最先证到(那是1948年的事了)任何充份大的偶数可以表示成1个素数和几个素数乘积的和。

1962年年青数学家潘承洞证明了充份大的偶数可以表示成一个素数和一个最多有五个素数乘积的整数的和。

王元和潘承洞在1962年和1963年更进一步证明了充分大的偶数可以表示成一个素数和一个最多有四个素数乘积的整数的和。

陈景润在1963年才开始对哥德巴赫问题做研究。他为了解决这个问题夜以继日的研究,甚至假日也不休息。不论是酷热的炎夏,还是严寒的隆冬,他都埋头在图书馆做这研究。在1966年取得初步成果论证了充份大的偶数都是由一个素数再加上另一个整数,这整数最多由二个素数相乘得到。这结果在《科学通报》发表了一个简单证明。那时他才32岁。

1965年意大利杰出的青年数学家EBombieri(他在1974年获得世界数学家会议颁给的Field金奖章,因为他在几何以及数论方面的成就。)只证到任何充分大的偶数是一个素数和一个最多能表示成三个素数乘积的整数和。

记者访问陈景润,他说:“在1973年我在《中国科学》正式发表了题为:《大偶数表为一个素数及一个不超过二个素数的乘积之和》的论文。这是我研究的成果论文,它接近了哥德巴赫猜想,如果求证到另一个数也是素数,那就完全证实了歌德巴赫的猜想,要达到这一步还要继续努力。”

不久前陈景润还出席了全国第四届人民代表大会。陈景润的工作在数论是非常重要,他同时接近解决了数论二大难题:孪生素数和哥德巴赫问题。最近英国数学家哈伯斯坦(Ha berstram)在他新写的《筛法》一书,特别一章专门讲陈景润的定理。

看到年轻一代的数学家在数论方面的成就,我们不要忘记了老一辈的数学家如华罗庚、闵嗣鹤等教授的功劳。第一代的数学前辈披荆斩棘闯出了一条路来,而第二代的数学家发扬前辈大无畏的精神敢于攀登科学高峰,获得了一些优秀成绩。

在外国一些认识华罗庚工作的人,由于个人主义的想法常常为他惋惜——不能继续搞深的数学,而做普及“简单”数学教育的工作。可是他们哪里知道:“一枝吐放不是春,万紫千红才是春。”华罗庚等人长期来苦心孤诣,不辞劳苦到处做普及数学教育的工作,使广大群众能早日掌握到“打开科学大门的锁钥”——数学这门知识。随着老中青三结合的政策的实行,第三代的年青数学工作者将迅速茁长,在这种情况下:“天公亦喜凌霄志,不拘一格降人材。”在不远的将来,肯定中国人民在数学上将会和几千年来祖先在这领域一样有着辉煌的成就。

“待到山花烂漫时,她在丛中笑”这日子是不远了。

附件:如何求素数

public class Test
{
 /*
  * 最普通的算法:
  * 打印num以内的素数并返回素数个数
  * n、m分别为外、内层循环,i是第几个素数,s是素数个数
  */
 public int prime(int num){
  int n,m,i=0,s=0;
  label1:
  for(n=2;n<=num;n++)
  {
   for(m=2;m<=n/2;m++)
   {
    if(n%m==0)
    continue label1;
   }
   s++;
   i++;
   System.out.println("第"+i+"个素数是:"+n);
  }
  return s;
 }
 
 public static void main(String args[]){
  Test test = new Test();
  int sum = test.prime(1000);
  System.out.println("共"+sum+"个素数");
 }
}

【1】求10000以内的所有素数。
素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数,所以对于数学家来说,素数一直是一个未解之谜。像著名的 哥德巴赫猜想、孪生素数猜想,几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研,呕心沥血,但至今仍然未见分晓。
自从有了计算机之后,人们借助于计算机的威力,已经找到了2216091以内的所有素数。
求素数的方法有很多种,最简单的方法是根据素数的定义来求。对于一个自然数N,用大于1小于N的各个自然数都去除一下N,如果都除不尽,则N为素数,否则N为合数。
但是,如果用素数定义的方法来编制计算机程序,它的效率一定是非常低的,其中有许多地方都值得改进。
第一,对于一个自然数N,只要能被一个非1非自身的数整除,它就肯定不是素数,所以不
必再用其他的数去除。
第二,对于N来说,只需用小于N的素数去除就可以了。例如,如果N能被15整除,实际
上就能被3和5整除,如果N不能被3和5整除,那么N也决不会被15整除。
第三,对于N来说,不必用从2到N一1的所有素数去除,只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明:
如果N是合数,则一定存在大于1小于N的整数d1和d2,使得N=d1×d2。
如果d1和d2均大于√N,则有:N=d1×d2>√N×√N=N。
而这是不可能的,所以,d1和d2中必有一个小于或等于√N。
基于上述分析,设计算法如下:
(1)用2,3,5,7逐个试除N的方法求出100以内的所有素数。
(2)用100以内的所有素数逐个试除的方法求出10000以内的素数。
首先,将2,3,5,7分别存放在a[1]、a[2]、a[3]、a[4]中,以后每求出一个素数,只要不大于100,就依次存放在A数组中的一个单元 中。当我们求100—10000之间的素数时,可依次用a[1]-a[2]的素数去试除N,这个范围内的素数可以不保存,直接打印。

【2】用筛法求素数。
简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家,他在寻找素数时,采用了一种与众不同的方法:先将2-N的各数写在纸上:

在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数 是5,将它画圈,并划去5的其他倍数……依次类推,一直到所有小于或等于N的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于 N的素数。

这很像一面筛子,把满足条件的数留下来,把不满足条件的数筛掉。由于这种方法是厄拉多塞首先发明的,所以,后人就把这种方法称作厄拉多塞筛法。
在计算机中,筛法可以用给数组单元置零的方法来实现。具体来说就是:首先开一个数组:a[i],i=1,2,3,…,同时,令所有的数组元素都等于下标 值,即a[i]=i,当i不是素数时,令a[i]=0 。当输出结果时,只要判断a[i]是否等于零即可,如果a[i]=0,则令i=i+1,检查下一个a[i]。
筛法是计算机程序设计中常用的算法之一。

【3】用6N±1法求素数。
任何一个自然数,总可以表示成为如下的形式之一:
6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)
显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析,我们可以构造另一面筛子,只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。

在程序上,我们可以用一个二重循环实现这一点,外循环i按3的倍数递增,内循环j为0-1的循环,则2(i+j)-1恰好就是形如6N±1的自然数。


 
  评论这张
 
阅读(449)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017