初等數(shù)論第一章整除

2023/4/27

*第1頁，共23頁，2023年，2月20日，星期日

2023/4/27

*定理1設(shè)a1,a2,…,an都是正整數(shù),且p是素?cái)?shù).若p|a1a2…an,則至少有一個(gè)ar,使得p|ar,其中1≤r≤n.證明假設(shè)ai不能被p整除,1≤i≤n.從p是一素?cái)?shù)和定理得到(p,a1)=(p,a2)=…＝(p,an)=1.所以由定理5推論得到(p,a1a2…an)=1,這與題設(shè)p|a1a2…an矛盾,故必有一ar,使得p|ar,其中1≤r≤n.第2頁，共23頁，2023年，2月20日，星期日

2023/4/27

*推論設(shè)p1,p2,…,pn和p都是素?cái)?shù),n≥2.若p|p1p2…pn,則至少有一個(gè)pr,使得p=pr.證明由p|p1p2…pn和定理1知,至少存在一個(gè)pr,使得p|pr.由于pr是素?cái)?shù),故它只有二個(gè)正因數(shù)1和pr.由p≠1和p|pr,所以:p=pr.第3頁，共23頁，2023年，2月20日，星期日

2023/4/27

*定理2

(整數(shù)分解唯一性定理)每個(gè)大于1的正整數(shù)a均可分解成有限個(gè)素?cái)?shù)之積,并且若不計(jì)素因數(shù)的次序,其分解是唯一的.證明先證分解式的存在性.唯一性.當(dāng)a=2時(shí),分解式顯然是唯一的.現(xiàn)設(shè)比a小的正整數(shù)其分解式均是唯一的.考慮正整數(shù)a,假設(shè)a有兩個(gè)分解式a=plp2…pk和a=q1q2…ql,其中pl,p2,…,pk和q1,q2,…,ql都是素?cái)?shù).第4頁，共23頁，2023年，2月20日，星期日

2023/4/27

*于是p1|q1q2…ql,根據(jù)定理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,從而由歸納假設(shè)知,a’的分解式是唯一的.因此k=l,并且p1=q1,…,pk=qk,再由p1=ql,知a分解式也是唯一的.第5頁，共23頁，2023年，2月20日，星期日

2023/4/27

*若將a的分解式中相同素因數(shù)合并為它的冪數(shù),則任意大于1的整數(shù)a只能分解成一種形式:(2)p1<p2<…<

psn≥1,其中p1,p2,…,ps是互不相同的素?cái)?shù),

,,…,

是正整數(shù).并稱其是a的標(biāo)準(zhǔn)分解式.第6頁，共23頁，2023年，2月20日，星期日

2023/4/27

*推論3使用式(2)中的記號(hào)，有(ⅰ)

d

是a的正因數(shù)的充要條件是

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

n的正倍數(shù)m必有形式m=M，MN，iN，i

i，1≤i≤s。第7頁，共23頁，2023年，2月20日，星期日

2023/4/27

*推論設(shè)正整數(shù)a與b的標(biāo)準(zhǔn)分解式是

其中pi(1≤i≤k)，qi(1≤i≤l)與ri(1≤i≤s)是兩兩不相同的素?cái)?shù),i,i(1≤i≤k),i(1≤i≤l)與i（1≤i≤s）都是非負(fù)整數(shù)，則(a,b)=，i=min{i,i},1≤i≤k，[a,b]=，i

=max{i,i}，1≤i≤k。第8頁，共23頁，2023年，2月20日，星期日

2023/4/27

*推論4設(shè)正整數(shù)a與b的分解式是其中p1,p2,,ps

是互不相同的素?cái)?shù)，i，i（1≤i≤k）都是非負(fù)整數(shù)，則第9頁，共23頁，2023年，2月20日，星期日

2023/4/27

*推論5設(shè)a，b，c，k是正整數(shù)，ab=ck

，(a,b)=1，則存在正整數(shù)u，v，使得a=uk，b=vk，c=uv，(u,v)=1。證明設(shè)，其中p1,p2,,ps

