素数与算术基本定理

1、素数,定义1,设,若,的正因数只有 和它本身,则,称为素数,否则 称为合数.,正整数,素数,合数,唯一的偶素数,算术基本定理,素数与合数的基本性质,设,是合数,则,1),存在整数,使得,2),存在素数,使得,且,例如,判定,是否为素数.,所以,是素数.,合数必有素因子,素数与合数的基本性质,设,是素数,则,1),对任意整数,有,2),若,则,或,或,例1,设,是素数,求,的所有可能值.,解,设,则,定理1,素数有无穷多.,证,假定素数有有限多个,设,是全体素数.,令,设,是,的素因数,则,这是因为若,就有,是素数矛盾.,这与,推论,设,是第 个素数,则,厄拉多塞 (Eratosthenes)筛

2、法,求不超过 的全体素数:,首先列出不超过 的所有素数.,设为,依次排列,在其中留下,划去,的所有倍数,再留下,把 的倍数划掉,继续这一手续,直到最后留下,而划去,的所有倍数.,求 以内的全部素数,素数的分布,1)随着整数范围的扩大，素数是不是越来越稀疏？稀疏的程度是否单调地增加？,3）间隔差为2的素数对是否有无穷多个? 更一般地, 间隔差为某一个固定偶数的素数对是否有无穷多个? 是否存在相邻的素数, 其间隔值可以任意大?,2）相邻素数之间的间隔值有哪些? 它们各重复多少次? 随整数范围扩大, 最大间隔值是否也随之增大?,用,表示,不超过,实数,的素数的个数.,所以,Gauss,1792,Le

3、gendre,1798,素数定理,Hadamard, de la Valle Poussin,1896年.,A. Selberg, P. Erds ,1949年.,Erds 1913-1996,Hadamard1865-1963,Poussin 1866-1962,Selberg 1917-2007,有没有公式可以比素数定理更精确地描述素数的分布呢？,算术级数中的素数,对任意正整数,存在连续的 个正整数,它们,都是合数.,证,考虑 个正整数,则,算术级数中的素数,(Dirichlet,1837),若正整数,互素,则,存在无穷多形如,的素数.,存在长度为,如,Green-Tao定理,是否存在任意

4、长度相邻,素数的等差数列?,陶哲轩,1975-,等差为,素数列,有关素数的猜想,1) 每个不小于6的偶数都可以表为两个奇素数之和;,2) 每个不小于9的奇数可以表为三个奇素数之和.,哥德巴赫(Goldbach) 猜想,(1742年),1937，苏联数学家Vinogradov证明，充分大的奇数可以表为三个素数的和.,1900年，Hilbert在巴黎世界数学家大会上提出23个问题供20世纪数学家研究。其中第8问题中将Goldbach猜想作为最重要的问题之一提出.,英国伦敦Faber出版社2000年3月悬赏100万美金征解Goldbach猜想.,1938年，华罗庚证明：几乎所有大于6的偶数均可表示成

5、两个奇素数之和.,1966 陈景润 证明 (1 + 2),1958 王元 证明 (2 + 3),1962 潘承洞 证明 (1 + 5),1963 王元、潘承洞 证明 (1 + 4),1965 Vinogradov 证明 (1 + 3),目前计算结果表明, 在,之前的偶数都,满足哥德巴赫猜想.,If you could be the Devil and offer a mathematician,I think it would be the Riemann Hypothesis.,to sell his soul for the proof of one theorem,- what theo

6、rem would most mathematicians ask for?,- H. Montgomery,Riemann 1826-1866,Riemann猜想（RH）,Riemann 1859 年,“论不大于一个给定值的素数的个数”,2005年5月24日,Clay数学研究所将黎曼猜想作为七个千禧年数学难题之一公开悬赏征解.,Euler乘积公式,Riemann,函数,令,对 函数在复平面作解析延拓,有,都是,的平凡零点.,Riemann 猜想,的所有非平凡零点都位于复平面上,的直线上.,Riemann素数公式,Mertens猜想,A.M. Odlyzko等,1984年证明,对所有实数,有,

