初等數(shù)論精講與習(xí)題講解.doc

初等數(shù)論精講與習(xí)題講解算術(shù)基本定理。大約公元前350年，歐幾里得在他偉大的十三卷著作原本中，用了許多篇幅來討論素?cái)?shù)。特別是他證明了每一個(gè)比1大的數(shù)（即每個(gè)比1大的正整數(shù)）要么本身是一個(gè)素?cái)?shù)，要么可以寫成一系列素?cái)?shù)的乘積，如果不考慮這些素?cái)?shù)的在乘積中的順序，那么寫出來的形式是唯一的。例如：14=2*7，21=3*7，等等。等號右邊的表達(dá)式分別是數(shù)14與21的“素?cái)?shù)分解”。這樣我們能把歐幾里得的結(jié)果表達(dá)為：每一個(gè)大于1的計(jì)數(shù)數(shù)要么是素?cái)?shù)，要么具有唯一的（次序變化不計(jì)）素?cái)?shù)分解。這個(gè)事實(shí)被稱為算術(shù)基本定理，它告訴我們素?cái)?shù)好比化學(xué)家的原子所有整數(shù)得以構(gòu)成的基本砌塊。例1將8128的小于自身的全體正約數(shù)從小到大排成，求證：分析：（1）8128的正約數(shù)（數(shù)論知識），則其約數(shù)共有（6+1）（1+1）=14個(gè)。（柯西）數(shù)列的前n項(xiàng)和（估算）。裂項(xiàng)求和。解答：（1）8128的正約數(shù)（數(shù)論知識），則其約數(shù)共有（6+1）（1+1）=14個(gè)。8128的所有約數(shù)之和：。小于自身的正約數(shù)共（14-1=）13個(gè)，小于自身全體約數(shù)和：8128。即：。（2）（柯西）數(shù)列的前n項(xiàng)和（估算）。裂項(xiàng)求和。例2給定正整數(shù)，設(shè)兩個(gè)不相等的正整數(shù)，使得求的最小值解：設(shè)，可使，若為奇數(shù)，若為偶數(shù)，時(shí)，8，時(shí)，例3求證：存在無窮多個(gè)正整數(shù)，使得都可以表示為兩個(gè)正整數(shù)的平方和證明：，有：則，即：若，則不能寫成平方程（整數(shù)）形式若，則，可找到，若，e，若，則，那么，例4有多少個(gè)十位數(shù)是66667的倍數(shù)，并且它們的個(gè)數(shù)僅為3，4，5和6，。解：前五位數(shù)記作A，后五位數(shù)記作B,設(shè)N滿足條件,但 、 恰有一個(gè)解 、 所以 設(shè) 解 解 所以，共有種方法費(fèi)馬小定理是數(shù)論中的一個(gè)重要定理,其內(nèi)容為:假如p是質(zhì)數(shù)，且(a,p)=1，那么 a(p-1) （mod p）一、準(zhǔn)備知識：引理1剩余系定理2若a,b,c為任意3個(gè)整數(shù)，m為正整數(shù)，且(m,c)=1,則當(dāng)acbc(modm)時(shí)，有ab(modm)證明：acbc(mod m)可得acbc0(mod m)可得(a-b)c0(mod m)因?yàn)?m,c)=1即m,c互質(zhì)，c可以約去，ab0(mod m)可得ab(mod m)引理2剩余系定理5若m為整數(shù)且m1,a1,a2,a3,a4,am為m個(gè)整數(shù)，若在這m個(gè)數(shù)中任取2個(gè)整數(shù)對m不同余，則這m個(gè)整數(shù)對m構(gòu)成完全剩余系。證明：構(gòu)造m的完全剩余系（0,1,2,m-1），所有的整數(shù)必然這些整數(shù)中的1個(gè)對模m同余。取r1=0,r2=1,r3=2,r4=3,r=i-1,1i1，b是一個(gè)整數(shù)且(m,b)=1。如果a1,a2,a3,a4,am是模m的一個(gè)完全剩余系，則ba1,ba2,ba3,ba4,bam也構(gòu)成模m的一個(gè)完全剩余系。證明：若存在2個(gè)整數(shù)ba和baj同余即babaj(mod m)，根據(jù)引理2則有aaj(mod m)。根據(jù)完全剩余系的定義和引理4（完全剩余系中任意2個(gè)數(shù)之間不同余，易證明）可知這是不可能的，因此不存在2個(gè)整數(shù)ba和baj同余。由引理5可知ba1,ba2,ba3,ba4,bam構(gòu)成模m的一個(gè)完全剩余系。引理4同余定理6如果a,b,c,d是四個(gè)整數(shù)，且ab(mod m),cd(mod m),則有acbd(mod m)證明：由題設(shè)得acbc(mod m),bcbd(mod m)，由模運(yùn)算的傳遞性可得acbc(mod m)二、證明過程：構(gòu)造素?cái)?shù)p的完全剩余系P=1,2,3,4(p-1)，因?yàn)?a,p)=1，由引理3可得A=a,2a,3a,4a,(p-1)a也是p的一個(gè)完全剩余系。令W=1*2*3*4*(p-1)，顯然WW(mod p)。令Y=a*2a*3a*4a*(p-1)a,因?yàn)閍,2a,3a,4a,(p-1)a是p的完全剩余系，由引理2以及引理4可得a*2a*3a*(p-1)a1*2*3*(p-1)(mod p)即W*a(p-1)W(modp)。易知(W,p)=1，由引理1可知a(p-1)1(modp）中國余數(shù)定理:設(shè) n=n1*n2.nk, 其中因子兩兩互質(zhì).有:a-(a1,a2,.,ak), 其中ai = a mod ni, 則 a和(a1,a2