初等数论第一章整除精选PPT.ppt
初等数论第一章整除初等数论第一章整除 2023/4/12 *第1页，此课件共23页哦 2023/4/12 *定理定理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.第2页，此课件共23页哦 2023/4/12 *推论推论设设p1,p2,pn和和p都是素数都是素数,n2.若若p|p1p2pn,则至少有一个则至少有一个pr,使得使得p=pr.证明证明 由由p|p1p2pn和定理和定理1知知,至少存在一个至少存在一个pr,使得使得p|pr.由于由于pr是素数是素数,故它只有二个正因数故它只有二个正因数1和和pr.由由p1和和p|pr,所以所以:p=pr.第3页，此课件共23页哦 2023/4/12 *定理定理2(整数分解唯一性定理整数分解唯一性定理)每个大于每个大于1的正整数的正整数a均可分解成有限个素数均可分解成有限个素数之积之积,并且若不计素因数的次序并且若不计素因数的次序,其分解是唯其分解是唯一的一的.证明证明 先证分解式的先证分解式的存在性存在性.唯一性唯一性.当当a=2时时,分解式显然是唯一的分解式显然是唯一的.现设现设比比a小的正整数其分解式均是唯一的小的正整数其分解式均是唯一的.考虑正考虑正整数整数 a,假设假设 a有两个分解式有两个分解式 a=plp2pk和和a=q1q2ql,其中其中pl,p2,pk和和q1,q2,ql都是素都是素数数.第4页，此课件共23页哦 2023/4/12 *于是于是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分解式也是分解式也是唯一的唯一的.第5页，此课件共23页哦 2023/4/12 *若将若将a的分解式中相同素因数合并为它的幂的分解式中相同素因数合并为它的幂数数,则任意大于则任意大于1的整数的整数a只能分解成一种形只能分解成一种形式式:(2)p1 p2 psn1,其中其中p1,p2,ps是互不相同的素数是互不相同的素数,是正整数是正整数.并称其是并称其是 a的标准分解式的标准分解式.第6页，此课件共23页哦 2023/4/12 *推论推论3使用式使用式(2)中的记号，有中的记号，有()d 是是a的正因数的充要条件是的正因数的充要条件是 d=(3)ei Z，0 ei i，1 i s；()n的正倍数的正倍数m必有形式必有形式m=M，M N，i N，i i，1 i s。第7页，此课件共23页哦 2023/4/12 *推论推论 设正整数设正整数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=min i,i,1 i k，a,b=，i=max i,i，1 i k。第8页，此课件共23页哦 2023/4/12 *推论推论4设正整数设正整数a与与b的分解式是的分解式是其中其中p1,p2,ps 是互不相同的素数，是互不相同的素数，i，i（1 i k）都是非负整数，则）都是非负整数，则第9页，此课件共23页哦 2023/4/12 *推论推论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）都是非负整数。显然）都是非负整数。显然min i,i=0，i i=k i，1 i s，因此，对于每个因此，对于每个i（1 i s），等式），等式 i=k i，i=0与与 i=0，i=k i有且只有一个成立。有且只有一个成立。这就证明了推论。证毕。这就证明了推论。证毕。第10页，此课件共23页哦 2023/4/12 *推论推论6设设a是正整数，是正整数，表示表示a的所有正因数的个数的所有正因数的个数.若若a有有标准素因数分解式标准素因数分解式(2)，则，则推论推论7 设设a是正整数，是正整数，表示表示a的所有正因数的之和的所有正因数的之和.若若a有标准素因数分解式有标准素因数分解式(2)，则，则第11页，此课件共23页哦 2023/4/12 *例例1 证明：（证明：（a,b,c)=(a,b),(a,c)例例2 求求 ，例例3 求求第12页，此课件共23页哦 2023/4/12 *7 函数函数x与与x,n!的分解式的分解式第13页，此课件共23页哦 2023/4/12 *定义定义1设设x是实数，以是实数，以x表示不超过表示不超过x的最大整数，的最大整数，称它为称它为x的整数部分，即的整数部分，即x是一个整数且满足是一个整数且满足 x x x+1.又称又称x=x x为为x的小数部分。的小数部分。第14页，此课件共23页哦 2023/4/12 *定理定理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=；第15页，此课件共23页哦 2023/4/12 *x=.()对正整数对正整数m有有()设设a和和N是正整数是正整数.那么，正整数那么，正整数中被中被a整除的正整数的个数是整除的正整数的个数是第16页，此课件共23页哦 2023/4/12 *证明证明能被能被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 0(1 j s),并且并且n=a1+a2+as.证明：证明：n!/a1!a2!as!是整数是整数.第21页，此课件共23页哦 2023/4/12 *例例5设设n是正整数，是正整数，1 k n 1，则，则 N (3)若若n是素数，则是素数，则n ，1 k n 1.证明证明 由定理由定理2，对于任意的素数，对于任意的素数p，整数，整数n!，k!与与(n k)!的标准分解式中所含的的标准分解式中所含的p的指数分别是的指数分别是利用例利用例4可知可知第22页，此课件共23页哦 2023/4/12 *因此因此 是整数。是整数。若若n是素数，则对于是素数，则对于1 k n 1，有，有(n,k!)=1，(n,(n k)!)=1 (n,k!(n k)!)=1，由此及由此及 N，推出推出k!(n k)!(n 1)!，从而，从而n .证毕证毕.第23页，此课件共23页哦
