文档介绍：该【算术基本定理 】是由【泰山小桥流水】上传分享，文档一共【12】页，该文档可以免费在线阅读，需要了解更多关于【算术基本定理 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。大于1的整数n总有两个不同的正约数:(称n没有正因子),则称n为质数(或素数).若n有真因子,即n可以表示为ab的形式(这里a,b为大于1的整数),:数 1,素数类,,n为任意一个整数,则或者 p整除n,,p与n的最大公约数(p,n)必整除p,故由素数的定义推知,或者(p,n) 1,或者(p,n) p,即或者p与n互素,或者p|,a,|ab,则a,,若p不整除a和b,由性质2知,p与a和b均互素,从而p与ab互素。这与已知的 p|:若素数 p整除an(n 1),则p|a定理1素数有无限多个(公元前欧几里得给出证明)证明:(反证法)假设只有k个素数,设它们是 p1,p2,L,pk。记N p1p2Lpw1。(N不一定是素数)由第一节定理2可知,p有素因数p,我们要说明ppi,1ik从而得出矛盾事实上,若有某个 i,1 i k使得p pi,则由p|Np1p2Lpw1推出p|1,这是不可能的。因此在p1,p2,L,pk之外又有一个素数p,这与假设是矛盾的。所以素数不可能是有限个。引理1任何大于1的正整数n可以写成素数之积,即n p1p2L pm (1)其中pi,1 i m是素数。证明 当n=2时,结论显然成立。假设对于2 n k,式(1)成立,我们来证明式(1)对于n=k 1也成立,从而由归纳法推出式(1)对任何大于1的整数n成立。如果k 1是素数,式(1)显然成立。如果k1是合数,则存在素数p与整数d,使得k1=pd。由于2dk,由归纳假定知存在素数q1,q2,Lql,使得dq1,q2,Lql,从而k1pq1,q2,Lql。证毕。定理2(算术基本定理)任何大于1的整数n可以唯一地表示成np11p22Lpkk,(2)其中p1,p2,L,pk是素数,p1p2Lpk,a1,a2,L,ak是正整数。我们称np11p22Lpkka1,a2,L,ak是n的标准分解式,其中pi,1ik是素数,p1p2Lpk,:由引理1,任何大于1的整数n可以表示成式(2)的形式,因此,证明表示式(2)的唯一性。假设pi,1 i k与qj,1 j l都是素数,p1 p2 L pk,q1 q2 L ql, (3)并且n p1p2Lpk q1q2Lql, (4)则由第三节定理 4推论1,必有某个qj,1 j l,使得p1|qi,所以p1=qi;又有某个pi,1 i k,使得q1|pi,所以q1=pi。于是,由式(3)可知p1=q1,从而由式(4)得到p2L pk=q2Lql重复上述这一过程,得到kl,piqi,1ik证毕。:若设(n)为n的正约数的个数,(n)为n的正约数之和,则有(1)(n)(11)(21)gg(k1)(2)(n)p1111p2211ggpkk11p11p21pk1推论1使用式(2)中的记号,有(ⅰ)n的正因(约)数d必有形式d=d11p22Lpkk,1Z,0ii,1ikp(ⅱ)n的正倍数m必有形式mp11p22LpkkM,MN,iN,ii,1ik推论2设正整数a与b的标准分解式是ap11p22pkk,bp11p21pkk,其中p1,p2,,pk是互不相同的素数,i,i(1ik)都是非负整数,则(a,b)p11p21pkk,i[a,b]p11p21pkk,imin{ i, i},1 i k,max{ i, i},1 i k。推论3设a,b,c,n是正整数,ab=cn,ab,(5)(,)=1则存在正整数u,v,使得a=un,b=vn,c=uv,(u,v)=1。证明设c=p1p1k,其中p1p2,pk是互不相同的素数,i(112pk,,k)是正整数。又设ap11p22pkk,bp11p21pkk,其中I,i(1ik)都是非负整数。由式(5)及推论2可知min{i,i}=0,ii=ni,1ik,因此,对于每个i(1ik),等式i =n i , i =0与 i =0, i =n i有且只有一个成立。这就证明了推论。证毕。:对任意的正整数m及素数p,记号p||m表示p|m,p1|m,,p为素数,pp||n!,,则n0,:设p为任一素数,在n!中含p的最高乘方次数记为pn!,则有:pn!nnLnpmnpm1pp2pm证明:由于p是素数,所有n!中所含p的方次数等于n!的各个因数1,2,L,n所含p的方次数之总和。由性质10可知,在1,2,L,n中,有n个p的倍数,p有n个p2的倍数,有n个p3的倍数,L,当pmnpm1时,p2p3nnL0,所以命题成立。pm1pm2另证:对于任意固定的素数p,以pk表示在k的标准分解式中的p的指数,则pn!=p(1) p(2) L p(n).nj表示p(1),p(2),L,p(n)中等于j的个数,那么pn!=1n12n23n3L,(2)显然,nj就是在1,2,L,n中满足pja并且pj+1|a的整数a的个数,所以由定理2有nj[nj][nj1]。pp将上式代入式(2),得到p(n!)1([n][n2])2([n2][n3])3([n3][n4])Lpppppp[nr]。r 1 p即式(1)成立。证毕。二、重要方法证明某些特殊形式的数不是素数(或给出其为素数的必要条件)是初等数论中较为基本的问题,其方法是应用各种分解技术(如代数式的分解),指出所给数的一个真因子常用分解技术有:(1)利用代数式分解(如因式分解)指出其一个真因子;(2)应用数的分解(例如算术基本定理),指出数的一个真因子;(3)运用反证法,假定其是素数,、:无穷数列10001,100010001,中没有素数.(教材第13页例1)证明:记an10001L10001,(n2),则1442443n个1an1104108104(n1)104n11041对n分奇偶讨论:(1)当n为偶数时,设n108k1108k110812k,则an1**********显然1081是大于1的整数,当k2时,108k1(108)k1是大于1的整数104110811081而当k1时,a21000113137是合数.(2) 当为奇数时,设n 2k 1,nan108k41104k21104k21(102)2k11(102)2k1110411021102110211021易知(102)2k11,(102)2k11都是大于1的整数10211021综上:命题获证;:对任意整数 n 1,数n4 4n不是素数.(教材第13页例2)证明:我们对n分奇偶讨论:(1)当为偶数时,44n大于,且也为偶数,(2)当为奇数时,设n2k1,则n44nn442k1n44(2k)4(n2222k)24n2(2k)2(n2222k)2(2n2k)2(n2222k2n2k)(n2222k2n2k)由于n1,所以n2222k2n2k,n2222k2n2k都是大于1的整数,:,b,c,d满足abcd,证明:abcd不是素数证明一:本题不宜采用代数式的分解来产生所需的分解 .我们的第一种解是应用数的分解,,可设adm,其中m,,cnu,同理dmv,cnv故abcdmunumvnv(mn)(uv)是两个大于1的整数积,:由abcd,得bcd,因此abcdacdcd(ac)(ad),,设为p,则由(ac)(ad)ap(*),p|(ac)(ad)故p|(ac)或p|(ad),不妨设,p|(ac)则acp,结合(*)式得:ada,即d0,这不可能,故结论成立;,b,c,d满足abcd0,且a2acc2b2bdd2证明:abcd不是素数.(教材第18页****题3-4)证明:本题运用反证法,设有满足题设的一组a,b,c,d,使得abcd为素数,将其记为pabcd,于是apcd带入已知条件得到:bp(p2cdbc)(b2c2)(b2bdd2)由于p是素数,故p|(b2c2)或者p|(b2bdd2)(ⅰ)若p|(b2c2),则由b2c2abab2ab2(abcd)2p,推出b2c2p,即b2c2abcd,从而b|c(cd),显然(b,c)1(因为b2c2是素数)故b|(cd),这与0cdcb矛盾.(ⅱ)若p|(b2bdd2),则由0b2bdd22(abcd)2p知b2bdd2p,故a2acc2b2bdd2abcd,进而得到a2acc(cd)ab,b2bdd(dc)ab,于是得到a|c(cd),b|d(cd)都成立,但又知(ab,cd)1,,0cd2b从而必须有cda,cdb,:若整数a,b满足2a2a3b2b,:已知关系式变形为(ab)(2a2b1)b2(1)(ab,2a2b1) 1,则d有素因子p,从而由(1)知p|b2,因p是素数,故p||(a b)知p||(2a2b1)导出p|1,这不可能,故d1,,由(1)得右端为(1)b2是一个完全平方数,故|ab|,|2a2b1|,,b满足问题中的等式,|ab|是一个完全平方数故有bar2,这里r0;结合(1)推出r|b,再由bar2得出r|,aa1r,带入问题中的等式可得(注意r0,b1a1r)a126a1r3r210(2)将上式视为关于a1的二次方程,由求根公式解得a13r6r21,因a1是整数,;而6r21被3除得余数为,(或者更直接地:由2被3除得余数为0,故()左边被3除得的余数a1或12是1或2;但(2)的右边为0,(2)对任何整数a1及r均不成立)从而必须有ab0,:(例如,证明整数的最大公约数是1),由此我们常假设所说的数有一个素因子,利用素数的锐利性质(3)作进一步论证,,并求它的正约数的个数(n);解:我们有5148022574022128702364352351287235342923532143233251113(n)(11)(21)gg(k1)(31)(21)(11)(11)(11),使得10k|199!解:因为10 25,正整数k的最大值取决于199!的分解式中所含 ,199!的标准分解式中所含的 5的幂指数是[199][1992][1993]L47555所以,所求的最大整数是k47。,则[2x][2y]3[x][xy][y](*)证法一:设x[x],01,y[y],01,则右边[x][xy][y]2[x]2?[y],(1)左边[2x][2y]2[x]2?[y]22,(2)如果0,那么显然有22;如果1,那么与中至少有一个不小于1,于是2221。因此无论0或1,都有22,由此及式(1)和式(2)可以推出式(*):注意到对任意整数k及任意实数,kk,即上述不等式x或y改变一个整数量,则不等式(*)(*)只需证明0x1,:[2x] [2y] [x y],n是非负整数,证明:(2m)!(2n)!!n!(mn)!证明:我们只需证明:对每一个素数p,分母m!n!(mn)!的标准分解中p的幂次,不超过分子 (2m)!(2n)!中p的幂次,由定理知等价于证明2m2nmnmn①l1plpll1plplpl事实上我们能够证明一个更强的命题:设x与y是实数,则[2x] [2y]3 [x] [x y] [y] ②①②,b,c是整数,证明:(ⅰ)(a,b)[a,b]ab;(ⅱ)(a[b,c])[(a,b),(a,c)]。解 为了叙述方便,不妨假定 a,b,c是正整数。(ⅰ) 设a p11p22L pkk,b p11p21L pkkb,其中p1,p2,L,pk是互不相同的素数, i,i(1 i k)都是非负整数。由定理 1推论2 ,有(a,b)p11p21Lpkk,imin{i,i},1ik,[a,b]p11p21Lpkk,imax{i,i},1ik。由此知kkpimin{i,i}max{i,i}k(a,b)[a,b]=piiipiiiab;i1i1i1(ⅱ)设kkkapii,bpii,cpii,i1i1i1