初等数论最小公倍数ppt课件

.,3最小公倍数定义：n是大于1的整数，整数的公共倍数称为的公倍数，正公倍数中最小的一个称为的最小公倍数。记成,下面考虑两个数的最小公倍数,例2，-8=8,.,定理1：设M是正整数a,b的任一公倍数，则有a,b|M,且有。证：由M的定义知有M=ac=bd,又设有因为所以，即有M=a=t,显然当t=1时最小，即.所以M=a,bt,即有a,b|M.,.,例:设正整数m是a,b的公倍数,则证明：且,.,推论：设a,b,m是正整数，则ma,mb=ma,b,证：由,下面给出n个整数的最小公倍数的方法,定理2：设为n个整数，又则有,.,证：由定义知说明是公倍数。另一方面，设m是的任一公倍数，则有又即是最小公倍数。,注：定理吿诉我们n个整数的最小公倍数可两个两个地求法,.,定理2：若正整数两两互素，则有证：由有又又由定理1有如此下去可得,实际上，反过来也对，可用数学归纳法证明，请同学们自已证明。,.,例1：求24871,3468解：因为（24871,3468）=17所以24871,3468=5073684所以24871与3468的最小公倍数是5073684。,.,5素数,定义：一个大于1的整数a若它的正因数只有1和a，则称a是素数，否则称a是合数。例2，5，7，11等都是素数，4，6，8，9等是合数。1既不是素数，也不是合数。对素数有下面的定理定理1：任意大于1的整数a的不是1的最小正因数q一定是素数。且当a是合数时有。,.,证：假设q不是素数，由定义q除1和本身外还有一正因数，但，且，这与q的最小性矛盾。即q为素数。若a是合数，则有，且，有即有,.,定理1给出了当n不是很大时，判断n是否为素数的方法爱拉托散尼筛法。如果不大于的素因子都不是a的因数，则a一定为素数因为若a是合数，则a一定有一不大于的素因子。,例：构造不大于30的素数表,.,1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23，24，25，26，27，28，29，30。（1）删去1，剩下2为素数，删去2后面2的倍数，剩下的第一数为3，3为素数，剩下数为2，3，5，7，9，11，13，15，17，19，21，23，25，27，29（2）删去3后面3的倍数，剩下的第一数为5，5是素数，剩下数为2，3，5，7，11，13，17，19，23，25，29，（3）删去5后面5的倍数，剩下数为2，3，5，7，11，13，17，19，23，29，因为小于的最大素数是5，所以最后的10个数为30内的素数。,.,A素数的个数,定理：素数的个数有无穷多个？证：假设素数只有有限个，设为k个，设为,作N=+1,显然N1,则N的非1的最小正因子q是素数，且有q|N,有,若存在某个i,使得，则有,这是不可能的，即找到了第k+1个素数，假设是错误的，即素数有无穷多个。,注:素数可分为4k+1型和4k+3型,或6k+1型和6k+5型等(2除外),.,下面证明4k+3型的素数有无穷多个证明：假设只有k个4k+3型的素数作则N必有素因子，且素因子中必有一个为4k+3型的,（因为4k+1型因子的积仍是4k+1),设4k+3的素数为q,则，否则，即找到了第k+1个素数q，假设是错误的，即4k+3型的素数有无穷多个。,.,令表示不超过x的素数个数,可以证明:它表明了:尽管素数个数无穷多,但它比起正整数的个数来少得很多.,.,1644年,法国数学家默森尼(M.Mersenne)研究过形如2p-1的素数,其中p为素数.人们称它为默森尼素数,截止2003年11月17日,发现有40个,其中220996011-1是目前最大素数.在网上(/)有个基金组织资助计算M.Mersenne)素数的志愿者.猜想默森尼素数有无穷多,但至今都尚未证明.目前是最大素数,有12837064位，超过50公里长，,.,第1941个梅森素数序号素数位数发现人时间41224036583-17235733JohnFindley200440220996011-16320430MichaelShafer200339213466917-14053946MichaelCameron20013826972593-12098960Nayan,Woltman,Kurowski19993723021377-1909526Clarkson,Woltman,Kurowski19983622976221-1895932Spence,Woltman19973521398269-1420921Armengaud,Woltman19963421257787-1378632Slowinski&Gage1996332859433-1258716Slowinski&Gage1994322756839-1227832Slowinski&Gage1992312216091-165050DavidSlowinski1985302132049-139751DavidSlowinski1983292110503-133265Welsh&Colquitt198828286243-125962DavidSlowinski198227244497-113395Slowinski&Nelson197926223209-16987L.CurtNoll197925221701-16533Nickel&Noll197824219937-16002BryantTuckerman197123211213-13376DonaldB.Gillies19632229941-12993DonaldB.Gillies19632129689-12917DonaldB.Gillies19632024423-11332AlexanderHurwitz19611924253-11281AlexanderHurwitz1961,.,B素数的稠密性,一方面素数有无穷多个，另一方面越到后面其分布越来越稀,因为若记M=(n+1)!,则M+2+,M+3,M+(n+1)连续n+1个数都是合数。,C孪生素数问题,例如在100以内有七对孪生素数:(3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73).一方面素数越到后面其分布越来越稀，但是人们一直在找很大的相邻的两个奇数-孪生素数，已经找到了多达723位的孪生素数，是否有无穷多对孪生素数，这个问题至今还没有解决。,.,D不存在对任意整数恒取素数的多项式人们曾试图找一个能表示素数的多项式，但都失败了.例给出了，当x=0,1,2,39时都是素数,但当x=40时就是合数,当x=0,1,2,11000时都是素数,但当x=110001时就是合数.用反证法可证不存在对任意整数恒取素数的多项式（略）,.,素数的性质,定理：设p为素数，P|ab,则有p|a，或p|b证：若pa,则由素数的定义有(p,a)=1,则存在整数x,y使得ax+by=1,两边同乘b,有pxb+aby=b,因为p|aby,p|pb,所以有p|b.,推论1：若,则存在k,使证：若对任意k,都有p,则有则与已知矛盾，所以假设错误，即则存在k,有.,.,推论2：若,则存在k,使注：数学家因费尔马因都是素数，就说所有费尔马都是素数，但这是错误的，事实上有是合数。利用任意两个费尔马的互素性可证素数有无穷多个.因为对不同的m,n(Fn,Fm)=1。即不同的的费尔马数有不同的素因子,而费尔马数有无穷多个,所以素数有无穷多个.,.,6算术基本定理,算术基本定理：任何大于1的整数一定能分解成一些素数的乘积，且如果不计因数的次序，这种分解是唯一的即a1,则存在素数，使得,且若存在使得,则有m=n,适当调整次序后有,.,证：存在性：若a是素数，则已证。若a是合数，则至少有一个素因子，有若是素数，则已证。若是合数，则至少有一个素因子，设再对进行讨论，一直下去有,.,惟一性：设=(),则有s使得,不妨设,则有,重复上述讨论，调正次序有有,则有,但这是不可能的，所以m=n。即证明了惟一性。,.,标准分解式：任何大于1的整数a可惟一分解为且,推论1：设则a的正因子为,推论2：设则a的正倍数为,.,推论3：设a，b的分解式分别为则有,.,定义：设d（a）表示正整数a的所有正因子的个数，又设表示正整数a的所有正因子和，例如对于12=，12的正因数为1，2，3，4，6，12所以d（12）=6，,定理：设则有,.,完全数定义：满足的正整数a称为完全数完全数到目前为止只有38个.最小的完全数是6.依次为28,496,8128性质:1、个位是6或8，若是8，则十位是2。2、除6外，任何偶完全数除9余1。3、任何偶完全数可写成前n个自然数之和。6=1+2+328=1+2+3+4+5+6+7,.,496=1+2+3+318128=1+2+3+1274.任何偶完全数可写成连续2的方幂之和6=28=496=5.任何偶完全数倒数之和为2.,.,例1：设p为素数，求d(p),解：因为p为素数，所以其正因子只有1和p，即d（P）=2,例2:求d(1000)，解：1000=2353d(1000)=(3+1)(3+1)=16，=,.,例3：证明lg2是无理数。证：假设lg2是有理数，则存在二个正整数p,q使得lg2=，由对数定义可得，则有,则同一个数左边含因子5，右边不含因子5，与算术基本定理矛盾。lg2为无理数,.,例3:若为素数,则n为素数,证:设n为合数,则n=ab,a,b大于1小于n则有=为合数,与素数矛盾.所以n为素数.,.,例证明是无理数.,证:假设是有理数,则可设则有则上式左边有奇数个素因子,右边只有偶数个素因子,卢算术基本定理矛盾.所以假设错误,即是无理数.,.,例:设P是不小于5的素数,且2P+1也是素数,则4P+1是合数.,证:因为P是素数,则p=3k+1或3K+2当p=3k+1时,2P+1=3(2K+1)为合数,矛盾!所以P只能为3K+2,所以有4P+1=4(3K+2)+1=3(4K+1)为合数.,.,素数人们对素数这块整数中的“基石”进行大量研究，发现素数的分布是很不规则的，而且越往后赵稀疏例如，对于每个大于或等于2的整数n，连续n-1个整数n!2,n!3,n!n都不是素数.可见在正整数序列中,有任意长的区间中不含有素数.另一方面,任意两个相邻的正整数n和nl(n3)中必有一个不是素数.相邻两整数均为素数只有2和3.但是n和n2均为素数的则有很多,这样一对素数称为孪生素数.,.,素数,1742年,德国数学家哥德巴赫(C.Goldbach)提出了“每个大于2的偶数均可表成为两个素数之和”的著名猜想.我国数学家陈景润在已有研究成果的基础上,1966年证明并在1973年发表了“每一个充分大的偶数都可表为一个素数及一个不超过两个素数乘积之和”的重要论文,这是至今关于这一猜想的最好结果.有人验证了在3.3106以内的偶数对哥德巴赫猜想都是正确的.但该猜想至今未证明.,.,例3:证明当n2时,则n和n!之间至少有一个素数.,证:设p是n!-1的大于1的最小的正因数,则P为素数,且有Pn,否则有p|n!,则与p是n!-1的因数矛盾.所以假设不对.即有n和n!之间至少有一个素数.,.,例1:设教室里有100盏灯,编码为1-100,现有100个学生编码为0-100,8点进教室,每个学生分别把自己号码倍数的灯拉一下,问当所有学生都进来时教室时有几盏灯是亮的?,.,分析:灯拉了奇数次亮,偶数次不亮.所以只要考虑什么样的数的正因数的个数是奇数.解:设要使d(a)为奇数,则有每一个为奇数,所以每一个为偶数,即a为完全平方数,所以1,4,9,16,100有十盏灯是亮的.,.,完全平方数有一些