初等数论论文-2

初等数论论文素数及其应用摘要：质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。因为合数是由若干个质数相乘而得来的，所以，没有质数就没有合数，由此可见素数在数论中有着很重要的地位。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数是与合数相对立的两个概念，二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题，如哥德巴赫猜想等。算术基本定理每一个比1大的数（即每个比1大的正整数）要么本身是一个素数，要么可以写成一系列素数的乘积，如果不考虑这些素数的在乘积中的顺序，那么写出来的形式是唯一的。这个定理的重要一点是，将1排斥在素数集合以外。关键词：素数，无穷性，著名问题，应用素数的概念概念\o"编辑本段"只有1和它本身两个正因数的自然数，叫素数(PrimeNumber)，又称质素。（如：由2÷1=2，2÷2=1，可知2的因数只有1和它本身2这两个约数，所以2就是质数。与之相对立的是合数：“除了1和它本身两个因数外，还有其它因数的数，叫合数。”如：4÷1=4，4÷2=2，4÷4=1，很显然，4的因数除了1和它本身4这两个因数以外，还有因数2，所以4是合数。）100以内的质数有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，在100内共有25个质数。注：（1）2和3是所有素数中唯一两个连着的数。（2）2是唯一一个为偶数（双数）的质数。（3）质数的平方数只有三个因数.素数无穷性的证明素数的个数是无穷的。最经典的证明由欧几里得证得，在他的《几何原本》中就有记载。它使用了证明常用的方法：反证法。具体的证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，N+1是素数或者不是素数。如果N+1为素数，则N+1要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以N+1不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。对任何有限个素数的集合来说，用上述的方法永远可以得到有一个素数不在假设的素数集合中的结论。所以原先的假设不成立。也就是说，素数有无穷多个。其他数学家也给出了他们自己的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，HillelFurstenberg则用拓扑学加以证明。素数计算尽管整个素数是无穷的，仍然有人会问“100,000以下有多少个素数?”，“一个随机的100位数多大可能是素数?”。素数定理可以回答此问题。素数、即质数，是在大于1的整数中只能被1和其自身整除的数。梅森素数以法国数学家马兰.梅森命名，指的是形如2的P次幂减一的素数，而P本身也是素数。迄今为止，数学界共计发现48个梅森素数。中央密苏里大学在2013年1月25日协调世界时23:30:26发现的那一素数2的57,885,161次幂减一为迄今发现的最大素数。素数检验\o"编辑本段"检查一个正整数n是否为素数，最简单的方法就是试除法，将该数n用小于等于根号n的所有素数去试除，若均无法整除，则n为素数，参见素数判定法则。2002年，印度人M.Agrawal、N.Kayal以及N.Saxena提出了AKS质数测试算法，证明了可以在多项式时间内检验是否为素数。著名问题哥德巴赫猜想\o"编辑本段"在1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的整数都可写成三个质数之和。因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本，即任一大于2的偶数想陈述为欧拉的版本。把命题"任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"。1966年陈景润证明了"1+2"成立，即"任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和"。今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。从关于偶数的哥德巴赫猜想，可推出任一大于7的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。若关于偶数的哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。若哥德巴赫猜想尚未完全解决，但1937年时前苏联数学家维诺格拉多夫已经证明充分大的奇质数都能写成三个质数的和，也称为“哥德巴赫-维诺格拉朵夫定理”或“三素数定理”，数学家认为弱哥德巴赫猜想已基本解决。黎曼猜想黎曼猜想是关于黎曼ζ函数ζ(s)的零点分布的猜想，由数学家波恩哈德·黎曼（1826--1866）于1859年提出。德国数学家希尔伯特列出23个数学问题．其中第8问题中便有黎曼假设。素数在自然数中的分布并没有简单的规律。黎曼发现素数出现的频率与黎曼ζ函数紧密相关。黎曼猜想提出：黎曼ζ函数ζ(s)非平凡零点（在此情况下是指s不为-2、-4、-6等点的值）的实数部份是1/2。即所有非平凡零点都应该位于直线1/2+ti（“临界线”（criticalline））上。t为一实数，而i为虚数的基本单位。至今尚无人给出一个令人信服的关于黎曼猜想的合理证明。在黎曼猜想的研究中，数学家们把复平面上Re(s)=1/2的直线称为criticalline。运用这一术语，黎曼猜想也可以表述为：黎曼ζ函数的所有非平凡零点都位于criticalline上。黎曼猜想是黎曼在1859年提出的。在证明素数定理的过程中，黎曼提出了一个论断：Zeta函数的零点都在直线Res(s)=1/2上。他在作了一番努力而未能证明后便放弃了，因为这对他证明素数定理影响不大。但这一问题至今仍然未能解决，甚至于比此假设简单的猜想也未能获证。而函数论和解析数论中的很多问题都依赖于黎曼假设。在代数数论中的广义黎曼假设更是影响深远。若能证明黎曼假设，则可带动许多问题的解决。孪生素数猜想1849年，波林那克提出孪生质数猜想（theconjectureoftwinprimes），即猜测存在无穷多对孪生质数。猜想中的“孪生质数”是指一对质数，它们之间相差2。例如3和5，5和7，11和13，10,016,957和10,016,959等等都是孪生质数。费马数被称为“17世纪最伟大的法国数学家”的费马，也研究过质数的性质。他发现，设Fn=2^(2^n)+1，则当n分别等于0、1、2、3、4时，Fn分别给出3、5、17、257、65,537，都是质数，由于F5太大（F5=4,294,967,297），他没有再往下检测就直接猜测：对于一切自然数，Fn都是质数。这便是费马数。费马死后67年，25岁的瑞士数学家欧拉证明：F5=641×6,700,417是一个合数。以后的Fn值，数学家再也没有找到哪个Fn值是质数，全部都是合数。由于平方开得较大，因而能够证明的也很少。现在数学家们取得Fn的最大值为：n=1,495，其位数多达10^10584位，当然它尽管非常之大，但也不是个质数。高斯已经证明，一个正多边形能用直尺和圆规作出当且仅当边数为质数的Fn或若干个为质数的Fn的乘积。梅森素数17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：当2^p-1中的p是质数时，2^p-1是质数。他验算出：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2^p-1是质数。p=2，3，5，7时，2^p-1都是素数，但p=11时，所得2,047=23×89却不是素数。梅森去世250年后，美国数学家科勒证明，2^67-1=193,707,721×761,838,257,287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。质数排列得杂乱无章，也给人们寻找质数规律造成了困难。目前最大的已知质数是梅森质数2^57,885,161－1。迄今为止，人类仅发现48个梅森质数。由于这种质数珍奇而迷人，它被人们称为“数学珍宝”。中国数学家和语言学家周海中根据已知的梅森质数及其排列，巧妙地运用联系观察法和不完全归纳法，于1992年正式提出了梅森素质分布的猜想(即周氏猜测)。相关定理\o"编辑本段"素数定理素数定理描述素数的大致分布情况。素数的出现规律一直困惑著数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义π(x)为不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。以下是第一个这样的估计。π(x)≈x/lnx其中lnx为x的自然对数。上式的意思是当x趋近∞，π(x)和x/lnx的比趋近1（注：该结果为高斯所发现）。但这不表示它们的数值随着x增大而接近。下面是对π(x)更好的估计：π(x)=Li(x)+O(xe^(-(lnx)^(1/2)/15)，当x趋近∞。其中Li(x)=∫(dt/lnx2,x)，而关系式右边第二项是误差估计。素数定理可以给出第n个素数p(n)的渐近估计：p(n)～n/lnn.它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个，它是素数的概率大约是1/lnn。这定理的式子於1798年法国数学家勒让德提出。1896年法国数学家哈达玛(JacquesHadamard)和比利时数学家普森(CharlesJeandelaVallée-Poussin)先後独立给出证明。证明用到了复分析，尤其是黎曼ζ函数。因为黎曼ζ函数与π(x)关系密切，关于黎曼ζ函数的黎曼猜想对数论很重要。一旦猜想获证，便能大大改进素数定理误差的估计。1901年瑞典数学家HelgevonKoch证明出，假设黎曼猜想成立，以上关系式误差项的估计可改进为:π(x)=Li(x)+O(x^(1/2)lnx)至於大O项的常数则还未知道。素数定理有些初等证明只需用数论的方法。第一个初等证明于1949年由匈牙利数学家保罗·艾狄胥（“爱尔多斯”，或“爱尔多希”）和挪威数学家阿特利·西尔伯格合作得出。在此之前一些数学家不相信能找出不需借助艰深数学的初等证明。像英国数学家哈代便说过素数定理必须以复分析证明，显出定理结果的「深度」。他认为只用到实数不足以解决某些问题，必须引进复数来解决。这是凭感觉说出来的，觉得一些方法比别的更高等也更厉害，而素数定理的初等证明动摇了这论调。Selberg－艾狄胥的证明正好表示，看似初等的组合数学，威力也可以很大。但是，有必要指出的是，虽然该初等证明只用到初等的办法，其难度甚至要比用到复分析的证明远为困难。算术基本定理任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=(P_1^a1)*(P_2^a2)......(P_n^an),这里P_1<P_2<...<P_n是质数，其诸方幂ai是正整数。这样的分解称为N的标准分解式。算术基本定理的内容由两部分构成：分解的存在性、分解的唯一性（即若不考虑排列的顺序，正整数分解为素数乘积的方式是唯一的）。算术基本定理是初等数论中一个基本的定理，也是许多其他定理的逻辑支撑点和出发点。此定理可推广至更一般的交换代数和代数数论。高斯证明复整数环Z[i]也有唯一分解定理。它也诱导了诸如唯一分解整环，欧几里得整环等等概念。更一般的还有戴德金理想分解定理。素数等差数列等差数列是数列的一种。在等差数列中，任何相邻两项的差相等。该差值称为公差。类似7、37、67、97、107、137、167、197。这样由素数组成的数列叫做等差素数数列。2004年，格林和陶哲轩证明存在任意长的素数等差数列。2004年4月18日，两人宣布：他们证明了“存在任意长度的素数等差数列”，也就是说，对于任意值K，存在K个成等差级数的素数。例如K=3，有素数序列3,5,7（每两个差2）……K=10，有素数序列199,409,619,829,1039,1249,1459,1669,1879,2089（每两个差210）。未解之谜哥德巴赫猜想：是否每个大于2的偶数都可写成两个素数之和？孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？斐波那契数列内是否存在无穷多的素数？是否有无穷多个的梅森素数？在n2与（n+1）2之间是否每隔n就有一个素数？是否存在无穷个形式如X2+1素数？黎曼猜想素数的应用质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。素数的最新成果\o"编辑本段"数论是纯粹数学的分支之一，主要研究整数的性质。而整数的基本元素是素数（也称质数），所以数论的本质是对素数性质的研究。数论被高斯誉为“数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题，叫做“皇冠上的明珠”，以鼓励人们去“摘取”。发现已知的最大素数美国中央密苏里大学数学家柯蒂斯·库珀领导的研究小组通过参加一个名为“互联网梅森素数大索”（GIMPS）的国际合作项目，于2013年1月25日发现了目前已知的最大素数——2^57885161-1（即2的57885161次方减1）。该素数是第48个梅森素数，有17425170位；如果用普通字号将它连续打印下来，其长度可超过65公里！美国数学学会发言人迈克·布林宣称：这是数论研究的一项重大突破。研究小组在大约1000台大学里的计算机上运行GIMPS的软件，每台计算机都不间断地用了39天时间证明2^57885161-1是个素数。之后其他研究者也独立验证了这一结果。库珀通过参加GIMPS项目一共发现了3个梅森素数。寻找梅森素数已成为发现已知最大素数的最有效途径。如今世界上有180多个国家和地区近28万人参加了GIMPS项目，并动用超过79万台计算机联网来寻找新的梅森素数。梅森素数是否有无穷多个？这是一个尚未破解的著名数学谜题。证明“弱孪生素数猜想”美国新罕布什尔大学数学家张益唐经过多年努力，在不依赖未经证明推论的前提下，率先证明了一个“弱孪生素数猜想”，即“存在无穷多个之差小于7000万的素数对”。4月17日，他将论文投稿给世界顶级期刊《数学年刊》。美国数学家、审稿人之一亨里克·艾温尼科评价说：“这是一流的数学工作。”他相信不久会有很多人把“7000万”这个数字“变小”。尽管从证明弱孪生素数猜想到证明孪生素数猜想还有相当的距离，英国《自然》杂志在线报道还是称张益唐的证明为一个“重要的里程碑”。由于孪生素数猜想与哥德巴赫猜想密切相关（姐妹问题），很多数学家希望通过解决这个猜想，进而攻克哥德巴赫猜想。值得一提的是，英国数学家戈弗雷·哈代和约翰·李特尔伍德曾提出一个“强孪生素数猜想”。这一猜想不仅提出孪生素数有无穷多对，而且还给出其渐近分布形式。中国数学家周海中指出：要证明强孪生素数猜想，人们仍要面对许多巨大的困难。解开“弱哥德巴赫猜想”2013年5月13日，秘鲁数学家哈拉尔德·赫尔弗戈特在巴黎高等师范学院宣称：证明了一个“弱哥德巴赫猜想”，即“任何一个大于7的奇数都能被表示成3个奇素数之和”。他将论文投稿给全球最大的预印本网站（arXiv）；有专家认为这是哥德巴赫猜想研究的一项重大成果。不过，其证明是否成立，还有待进一步考证。赫尔弗戈特在论证技术上主要使用了哈代-李特尔伍德-维诺格拉多夫圆法。在这一圆法中，数学家创建了一个周期函数，其范围包括所有素数。1923年，哈代和李特尔伍德证明，假设广义黎曼猜想成立，三元哥德巴赫猜想对充分大的奇数是正确的；1937年，苏联数学家伊万·维诺格拉多夫更进一步，在无须广义黎曼猜想的情形下，直接证明了充分大的奇数可以表示为3个素数之和。英国数学家安德鲁·格兰维尔称，不幸的是，由于技术原因，赫尔弗戈特的方法很难证明“强哥德巴赫猜想”，即“关于偶数的哥德巴赫猜想”。如今数学界的主流意见认为：要证明强哥德巴赫猜想，还需要新的思路和工具，或者在现有的方法上进行重大的改进。初等证明\o"编辑本段"素数定理有些初等证明只需用数论的方法。第一个初等证明於1949年由匈牙利数学家保罗·艾狄胥（“爱尔多斯”，或“爱尔多希”）和挪威数学家阿特利·西尔伯格合作得出。在此之前一些数学家不相信能找出不需借助艰深数学的初等证明。像英国数学家哈代便说过素数定理必须以复分析证明，显出定理结果的「深度」。他认为只用到实数不足以解决某些问题，必须引进复数来解决。这是凭感觉说出来的，觉得一些方法比别的更高等也更厉害，而素数定理的初等证明动摇了这论调。Selberg－艾狄胥的证明正好表示，看似初等的组合数学，威力也可以很大。但是，有必要指出的是，虽然该初等证明只用到初等的办法，其难度甚至要比用到复分析的证明远为困难。质数趣谈\o"编辑本段"孪生素数和广义孪生素数众所周知，孪生素数指的是恰好相差2的两个质数。为什么是相差2，不是相差1呢？相差1的质数只有2和3一对（偶质数只有一个），太平凡；而相差2的有无穷多对，而且规律难以捉摸，这就成为了数学家们乐此不疲的研究课题。不少人相信，孪生素数有无穷多对，不过这个猜想至少未证明，却成为了数学界上最著名的未解问题之一[6]。而“广义”的“孪生”素数则是指相差不超过k的一对素数。有人说，这种素数不是很常见吗？比如k等于10的时候，在1000以内这种“广义”的孪生素数俯拾即是，不是很平凡吗？非也。众所周知，离原点越远，质数越稀疏，故数字大的时候这种广义孪生质数没有想象中这么容易找到。同时，既然孪生素数猜想这么难证明，我们可以退求其次，证明“广义孪生素数”有无穷多对，哥德巴赫猜想就是这么一步一步发展的——从（9+9）到（1+5）再到（1+4）（1+3）（1+2），至今距离哥德巴赫猜想本身——（1+1）只剩一步之遥了。数论一般都是如此，用最普通的数学归纳基本上是不可