初等数论一整除演示文稿课件.ppt
2023/3/22 07:33,5 算术基本定理,整数分解唯一性定理也称算术基本定理,在给出并证明该定理前,先介绍预备定理.定理 若p为素数,则a不能被p整除当且仅当:(p,a)=1,2023/3/22 07:33,定理1,设a1,a2,an都是正整数,且p是素数.若p|a1a2an,则至少有一个ar,使得p|ar,其中1rn.证明 假设 ai不能被p整除,1in.从p是一素数和定理得到(p,a1)=(p,a2)=(p,an)=1.所以由定理5推论得到(p,a1a2an)=1,这与题设p|a1a2an矛盾,故必有一ar,使得p|ar,其中1rn.,2023/3/22 07:33,推论,设p1,p2,pn和p都是素数,n2.若p|p1p2pn,则至少有一个pr,使得p=pr.证明 由p|p1p2pn和定理1知,至少存在一个pr,使得p|pr.由于pr是素数,故它只有二个正因数1和pr.由p1和p|pr,所以:p=pr.,2023/3/22 07:33,定理2(整数分解唯一性定理),每个大于1的正整数a均可分解成有限个素数之积,并且若不计素因数的次序,其分解是唯一的.证明 先证分解式的存在性.唯一性.当a=2时,分解式显然是唯一的.现设比a小的正整数其分解式均是唯一的.考虑正整数 a,假设 a有两个分解式 a=plp2pk和a=q1q2ql,其中pl,p2,pk和q1,q2,ql都是素数.,2023/3/22 07:33,于是p1|q1q2ql,根据定理1知必有一qi,使得p1|qi，不妨令i=1,即p1|q1,显然p1=q1.令a=a/p1,则a=p2p3pk,aq2q2ql.若a=1,则a=p1=q1,即a的分解式唯一.若a1,注意到aa,从而由归纳假设知,a的分解式是唯一的.因此k=l,并且 p1=q1,pk=qk,再由p1=ql,知a分解式也是唯一的.,2023/3/22 07:33,若将a的分解式中相同素因数合并为它的幂数,则任意大于1的整数a只能分解成一种形式:(2)p1 p2 psn1,其中p1,p2,ps是互不相同的素数,是正整数.并称其是 a的标准分解式.,2023/3/22 07:33,推论3,使用式(2)中的记号，有()d 是a的正因数的充要条件是 d=(3)eiZ，0 ei i，1 i s；()n的正倍数m必有形式m=M，MN，iN，i i，1 i s。,2023/3/22 07:33,推论 设正整数a与b的标准分解式是,其中pi(1 i k)，qi(1 i l)与ri(1 i s)是两两不相同的素数,i,i(1 i k),i(1 i l)与i（1 i s）都是非负整数，则(a,b)=，i=mini,i,1 i k，a,b=，i=maxi,i，1 i k。,2023/3/22 07:33,推论4,设正整数a与b的分解式是其中p1,p2,ps 是互不相同的素数，i，i（1 i k）都是非负整数，则,2023/3/22 07:33,推论5,设a，b，c，k是正整数，ab=ck，(a,b)=1，则存在正整数u，v，使得a=uk，b=vk，c=uv，(u,v)=1。证明 设，其中p1,p2,ps 是互不相同的素数，i（1 i s）是正整数。又设 其中i，i（1 i s）都是非负整数。显然mini,i=0，i i=k i，1 i s，因此，对于每个i（1 i s），等式i=ki，i=0与i=0，i=ki有且只有一个成立。这就证明了推论。证毕。,2023/3/22 07:33,推论6,设a是正整数，表示a的所有正因数的个数.若a有标准素因数分解式(2)，则推论7 设a是正整数，表示a的所有正因数的之和.若a有标准素因数分解式(2)，则,2023/3/22 07:33,例1 证明：（a,b,c)=(a,b),(a,c),例2 求，例3 求,2023/3/22 07:33,7 函数x与x,n!的分解式,2023/3/22 07:33,定义1,设x是实数，以x表示不超过x的最大整数，称它为x的整数部分，即x是一个整数且满足 x x x+1.又称x=x x为x的小数部分。,2023/3/22 07:33,定理1 设x与y是实数，则,()x y x y；()若x=m+v,m是整数，0 v 1,则m=x,v=x，特别地，若0 x 1，则x=0，x=x；()若m是整数，则m x=m x；()x y=；()x=；,2023/3/22 07:33,x=.()对正整数m有()设a和N是正整数.那么，正整数中被a整除的正整数的个数是,2023/3/22 07:33,证明,能被a整除的正整数是a,2a,3a,，因此，若数1,2,N中能被a整除的整数有k个，则ka N(k 1)a k N/a k 1 k=证毕。由以上结论我们看到，若b是正整数，那么对于任意的整数a，有即在带余数除法 a=bq r，0 r b中有,2023/3/22 07:33,定理2,设n是正整数，n!=是n!的标准分解式，则 i=(1)证明 对于任意固定的素数p，以p(k)表示在k的标准分解式中的p的指数，则 p(n!)=p(1)p(2)p(n).以nj表示p(1),p(2),p(n)中指数等于j的个数，那么 p(n!)=1n1 2n2 3n3，(2)显然，nj就是在1,2,n中满足pja并且pj+1 a的整数a的个数，所以，由定理有,2023/3/22 07:33,nj=将上式代入式(2)，得到即式(1)成立。,2023/3/22 07:33,推论,设n是正整数，则n!=，其中 表示对不超过n的所有素数p求积。,2023/3/22 07:33,例2,求20！的标准素因数分解式例3 20！的十进位表示中有多少个零？例4 设整数aj0(1 j s),并且n=a1+a2+as.证明：n!/a1!a2!as!是整数.,2023/3/22 07:33,例5,设n是正整数，1 k n 1，则 N(3)若n是素数，则n，1 k n 1.证明 由定理2，对于任意的素数p，整数n!，k!与(n k)!的标准分解式中所含的p的指数分别是利用例4可知,2023/3/22 07:33,因此 是整数。若n是素数，则对于1 k n 1，有(n,k!)=1，(n,(n k)!)=1(n,k!(n k)!)=1，由此及 N，推出k!(n k)!(n 1)!，从而n.证毕.,