7、RH,对任意正数,Mertens函数,反例,若,是代数数,是无理代数数,则,是超越数.,猜想,猜想,1935年,Fermat猜想,Riemann 猜想,1995年,?,（Hilbert 第7问题）,孪生素数猜想,（Twin prime conjecture）,是否存在无限多素数对,如,2013年5月，Yitang Zhang 证明,张益唐 1955-,2013年7月，Engelsma 证明,The,conjecture,形如 的素数有无限多.,任给正整数,在,和,之间是否一定,存在素数?,素数的判定,是素数,Fermat判别法,基于广义黎曼猜想的判别,表示素数的公式,Miller,1947,存

8、在,使得,都是素数.,Euler,1772,设,则,时,都是素数.,Hardy,1979,其中,且,Ruiz, 2000,其中,任给正整数,不存在整系数多项式,使得,都是素数.,取所有,的整数时,算术基本定理,定理2,设,则,其中,是素数,且若,是素数,其中,则,注,对其它类型的数,唯一分解定理未必成立.,如,的标准分解式,设,则,对任意素数,其中,有,其中,是互不相同的素数,设,且,则,求,例2,设,是素数,证明,是无理数.,证,若,是素数,是有理数,设,则,所以,令,有,这与,矛盾.,例3,设,且,的标准分解式为,证明,若对某个,则,证,若,则,设,有,讨论,例4,若 是素数,证明,证,由

9、,及,可知,所以,例5,设,证明,若 是素数,则,且,是素数.,证,由,及,若,知,是合数.,这与已知矛盾.,若,是合数,设,由,及,知,是合数.,这又与已知矛盾.,例6,设,证明 若,是素数,则,也是素数.,证,由,若,是合数,设,及,知,是合数,这与已知矛盾.,例7,求所有正整数,使得,解,设,则,所以,与,定义2,设,则,的所有不同的正因数的,个数记为,的所有不同的正因数之和记为,设,的标准分解式为,若,则,因此,又,例8,性质,若,则,及,证明,1),是奇数,是平方数.,2),是素数,例9,证明,设,证明,约定,等价于,则,设,可表示为若干不同素数方幂的乘积,表示法个数（不计次序）记为

10、,显然,习题,1）,由,收敛且大于,得,因此,故,收敛，,从而,2）,对任给的正整数,收敛且大于,设,因此,对任给的正整数,令,令,得,所以,习题,证明,形如,的素数有无穷多.,证明,形如,的素数有无穷多.,证明,若,是素数,则,证明,若,则,是合数，,证明,若,是素数,则,且,证明,若,求,1),2),所有正整数,恰有4个正因数.,为其真因数之积,证明,一个素数的立方或是两个不同素数的乘积.,习题,是,不是整数.,习题,如果一个整数不能被任一个素数的平方,所整除则叫做无平方因子.,证明,对每个整数,存在唯一的,使得,其中,无平方因子.,证明,若,是 的最大平方因子,则由,可推出,设,证明,证

11、,设,是素数,对整数,有,即,若,为素数,则,而,至多有 个,使得,若,则 是素数.,判别法的计算量为,若该算法成立的话,但,是合数.,若 是合数,且,则称 是以 为底,的伪素数.,在 之内，以 为底的伪素数不到,素数的百万分之三.,出错概率约小于,上述算法的计算量为,(Miller,1976),若广义黎曼猜想成立, 对任何整数 ,若 为合数，则存在,使得,由此可以设计如下多项式算法,对任意n, 依次对,检验上式是否成立.,若对每一个a都不成立，,则 为素数,否则 为合数.,证,假定形如 素数有有限多个,设为,令,则,至少有一个,素因子,形如,而,这与假设矛盾.,证,1),时,的所有素因子,都形如,若素数,是其素因子,由,有,又,则,所以,2),取,足够大.,证,对,作归纳法.,结论成立.,假定结论对 成立,对,情形,及,可知结论成立.,即,由,证,设,为奇数.,若,由,及,知,是合数.,证,设,若,则,是,到,之间不同,的两个数.,若,则,时,到,之间不同,所以,是,的两个数.,证,对任意正整数,有,无平方因子.,考虑所有正整数对,无平方因子.,整数对,至少,对.,而,无平方因子,最多有,个.,所以,取,有,满足,解,设,解,由已知,所以,证,设,令,则,无平方因子.,若另有,无平方因子.,对 的任一