素数与算术基本定理

素数定义1设,1a若的正因数只有和它本身,,5,3,21则a称为素数,否则称为合数.a正整数1素数合数唯一的偶素数a算术基本定理素数与合数的基本性质设a是合数,则1)存在整数,,lk,,1alk使得.kla2)存在素数,q使得,|aq且.aq例如,判定359是否为素数.1935918359|17,13,11,7,3,3,2所以359是素数.合数必有素因子素数与合数的基本性质设q是素数,则1)对任意整数有2)若则,|aq或.|bq,n,|nq或.1),(nq,|abq例1设p是素数,求.),(pba),(32ba的所有可能值.解设,1paa,1pbb,1),(11ba),(),(3121232pbapba),(212pap则32pp定理1素数有无穷多.证假定素数有有限多个,设kppp,,3,221是全体素数.令,121kpppN设q是N的素因数,则.,,,21kpppq这是因为若,ipq就有是素数矛盾.,1|q这与q推论设np是第个素数,n则.1211nnpppp厄拉多塞(Eratosthenes)筛法求不超过的全体素数:N首先列出不超过的所有素数.N设为Npppk212依次排列,,,3,2N在其中留下,21p划去1p的所有倍数,再留下,2p把的倍数划掉,2p继续这一手续,直到最后留下kp而划去kp的所有倍数.求以内的全部素数530,21p,32p,53p3023457689101213141517161819201122232425272628293021素数的分布1)随着整数范围的扩大，素数是不是越来越稀疏？稀疏的程度是否单调地增加？3）间隔差为2的素数对是否有无穷多个?更一般地,间隔差为某一个固定偶数的素数对是否有无穷多个?是否存在相邻的素数,其间隔值可以任意大?2）相邻素数之间的间隔值有哪些?它们各重复多少次?随整数范围扩大,最大间隔值是否也随之增大?1-n的区间素数个数π(n)π(n)/nn100251/4n10001681/5n1000012291/8n10000095921/10用表示不超过)(x实数x的素数的个数.所以0)(limxxx)log(n)(/nnx)(xxxln/xxxln/)(42516812299592784986645793.47.218.1447.10855.6204208.86855.72382152.1071.116.193.013.1131.1084.1110310210510610710410Gauss,1792Legendre,1798.,08366.1ln~)(xxxx.,lnLi~)(0xtdtxxx素数定理.1ln/)(limxxxxHadamard,delaValléePoussin,1896年.A.Selberg,P.Erdös,1949年.Erdös1913-1996Hadamard1865-1963Poussin1866-1962Selberg1917-2007有没有公式可以比素数定理更精确地描述素数的分布呢？算术级数中的素数对任意正整数,n存在连续的个正整数,它们都是合数.n证考虑个正整数n1)!1(,,3)!1(,2)!1(nnnn则.1,,2,)!1(|njjnj算术级数中的素数(Dirichlet,1837)若正整数ba,互素,则存在无穷多形如bna的素数.存在长度为,5860445467380903975621138376k.22,,1,0k如Green-Tao定理是否存在任意长度相邻素数的等差数列?陶哲轩1975-k等差为素数列k有关素数的猜想1)每个不小于6的偶数都可以表为两个奇素数之和;2)每个不小于9的奇数可以表为三个奇素数之和.哥德巴赫(Goldbach)猜想(1742年)1937，苏联数学家Vinogradov证明，充分大的奇数可以表为三个素数的和.1900年，Hilbert在巴黎世界数学家大会上提出23个问题供20世纪数学家研究。其中第8问题中将Goldbach猜想作为最重要的问题之一提出.英国伦敦Faber出版社2000年3月悬赏100万美金征解Goldbach猜想.1938年，华罗庚证明：几乎所有大于6的偶数均可表示成两个奇素数之和.1966陈景润证明(1+2)1958王元证明(2+3)1962潘承洞证明(1+5)1963王元、潘承洞证明(1+4)1965Vinogradov证明(1+3)目前计算结果表明,在1810之前的偶数都满足哥德巴赫猜想.IfyoucouldbetheDevilandofferamathematicianIthinkitwouldbetheRiemannHypothesis.tosellhissoulfortheproofofonetheorem-whattheoremwouldmostmathematiciansaskfor?-H.MontgomeryRiemann1826-1866Riemann猜想（RH）Riemann1859年“论不大于一个给定值的素数的个数”2005年5月24日,Clay数学研究所将黎曼猜想作为七个千禧年数学难题之一公开悬赏征解.11)1(snpspn)(2cos)()2(2)1(sssssits1,)(1nsnsEuler乘积公式,1sRiemann函数令对函数在复平面作解析延拓,有都是,4,2s)(s的平凡零点.Riemann猜想)0(loglog)1()Li(Li)(20xuuuduxxxJ的所有非平凡零点都位于复平面上21)Re(s的直线上.Riemann素数公式)(s)()()(/111nnxJnnx)()(nxMxn.)(2/1xxM,1xMertens猜想A.M.Odlyzko等,1984年证明06.1)(suplim2/1xxMx对所有实数有RH)()(2/1xOxM对任意正数,Mertens函数反例0x641021.301410ex若是代数数,是无理代数数,则是超越数.猜想猜想1935年Fermat猜想Riemann猜想1995年?（Hilbert第7问题）孪生素数猜想（Twinprimeconjecture）是否存在无限多素数对?2,pp1256551646835333333p如2013年5月，YitangZhang证明71107)(inflimnnnpp张益唐1955-2013年7月，Engelsma证明?4680)(inflim1nnnppThe12nconjecture形如的素数有无限多.12n任给正整数2)1(n2n,n在和之间是否一定存在素数?素数的判定p是素数Fermat判别法1)!1(|pp基于广义黎曼猜想的判别表示素数的公式Miller,1947存在,R使得1],[)(3nfn都是素数.3064.1Euler,1772设,41)(2xxxf则39,,1,0x时,都是素数.)(xfHardy,19793,))(,(121njnfpnjn其中yxyxyxyxyxf],1[21,0),(且njjjjjn3]))!2([)!2((1)(Ruiz,2000)1]ln([212))]([11(1nnkkjnnjsp其中jsjsjjsjs1)21()(任给正整数,x不存在整系数多项式01)(axaxaxfnn使得0xx)(xf都是素数.x取所有的整数时算术基本定理定理2设,1a则,21mpppa其中,21mppp是素数,且若,21nqqqa,21nqqq是素数,ipiq其中则,nm).,,1(niqpii注对其它类型的数,唯一分解定理未必成立.},:5{)5(ZbaibaiZ如)51)(51(326ii的标准分解式a,1a设则sspppa2121对任意素数,papat其中1),(,0pat有其中ip.0i是互不相同的素数,sspppb2121.,,2,1,0siiiab|0b,0,ba设且sspppa2121sspppb2121则siiiipba1},min{),(siiiipba1},max{],[求],[ba),,(ba例2设p是素数,证明p是无理数.证若是素数,p是有理数,设,1),(,babap则22pba所以,|2ap,|ap令1paa有,221bpa,|2bp,|bp这与1),(ba矛盾.例3设,0a,0nsimiipa1且a的标准分解式为证明若对某个,ip,Qpnmii则.Qan证,)(/1yxpjnmjj若则,|xpi设,xpxti有nmntimjijnxppyij,1),(ipx,1),(yx,1t讨论,0imnt,0imnt.0imnt例4若是素数,p证明.11,|piCpip证由!)1()1(iipppCiP及1)!,(ip可知)1()1(!|ippi所以.11,|piCpipZ例5设,1a证明若是素数,1na则2a且n是素数.证由)1)(1(11aaaann及若,2a,1n1)1(1naa知1na是合数.这与已知矛盾.若n是合数,设,,1,nlkkln由)122)(12(12)1(klkkn及12)12(1nk知1na是合数.这又与已知矛盾.例6设,111ssp证明若sp是素数,则s也是素数.证由ssp1119110s若s是合数,设slkkls,1,9110kl)11010(9)110()1(klkk及skp9)110(1知sp是合数,这与已知矛盾.例7求所有正整数,,ba使得,24),(ba.144],[ba解设1132a2232b则,3),min(21,4),max(2121,2),max(21所以3142413211,2212,1),min(21与)(nd)(n定义2设,0n则n的所有不同的正因数的个数记为),(nd的所有不同的正因数之和记为n).(n设n的标准分解式为siiipn1若,|0nd则iisiiipd0,1因此)1()1)(1()(21snd又nddn|)(sssppp,,,21212111222111121ssssppp)())((11222111121sssspppsiiippi111例8性质若,1),(ba则)()()(bdadabd)()()(baab及证明1))(nd是奇数n是平方数.2)n是素数1)(nn例9证明ndd|1设,1nnn)(证明snspnp1)11(11约定n,1n等价于)(nc则设可表示为若干不同素数方幂的乘积表示法个数（不计次序）记为显然,1)(nc.1)1(c,1,1)(nnc习题1）1)11(spp由，1s收敛且大于1)1ln(1xxxxtdt01x)1(x得1)11ln(0sp)111ln(sp11sp因此1)11ln(spp