初等数论第一章整除

初等数论第一章整除

2023/7/31

*第1页，课件共23页，创作于2023年2月

2023/7/31

*定理1设a1,a2,…,an都是正整数,且p是素数.若p|a1a2…an,则至少有一个ar,使得p|ar,其中1≤r≤n.证明假设ai不能被p整除,1≤i≤n.从p是一素数和定理得到(p,a1)=(p,a2)=…＝(p,an)=1.所以由定理5推论得到(p,a1a2…an)=1,这与题设p|a1a2…an矛盾,故必有一ar,使得p|ar,其中1≤r≤n.第2页，课件共23页，创作于2023年2月

2023/7/31

*推论设p1,p2,…,pn和p都是素数,n≥2.若p|p1p2…pn,则至少有一个pr,使得p=pr.证明由p|p1p2…pn和定理1知,至少存在一个pr,使得p|pr.由于pr是素数,故它只有二个正因数1和pr.由p≠1和p|pr,所以:p=pr.第3页，课件共23页，创作于2023年2月

2023/7/31

*定理2

(整数分解唯一性定理)每个大于1的正整数a均可分解成有限个素数之积,并且若不计素因数的次序,其分解是唯一的.证明先证分解式的存在性.唯一性.当a=2时,分解式显然是唯一的.现设比a小的正整数其分解式均是唯一的.考虑正整数a,假设a有两个分解式a=plp2…pk和a=q1q2…ql,其中pl,p2,…,pk和q1,q2,…,ql都是素数.第4页，课件共23页，创作于2023年2月

2023/7/31

*于是p1|q1q2…ql,根据定理1知必有一qi,,使得p1|qi，不妨令i=1,即p1|q1,显然p1=q1.令a’=a/p1,则a’=p2p3…pk,a’＝q2q2…ql.若a’=1,则a=p1=q1,即a’的分解式唯一.若a’＞1,注意到a’<a,从而由归纳假设知,a’的分解式是唯一的.因此k=l,并且p1=q1,…,pk=qk,再由p1=ql,知a分解式也是唯一的.第5页，课件共23页，创作于2023年2月

2023/7/31

*若将a的分解式中相同素因数合并为它的幂数,则任意大于1的整数a只能分解成一种形式:(2)p1<

p2<…<

psn≥1,其中p1,p2,…,ps是互不相同的素数,

,,…,

是正整数.并称其是a的标准分解式.第6页，课件共23页，创作于2023年2月

2023/7/31

*推论3使用式(2)中的记号，有(ⅰ)

d

是a的正因数的充要条件是

d=(3)eiZ，0≤ei≤i，1≤i≤s；(ⅱ)

n的正倍数m必有形式m=M，MN，iN，i

i，1≤i≤s。第7页，课件共23页，创作于2023年2月

2023/7/31

*推论设正整数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年2月

2023/7/31

*推论4设正整数a与b的分解式是其中p1,p2,,ps

是互不相同的素数，i，i（1≤i≤k）都是非负整数，则第9页，课件共23页，创作于2023年2月

2023/7/31

*推论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=ki，1≤

i≤s，因此，对于每个i（1≤

i≤s），等式i=ki

，i=0与i=0，i=ki有且只有一个成立。这就证明了推论。证毕。第10页，课件共23页，创作于2023年2月

2023/7/31

*推论6设a是正整数，表示a的所有正因数的个数.若a有标准素因数分解式(2)，则推论7

设a是正整数，表示a的所有正因数的之和.若a有标准素因数分解式(2)，则第11页，课件共23页，创作于2023年2月

2023/7/31

*例1证明：（a,[b,c])=[(a,b),(a,c)]例2

求，例3

求第12页，课件共23页，创作于2023年2月

2023/7/31

*§7函数[x]与{x},n!的分解式第13页，课件共23页，创作于2023年2月

2023/7/31

*定义1设x是实数，以[x]表示不超过x的最大整数，称它为x的整数部分，即[x]是一个整数且满足

[x]≤x<[x]+1.又称{x}=x

[x]为x的小数部分。

第14页，课件共23页，创作于2023年2月

2023/7/31

*定理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年2月

2023/7/31

*{x}=.(ⅵ)对正整数m有(ⅶ)设a和N是正整数.那么，正整数中被a整除的正整数的个数是第16页，课件共23页，创作于2023年2月

2023/7/31

*证明能被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中有

第17页，课件共23页，创作于2023年2月

2023/7/31

*定理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

+1a的整数a的个数，所以，由定理有第18页，课件共23页，创作于2023年2月

2023/7/31

*nj=将上式代入式(2)，得到即式(1)成立。第19页，课件共23页，创作于2023年2月

2023/7/31

*推论设n是正整数，则n!=，其中表示对不超过n的所有素数p求积。第20页，课件共23页，创作于2023年2月

2023/7/31

*例2求20！的标准素因数分解式例320！的十进位表示中有多少个零？例4设整数aj>0(1≤

j≤s),并且n=a1+a2+…