初等數論精講與習題講解.doc

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