5算术基本定理课件

11/21/2022

07:42§5算术基本定理整数分解唯一性定理也称算术基本定理,在给出并证明该定理前,先介绍预备定理.定理若p为素数,则a不能被p整除当且仅当:(p,a)=111/21/202202:521

11/21/2022

07:42定理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.11/21/202202:522

11/21/2022

07:42推论设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.11/21/202202:523

11/21/2022

07:42定理2

(整数分解唯一性定理)每个大于1的正整数a均可分解成有限个素数之积,并且若不计素因数的次序,其分解是唯一的.证明先证分解式的存在性.唯一性.当a=2时,分解式显然是唯一的.现设比a小的正整数其分解式均是唯一的.考虑正整数a,假设a有两个分解式a=plp2…pk和a=q1q2…ql,其中pl,p2,…,pk和q1,q2,…,ql都是素数.11/21/202202:524

11/21/2022

07:42于是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分解式也是唯一的.11/21/202202:525

11/21/2022

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

p2<…<

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

,,…,

是正整数.并称其是a的标准分解式.11/21/202202:536

11/21/2022

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

d是a的正因数的充要条件是d=(3)eiZ，0≤ei≤i，1≤i≤s；(ⅱ)a的正倍数m必有形式m=M，MN，iN，i

i，1≤i≤s。11/21/202202:537

11/21/2022

07:42推论设正整数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。11/21/202202:538

11/21/2022

07:42推论4设正整数a与b的分解式是其中p1,p2,,ps是互不相同的素数，i，i（1≤i≤k）都是非负整数，则11/21/202202:539

11/21/2022

07:42推论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有且只有一个成立。这就证明了推论。证毕。11/21/202202:5310

11/21/2022

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

设a是正整数，表示a的所有正因数的之和.若a有标准素因数分解式(2)，则11/21/202202:5311

11/21/2022

07:42例1证明：（a,[b,c])=[(a,b),(a,c)]例2求，例3求11/21/202202:5312

11/21/2022

07:42§7函数[x]与{x},n!的分解式11/21/202202:5313

11/21/2022

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

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

[x]为x的小数部分。

11/21/202202:5314

11/21/2022

07:42定理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]=；11/21/202202:5315

11/21/2022

07:42{x}=.(ⅵ)对正整数m有(ⅶ)设a和N是正整数.那么，正整数中被a整除的正整数的个数是11/21/202202:5316

11/21/2022

07:42证明能被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中有

11/21/202202:5317

11/21/2022

07:42定理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的个数，所以，由定理2有11/21/202202:5318

11/21/2022

07:42nj=将上式代入式(2)，得到即式(1)成立。11/21/202202:5319

11/21/2022

07:42推论设n是正整数，则n!=，其中表示对不超过n的所有素数p求积。11/21/202202:5320

11/21/2022

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

j≤s),并且n=a1+a2+…+as.证明：n!/a1!a2!…as!是整数.11/21/202202:5321

11/21/2022

07:42例5设n是正整数，1≤

k

≤

n1，则N(3)若n是素数，则n，1≤

k

≤

n1.证明由定理2，对于任意的素数p，整数n!，k!与(n

k)!的标准分解式中所含的p的指数分别是利用例4可知11/21/202202:5322

11/21/2022

07:42因此是整数。若n是素数，则对于1≤

k≤

n1，有(n,k!)=1，(n,(n

k)!)=1(n,k!(n

k)!)=1，由此及N，推出k!(n

k)!(n1)!，从而n.证毕.11/21/202202:5323

11/21/2022

07:42§5算术基本定理整数分解唯一性定理也称算术基本定理,在给出并证明该定理前,先介绍预备定理.定理若p为素数,则a不能被p整除当且仅当:(p,a)=111/21/202202:5224

11/21/2022

07:42定理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.11/21/202202:5225

11/21/2022

07:42推论设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.11/21/202202:5226

11/21/2022

07:42定理2

(整数分解唯一性定理)每个大于1的正整数a均可分解成有限个素数之积,并且若不计素因数的次序,其分解是唯一的.证明先证分解式的存在性.唯一性.当a=2时,分解式显然是唯一的.现设比a小的正整数其分解式均是唯一的.考虑正整数a,假设a有两个分解式a=plp2…pk和a=q1q2…ql,其中pl,p2,…,pk和q1,q2,…,ql都是素数.11/21/202202:5227

11/21/2022

07:42于是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分解式也是唯一的.11/21/202202:5228

11/21/2022

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

p2<…<

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

,,…,

是正整数.并称其是a的标准分解式.11/21/202202:5329

11/21/2022

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

d是a的正因数的充要条件是d=(3)eiZ，0≤ei≤i，1≤i≤s；(ⅱ)a的正倍数m必有形式m=M，MN，iN，i

i，1≤i≤s。11/21/202202:5330

11/21/2022

07:42推论设正整数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。11/21/202202:5331

11/21/2022

07:42推论4设正整数a与b的分解式是其中p1,p2,,ps是互不相同的素数，i，i（1≤i≤k）都是非负整数，则11/21/202202:5332

11/21/2022

07:42推论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有且只有一个成立。这就证明了推论。证毕。11/21/202202:5333

11/21/2022

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

设a是正整数，表示a的所有正因数的之和.若a有标准素因数分解式(2)，则11/21/202202:5334

11/21/2022

07:42例1证明：（a,[b,c])=[(a,b),(a,c)]例2求，例3求11/21/202202:5335

11/21/2022

07:42§7函数[x]与{x},n!的分解式11/21/202202:5336

11/21/2022

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

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

[x]为x的小数部分。

11/21/202202:5337

11/21/2022

07:42定理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]=；11/21/202202:5338

11/21/2022

07:42{x}=.(ⅵ)对正整数m有(ⅶ)设a和N是正整数.那么，正整数中被a整除的正整数的个数是11/21/202202:5339

11/21/2022

07:42证明能被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中有

11/21/202202:5340

11/21/2022

07:42定理2设n是正整数，n!=是n!的标准分解式，则i=(1)证明对于任意固定的素数p，以p(k)表示在k的标准分解式中的p的指数，则p(n!)=p(1