是互不相同的素?cái)?shù)，i（1≤

i≤

s）是正整數(shù)。又設(shè)

其中i，i（1≤

i≤s）都是非負(fù)整數(shù)。顯然min{i,i}=0，i

i=ki，1≤

i≤s，因此，對于每個(gè)i（1≤

i≤s），等式i=ki

，i=0與i=0，i=ki有且只有一個(gè)成立。這就證明了推論。證畢。第10頁，共23頁，2023年，2月20日，星期日

2023/4/27

*推論6設(shè)a是正整數(shù)，表示a的所有正因數(shù)的個(gè)數(shù).若a有標(biāo)準(zhǔn)素因數(shù)分解式(2)，則推論7

設(shè)a是正整數(shù)，表示a的所有正因數(shù)的之和.若a有標(biāo)準(zhǔn)素因數(shù)分解式(2)，則第11頁，共23頁，2023年，2月20日，星期日

2023/4/27

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

求，例3

求第12頁，共23頁，2023年，2月20日，星期日

2023/4/27

*§7函數(shù)[x]與{x},n!的分解式第13頁，共23頁，2023年，2月20日，星期日

2023/4/27

*定義1設(shè)x是實(shí)數(shù)，以[x]表示不超過x的最大整數(shù)，稱它為x的整數(shù)部分，即[x]是一個(gè)整數(shù)且滿足

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

[x]為x的小數(shù)部分。

第14頁，共23頁，2023年，2月20日，星期日

2023/4/27

*定理1設(shè)x與y是實(shí)數(shù)，則(ⅰ)x≤y

[x]≤[y]；(ⅱ)若x=m+v,m是整數(shù)，0≤v<1,則m=[x],v={x}，特別地，若0≤x<1，則[x]=0，x={x}；(ⅲ)若m是整數(shù)，則[m

x]=m

[x]；(ⅳ)[x

y]=；(ⅴ)[x]=；第15頁，共23頁，2023年，2月20日，星期日

2023/4/27

*{x}=.(ⅵ)對正整數(shù)m有(ⅶ)設(shè)a和N是正整數(shù).那么，正整數(shù)中被a整除的正整數(shù)的個(gè)數(shù)是第16頁，共23頁，2023年，2月20日，星期日

2023/4/27

*證明能被a整除的正整數(shù)是a,2a,3a,，因此，若數(shù)1,2,,N中能被a整除的整數(shù)有k個(gè)，則ka≤N<(k

1)a

k≤N/a<k

1

k=證畢。由以上結(jié)論我們看到，若b是正整數(shù)，那么對于任意的整數(shù)a，有即在帶余數(shù)除法

a=bq

r，0≤r<b中有

第17頁，共23頁，2023年，2月20日，星期日

2023/4/27

*定理2設(shè)n是正整數(shù)，n!=是n!的標(biāo)準(zhǔn)分解式，則i=(1)證明對于任意固定的素?cái)?shù)p，以p(k)表示在k的標(biāo)準(zhǔn)分解式中的p的指數(shù)，則

p(n!)=p(1)

p(2)

p(n).以nj表示p(1),p(2),,p(n)中指數(shù)等于j的個(gè)數(shù)，那么

p(n!)=1n1

2n2

3n3

，(2)顯然，nj就是在1,2,,n中滿足pja并且pj

+1a的整數(shù)a的個(gè)數(shù)，所以，由定理有第18頁，共23頁，2023年，2月20日，星期日

2023/4/27

*nj=將上式代入式(2)，得到即式(1)成立。第19頁，共23頁，2023年，2月20日，星期日

2023/4/27

*推論設(shè)n是正整數(shù)，則n!=，其中表示對不超過n的所有素?cái)?shù)p求積。第20頁，共23頁，2023年，2月20日，星期日

2023/4/27

*例2求20！的標(biāo)準(zhǔn)素因數(shù)分解式例320！的十進(jìn)位表示中有多少個(gè)零？例4設(shè)整數(shù)aj>0(1≤

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