初等数论最小公倍数

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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),研究过形如,2,p,-1,的素数,其中,p,为素数,.,人们称它为默森尼素数,截止,2003,年,11,月,17,日,发现有,40,个,其中,2,20996011,-1,是目前最大素数,.,在网上,(http:/www.mersenne.org/),有个基金组织资助计算,M.Mersenne),素数的志愿者,.,猜想默森尼素数有无穷多,但至今都尚未证明,.,目前 是最大素数,有,12837064,位，超过,50,公里长，,第,1941,个梅森素数,序号 素数 位数 发现人 时间,41 224036583-1 7235733 John Findley 2004,40 220996011-1 6320430 Michael Shafer 2003,39 213466917-1 4053946 Michael Cameron 2001,38 26972593-1 2098960 Nayan,Woltman,Kurowski 1999,37 23021377-1 909526 Clarkson,Woltman,Kurowski 1998,36 22976221-1 895932 Spence,Woltman 1997,35 21398269-1 420921 Armengaud,Woltman 1996,34 21257787-1 378632 Slowinski&Gage 1996,33 2859433-1 258716 Slowinski&Gage 1994,32 2756839-1 227832 Slowinski&Gage 1992,31 2216091-1 65050 David Slowinski 1985,30 2132049-1 39751 David Slowinski 1983,29 2110503-1 33265 Welsh&Colquitt 1988,28 286243-1 25962 David Slowinski 1982,27 244497-1 13395 Slowinski&Nelson 1979,26 223209-1 6987 L.Curt Noll 1979,25 221701-1 6533 Nickel&Noll 1978,24 219937-1 6002 Bryant Tuckerman 1971,23 211213-1 3376 Donald B.Gillies 1963,22 29941-1 2993 Donald B.Gillies 1963,21 29689-1 2917 Donald B.Gillies 1963,20 24423-1 1332 Alexander Hurwitz 1961,19 24253-1 1281 Alexander Hurwitz 1961,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|a b,则有,p|a,，或,p|b,证：若,p,a,则由素数的定义有,(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+3,28=1+2+3+4+5+6+7,496=1+2+3+,+31,8128=1+2+3+,+127,4.,任何偶完全数可写成连续,2,的方幂之和,6=,28=,496=,5.,任何偶完全数倒数之和为,2.,例,1,：设,p,为素数，求,d(p),解：因为,p,为素数，所以其正因子只有,1,和,p,，即,d,（,P,）,=2,例,2,:,求,d,(1000),，,解：,1000=2,3,5,3,d,(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=