素数定理

定理描述素数素数的大致分布情况。 素数的出现规律一直困惑著数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义π(x)为不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。以下是第一个这样的估计。 π(x)≈x/ln x 其中ln x为x的自然对数。上式的意思是当x趋近∞，π(x) 和x/ln x的比趋 近1（注：该结果为高斯所发现）。但这不表示它们的数值随着x增大而接近。 下面是对π(x)更好的估计： π(x)=Li (x) + O (x e^(-(ln x)^(1/2)/15)，当 x 趋近∞。 其中 Li(x) = ∫(dt/ln x2,x)，而关系式右边第二项是误差估计，详见大O符号。 下表比较了π(x)，x/ln x和Li(x)： x π(x) π(x) - x/ln(x) Li(x) - π(x) x/π(x)素数定理可以给出第n个素数p(n)的渐近估计： :p(n)～n/ln n. 它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n。 这定理的式子於1798年法国数学家勒让德提出。1896年法国数学家哈达玛(Jacques Hadamard)和比利时数学家普森(Charles Jean de la Vallée-Poussin)先後独立给出证明。证明用到了复分析，尤其是黎曼ζ函数。 因为黎曼ζ函数与π(x)关系密切，关于黎曼ζ函数的黎曼猜想对数论很重要。一旦猜想获证，便能大大改进素数定理误差的估计。1901年瑞典数学家Helge von Koch证明出，假设黎曼猜想成立，以上关系式误差项的估计可改进为 :π(x)=Li (x) + O (x^(1/2) ln x) 至於大O项的常数则还未知道。

一个正整数a大于或等于3有且仅有1和a本身两个数因子时，a就是奇素数，表为：3≤a＜＝＞1×1＝p，这个素数定理是符合法则的。

证 由素数定理知 Mn+12(√Mn-1) (1)π(Mn)=--------------- 由中华素数定理的定义域知maxAm=√Mn-1 Am 设在区间[Mn,2Mn]含有的素数差是dn 则只须证明 (2)dn=π(2Mn)-π(Mn)≥1 [2,2n] n=1,2,3,,,+∞ 定理得证 2Mn+12(√2Mn-1) Mn+12(√Mn-1)因为dn={[---------------]-[ ---------------]} √2Mn-1 √Mn-1 (√2Mn+1)(√2Mn-1)+12(√2Mn-1)+1 (√Mn+1)(√Mn-1)+12(√Mn-1)+1 ={[---------------------------------]-[-------------------------------] √2Mn-1 √Mn-1 =√2Mn+12-√Mn-12 =√2Mn-√Mn =(√2-1)√Mn因此 当Mn≥6时 dn≥1 当n=1时,Mn=2n=2,2Mn=2×2=4在[2,4]之间有素数3 当n=2时,Mn=2n=4,2Mn=8 在[4,8]之间有素数5,7 定理证毕.当Mn→∞,[π(2Mn)-π(Mn)]→∞ limdn=lim[(√2-1)√Mn]→∞ Mn→∞ Mn→∞欢迎批评指教!

素数定理在（）被证明出来。 A.1894年B.1895年C.1896年D.1893年正确答案：C

素数定理的式子是（）提出的。 A.黎曼B.柯西C.欧拉D.勒让德正确答案：D

素数定理必须以复分析证明。（） A.正确 B.错误 正确答案：A

25岁的前苏联数学家什尼列尔曼(1905～1938)，创造了“正密率法”，首先把朗道所说的“C个”确定为不大于80万。C的结果年代获得结果的数学家20081935前苏联罗曼诺夫(1907～？)711936德国或加拿大海尔布隆(1908～1975)、德国朗道、德国西尔克671937意大利雷西201950美国夏彼罗、美国瓦尔加(1922～)181956中国尹文霖(1928～1985)此外，在1937年，前苏联数学家维诺格拉多夫(1891～1983)用改进了哈代和李特尔伍德等在20世纪20年代创立的“圆法”，和他本人独创的“三角和估计法”，基本上完全证明了“三素数猜想”，使它成为“三素数定理”。这里提到的哈代(1877～1947)和李特尔伍德(1885～1977)，都是英国数学家。

下面是对π(x)更好的估计：, 其中. 而关系式右边第二项是误差估计，详见大O符号。 下表比较了π(x)，x/ln x和Li(x)： x π(x) π(x) - x/ln(x) Li(x) - π(x) x/π(x)（如图所示）素数定理可以给出第n个素数p(n)的渐近估计：它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n。 这定理的式子於1798年法国数学家勒让德提出。1896年法国数学家哈达玛(JacquesHadamard)和比利时数学家普森(Charles Jean de la Vallée-Poussin)先後独立给出证明。证明用到了复分析，尤其是黎曼ζ函数。 因为黎曼ζ函数与π(x)关系密切，关于黎曼ζ函数的黎曼猜想对数论很重要。一旦猜想获证，便能大大改进素数定理误差的估计。1901年瑞典数学家Helge von Koch证明出，下式与黎曼猜想等价:至于大O项的常数则还未知道。 在1948年, 塞尔伯格和保罗·埃尔德什首次给出素数定理的初等证明.

1、素数定理（prime number theorem）是素数分布理论的中心定理。 2、关于素数个数问题的一个命题：设x≥1，以π(x)表示不超过x的素数的个数，当x→∞时，π(x)～Li(x)或π(x)～x/ln(x)。（Li(x)为对数积分）。

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。所以，质数是合数的基础，没有质数就没有合数。这也说明了前面所提到的质数在数论中有着重要地位。历史上曾将1也包含在质数之内，但后来为了算术基本定理，最终1被数学家排除在质数之外，而从高等代数的角度来看，1是乘法单位元，也不能算在质数之内，并且，所有的合数都可由若干个质数相乘而得到。

定理描述素数素数的大致分布情况.素数的出现规律一直困惑著数学家.一个个地看,素数在正整数中的出现没有什么规律.可是总体地看,素数的个数竟然有规可循.对正实数x,定义π(x)为不大于x的素数个数.数学家找到了一些函数来估计π(x)的增长.以下是第一个这样的估计.:pi(x)approxfrac 其中ln x为x的自然对数.上式的意思是当x趋近∞,π(x) 和x/ln x的比趋近1（注：该结果为高斯所发现）.但这不表示它们的数值随着x增大而接近.下面是对π(x)更好的估计：:pi(x)= (x) + O left(x e^ ight),当 x 趋近∞.其中 (x) = int_2^x frac,而关系式右边第二项是误差估计,详见大O符号.下表比较了π(x),x/ln x和Li(x)：x π(x) π(x) - x/ln(x) Li(x) - π(x) x/π(x)

          素数定理给出的是估计素数个数的方法：           设π(x)是小于x的素数的个数，则           π(x)≈x/lnx           eg：                64位二进制表示的素数的个数为                     (1)欧拉定理            提及欧拉定理，需要先引出欧拉函数的定义：            欧拉函数Φ(n)是定义在正整数上的函数，Φ(n)的值等于序列0,1,2,3,…,n-1中与n互素的数的个数            欧拉函数的性质：                    (1)m的素数时，有Φ(m)=m-1                    (2)m=pq,且p和q均是素数时，有Φ(m)=Φ(p)Φ(q)=(p-1)(q-1)                    (3)若m和n互素，则Φ(m×n)=Φ(m)×Φ(n)                    (4)若p是一个素数，则Φ(p^e)=p^e-p^(e-1)                    (5)          由欧拉函数可以延伸出欧拉定理的内容：                     欧拉定理:                               对于任何互素的两个整数a和n，有                                         1(mod n)                                如果n=p是素数,则有                                         1(mod p)                              显然欧拉定理可以看成是费马定理的推广形式。                     欧拉定理可以用来简化幂的模运算                     Eg：                            求 的后三位数字                           解：     (mod 1000)的结果                                                                          有 (mod 1000)      (2)费马定理            如果p是素数，a是正整数，且gcd(a,p)=1，那么                    1(mod p)           另一种形式：                如果p是素数，a是任意正整数，则对gcd(a,p)=1,有                    (mod p)      (3)二次探测定理           如果p是一个素数，且0<x<p,则方程 1(mod p)的解为 x = -1、p-1。           即如果符合 1(mod p)，那么p很有可能是素数，但是仍不能肯定p就是素数。      (1)Wilson定理           对于给定的正整数n，判断n是一个素数的充要条件是 -1(mod n)。           虽然是充要条件，且Wilson的定理有很高的的理论介质。因为带有阶乘，在检测的时候计算量大，不适合检测较大素数的检测。      (2)米勒-拉宾算法           米勒-拉宾算法是一个多项式算法，能以接近概率1保证判断结果的正确性。           Miller-Rabin(n)           把n-1写成 ，其中m是一个奇数           选取随机整数a，使得                (mod n)                If (mod n)                     Return (‘n是素数")                End                For i=0到k-1                     If b≡-1(mod n)                          Return (‘n是素数")                     Else                          b=b^2(mod n)                     End                End                     Return(‘n是合数") 欧几里得算法描述：           两个整数用a，b表示，商用q表示，余数用r表示           Step1      取a，b较大者为a，较小者为b           Step2      做除法，计算并保留余数r=mod(a,b)           Step3      将原来的除数改做被除数，余数作为除数a=b,b=r           重复Step1和Step2直到r=0,返回b 乘法逆元的定义：           假设gcd(a,n)=1,则存在整数s，使得 (mod n)，即s是a(mod n)的乘法逆元素。      关于ax+by=d           设a和b是两个正整数(至少有一个非零)，d=gcd(a,b),则存在整数x和y使得ax+by=d成立，如果a、b互素，那 么存在整数x和y使得ax+by=1成立，此时可以求出ax≡1(mod b)中的x，即为逆元。 扩展欧几里得算法： 构造两个数列：                 Eg：                  求28mod75的乘法逆元(a=75,b=28)                       gcd(28,75)=1 所以存在逆元                       75=2×28+19                       28=1×19+9                       19=2×9+1                       9=9×1+0                        3×78+(-8)×28=1                        所以28mod75的乘法逆元为-8     中国剩余定理完整版            Eg：                    已知下列同余方程组，求解x                    第一步：求M                          M=2×3×5×7=210                    第二步：求                                            第三步：求                         1(mod )(i=1,2,...,k)                    第四步:                          (mod M)                          (105×1×1+70×1×2+42×3×3+30×4×5)(mod 210)                          173(mod 210)

定理描述素数的比较准确的分布情况。素数的出现规律一直困惑著数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义π(x)为不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。其中有二个公式是极为重要的，一个是高斯公式，另一个是黎曼公式，素数分布定理是以黎曼公式为中心，以高斯公式为上限的正态分布，这是经过大量大数计算和统计所得出的经验定理，也可以称为素数正态分布定理猜想，有待数学家在数学上给出严格的证明。

因为gcd(a,n)=1可以推出a^(phi(n)-1) = 1 (mod n) 【费马小定理的一般形式，证明可以考虑一个mod n的完全剩余系】然后由定理2的条件知道phi(n)不能是1到n-2，所以只能是phi(n)=n-1。（定理2条件中是否应该是小于等于n-1？也可以证明除了n=4以外不可能phi(n)=n-2。）所以由定理1，n是素数。

关于素数的哪一个定理？

若用π(n)表示不超过n的素数的个数.当n→+ 时, =+ .人们可以发现:顺着自然数的序列,越往后素数的密度 π(n)/ n就变得越小7.1.2 陈氏定理―数学皇冠上的明珠哥德巴赫猜想(1742年)每个偶数都是两个素数之和;每个奇数都是三个素数之和哥德巴赫猜想的研究进展数学家哈代和李特尔伍德(英国,1923年)在广义黎曼猜想正确的前提下,有条件地证明了每个充分大的奇数都是三个奇素数之和以及几乎所有偶数都是两个奇素数之和.维诺格拉多夫(1937年),无条件地证明了奇数哥德巴赫猜想,即每个充分大的奇数都是三个奇素数之和布朗(挪威1919年)证明了:每个大偶数都是两个素因子个数均不超过9的整数之和(记为9 + 9,记号k + l表示大偶数分解为不超过k个奇素数的积与不超过l个奇素数的积之和,下同)布赫夕塔布的4 + 4(1940),瑞尼的l+c (c为一不确定大数)(1948)和库恩的a+b (a+b≤6)(1954);王元的2+3(1957)和潘承洞的1+5(1962),到1965年,欧洲数学家邦别里等三人差不多同时证明了1 + 3;1966年,中国数学家陈景润宣布证明了1+2(1973年发表详细证明)陈景润(1933~1996)简介图7.1华罗庚(右)与陈景润(左)7.1.3费马最后定理费马猜想:对每个正整数n≥3,方程xn + yn = zn均没有正整数解(x, y, z).费马本人利用无限下降法证明了n=4时,费马猜想成立.1825年年仅20岁的德国数学家狄利克雷和年过七旬的法国数学家勒让德各自独立地证明了n = 5的情形,1839年法国数学家拉梅证明了n = 7的情形.欧拉的整数分解的定理:由a + b 形式的数所形成的数系(记为 ,a,b为任意整数)中,有唯一因子分解定理成立,即每一个整数都可唯一地分解为这个数系中数的乘积.后来才知道,对形如 的数系,唯一因子分解定理并不总是成立的,例如在数系 中,6 = 3×2 =(1+ )(1- ),就有两种分解方式.事实上,能保证唯一因子分解定理成立的数系 只有9种德国的数学家库默尔(1810~1893)利用理想数的概念,证明了对于 100以内的所有素数,都能使费马猜想成立.志村-韦伊―谷山猜想――费马猜想的等价命题怀尔斯的论文模曲线和费马最后定理 (1994年)――费马猜想终于成为定理,被称为费马大定理或费马最后定理7.1.4 让我们教猜想吧费马猜想是只会下金蛋的鹅1966年菲尔兹奖获得者,英国数学家阿蒂亚(1929~)认为:与其它自然科学的情况一样,数学中的一些发现也要经过几个阶段才能实现,而形式证明只是最后一步.最初阶段在于鉴别出一些重要的事实,将它们排列成具体含义的模式,并由此提炼出看起来很有道理的定律或公式.接着,人们用新的经验事实来检验这种公式.只是到了此时,数学家们才开始考虑证明问题.1958年菲尔兹奖获得者,突变理论的创立者,法国数学家托姆用半开玩笑的态度说:严格性是一个拉丁名词.我们会想起僵死(rigormorits),即僵化的尸体.我要把数学分为以下的三类:第一,以婴儿摇篮为标记.这是"活的数学"允许改变,澄清,完成证明,反对,反驳.第二,以十字架为标记.这是坟墓上的十字架.作者声明它已完全严格,具有不朽的正确性.这类工作将构成"坟墓数学".第三,以教堂为标记.这是外部的权威,由高级教士组成,判断哪些工作已成为"坟墓数学".推测数学家的成功范例之一是印度数学家拉马努金(1887~1920)波利亚认为,在数学教育中,证明与猜想,这两类推理即论证的与合情的都必须教给学生,在有些情况下教猜想比教证明更为重要.因此,波利亚强烈的呼吁:让我们教猜想吧!

质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。所以，质数是合数的基础，没有质数就没有合数。这也说明了前面所提到的质数在数论中有着重要地位。历史上曾将1也包含在质数之内，但后来为了算术基本定理，最终1被数学家排除在质数之外，而从高等代数的角度来看，1是乘法单位元，也不能算在质数之内，并且，所有的合数都可由若干个质数相乘而得到。

无法证明，也不需要证明，因为这个命题不成立。对n=1，2，3 ...100 进行验证，有40多个结果不是素数。见下图：同时附上验证计算的fortran代码：

素数定理有些初等证明只需用数论的方法。第一个初等证明由1949年由匈牙利数学家保罗·厄多斯（另译埃尔德什、艾狄胥、“爱尔多斯”，或“爱尔多希”）和挪威数学家阿特利·西尔伯格合作得出。 在此之前一些数学家不相信能找出不需借助艰深数学的初等证明。像英国数学家哈代便说过素数定理必须以复分析证明，显出定理结果的「深度」。他认为只用到实数不足以解决某些问题，必须引进复数来解决。这是凭感觉说出来的，觉得一些方法比别的更高等也更厉害，而素数定理的初等证明动摇了这论调。Selberg－艾狄胥的证明正好表示，看似初等的组合数学，威力也可以很大。 但是，有必要指出的是，虽然该初等证明只用到初等的办法，其难度甚至要比用到复分析的证明远为困难。

素数分布规律一直是人类探索素数的伟大目标。自欧拉、高斯到黎曼，许多数学家都做出了巨大努力和贡献。高斯发现的素数定理，表明素数分布与对数积分的关系，但对不大于给定数值的素数个数的预测结果，其准确率不高。揭示素数分布的秘密，找到一个可准确计算预测素数个数的普适公式，是当前素数研究的紧迫任务什么是素数。素数是我们小学就学习过的数学概念。素数是指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。 否则称为合数。人们经常把它类比成化学中的基本元素，化学中有100多种基本元素，这些基本元素可以构成我们这个色彩缤纷的世界。比如 两个氢原子和一个氧原子可以构成水分子， 甲烷就是 一个碳原子和四个氢原子等等。同样的道理，一个大于1的自然数，要么是素数，要么是几个素数的乘积。在数论中，还有一个概念，任何一个合数，都可以分解成几个素数的乘积，而且合数的因数分解是唯一的。这个理论非常重要，它更加明确的确立了素数在数论体系中的地位，就像水分子只能分解为两个氢原子和一个氧原子，一个合数，只能分解为唯一的一组素数的乘积。比如 120 只能分解为 2*2*2*5*3。关于这个因数分解的唯一性的证明，可以参考 加州理工大学Tom Apostol 教授的数学分析，第二版的第六页。加州理工大学 Tom Apostol 教授的数学分析因数分解唯一性的 证明素数有多少呢？这问题早在约公元前300年时，就已被欧几里得解决。他发现素数有无穷多个。而且证明起来也非常巧妙。不妨假设我们目前发现了 m 个素数，（2， 3， 5， 。。。pm ）现在考虑它们的积再加1 ： （2 * 3 * 5 * … .. * pm + 1），这是一个比刚才已经发现的m 个素数都大的数，也是一个自然数。它是素数吗？如果是，那我们就得到一个新的素数。注意一下，这里构造出来的数 （2 * 3 * 5 * … .. * pm + 1），和刚刚已知的最大素数pm 之间其实还是会有其他素数的。比如 假设我们目前只知道2 ， 3，5 这三个素数，通过刚刚的公式可以得到 2*3*5+1=31 ， 31 是一个比我们已知的2 和3 还大的素数，但是在已知素数（2， 3，5）和求得的素数（31）之间，7，11， 13， 23，等等也是素数。如果不是，那么 既然这个数按照定义不能被 那些m 个素数整除，必然存在其他的素数，可以整除它，所以还是会存在新的没发现的素数。比如，目前我们发现2，3，5，7，11，13 这几个素数，然后通过 2x3x5x7x11x13+1=30031，我们发现30031 不是素数，但是30031不能被 2，3，5，7，11，13 整除，所以必然存在其他素数。结果我们发现 30031=59*509. 所以我们还是可以发现新的素数。