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

§5算術(shù)基本定理整數(shù)分解唯一性定理也稱算術(shù)基本定理,在給出并證明該定理前,先介紹預(yù)備定理.定理若p為素?cái)?shù),則a不能被p整除當(dāng)且僅當(dāng):(p,a)=1

5/21/2023

02:57定理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.

5/21/2023

02:57推論設(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.

5/21/2023

02:57定理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ù).

5/21/2023

02:57于是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/21/2023

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

p2<…<

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

,,…,

是正整數(shù).并稱其是a的標(biāo)準(zhǔn)分解式.

5/21/2023

02:57推論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。

5/21/2023

02:57推論設(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。

5/21/2023

02:57推論4設(shè)正整數(shù)a與b的分解式是其中p1,p2,,ps是互不相同的素?cái)?shù)，i，i（1≤i≤k）都是非負(fù)整數(shù)，則

5/21/2023

02:57推論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，因此，對(duì)于每個(gè)i（1≤

i≤s），等式i=ki

，i=0與i=0，i=ki有且只有一個(gè)成立。這就證明了推論。證畢。

5/21/2023

02:57推論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)，則

5/21/2023

02:57例1證明：（a,[b,c])=[(a,b),(a,c)]例2求，例3求

5/21/2023

02:57§7函數(shù)[x]與{x},n!的分解式

5/21/2023

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

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

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

5/21/2023

02:57定理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]=；

5/21/2023

02:57{x}然=膚.(ⅵ豪)對(duì)正活整數(shù)m有(ⅶ)設(shè)a和N是正尚整數(shù).那么戴，正款整數(shù)中被a整除闊的正遇整數(shù)灶的個(gè)帶數(shù)是5/繪18恰/2挺02勞300俘:4融1證明能被a整除仿的正膜整數(shù)野是a,治2a,奸3a,，因丑此，燙若數(shù)1,竭2莊,,N中能恨被a整除雷的整匪數(shù)有k個(gè)，垮則ka≤N<自(k1)ak≤N/a<k1k=證畢聚。由以符上結(jié)虎論我非們看滔到，評(píng)若b是正釀?wù)麛?shù)玩，那穿么對(duì)坐于任初意的整樣數(shù)a，有即在糕帶余著數(shù)除曬法a=bqr，0廟≤r<b中有5/栗18該/2岡02抓300際:4矮1定理2設(shè)n是正混整數(shù)受，n!額=是n!的標(biāo)錢準(zhǔn)分扎解式，叔則i=染(晴1)證明對(duì)于碎任意因固定拍的素救數(shù)p，以p(k)表示寨在k的標(biāo)族準(zhǔn)分解式抽中的p的指及數(shù)，設(shè)則p(n!)煙=p(1般)p(2片)p(n).以nj表示p(1牛),p(2萌),,p(n)中指牽數(shù)等歇于j的個(gè)妖數(shù)，桶那么p(n!)瞇=泥1n12n23n3，(2掏)顯然夕，nj就是箏在1,揭2摔,,n中滿知足pja并且pj+六1a的整數(shù)a的個(gè)虹數(shù)，洋所以迅，由誤定理射有5/弓18粱/2剖02隔300催:4驗(yàn)1nj=將上怖式代巧入式(2豪)，得潮到即將式(1榆)成立浴。5/棵18劇/2恥02貍300園:4鞏1推論設(shè)n是正小整數(shù)微，則n!密=，其中深表示遵對(duì)不斃超過(guò)n的所樣有素姑數(shù)p求積雀。5/犯18循/2步02本300庭:4達(dá)1例2求20！的標(biāo)策準(zhǔn)素望因數(shù)謙分解厭式例320！的斬十進(jìn)度位表葬示中等有多抽少個(gè)敗零？例4設(shè)整慕數(shù)aj>0悄(1≤j≤s),并且n=a1+a2+…堵+as.證明伙：n!/a1!a2!阻…as!是整身數(shù).5/國(guó)18酷/2震02蹦300稼:4哨1例5設(shè)n是正述整數(shù)疾，1≤k≤n1，則N舌(默3)若n是素體數(shù)，議則n，1≤k≤n1.證明由定頸理2，對(duì)縮慧于任摧意的墾素?cái)?shù)p，整集數(shù)n!，k!與(nk)!的標(biāo)興準(zhǔn)分侵解式姓中所彼含的p的指