初等數(shù)論總復(fù)習(xí)題與知識點總結(jié)

1、初等數(shù)論學(xué)習(xí)總結(jié)本課程只介紹初等數(shù)論的的根本容。由于初等數(shù)論的根本知識和技巧與中學(xué)數(shù)學(xué)有著 密切的關(guān)系，因此初等數(shù)論對于中學(xué)的數(shù)學(xué)教師和數(shù)學(xué)系特別是師院校的本科生來說, 是一門有著重要意義的課程，在可能情況下學(xué)習(xí)數(shù)論的一些根底容是有益的一方面通過 這些容可加深對數(shù)的性質(zhì)的了解，更深入地理解某些他鄰近學(xué)科，另一方面，也許更重要 的是可以加強他們的數(shù)學(xué)訓(xùn)練，這些訓(xùn)練在很多方面都是有益的正因為如此，許多高等 院校，特別是高等師院校，都開設(shè)了數(shù)論課程。最后，給大家提一點數(shù)論的學(xué)習(xí)方法，即一定不能忽略習(xí)題的作用，通過做習(xí)題來理解數(shù)論 的方法和技巧，華羅庚教授曾經(jīng)說過如果學(xué)習(xí)數(shù)論時只注意到它的容而忽略習(xí)題

2、的作用， 那么相當(dāng)于只身來到寶庫而空手返回而異。數(shù)論有豐富的知識和悠久的歷史，作為數(shù)論的學(xué)習(xí)者，應(yīng)該懂得一點數(shù)論的常識，為此在 輔導(dǎo)材料的最后給大家介紹數(shù)論中著名的“哥德巴赫猜測和費馬大定理的閱讀材料。初等數(shù)論自學(xué)安排第一章：整數(shù)的可除性6學(xué)時自學(xué)18學(xué)時整除的定義、帶余數(shù)除法最大公因數(shù)和輾轉(zhuǎn)相除法整除的進一步性質(zhì)和最小公倍數(shù)素數(shù)、算術(shù)根本定理x和x的性質(zhì)與其在數(shù)論中的應(yīng)用習(xí)題要求 p3 :2， 3 ；p8 :4 ；Pl2 :1 ；P17 :1， 2，5；p20 : 1。第二章：不定方程4學(xué)時自學(xué)12學(xué)時二元一次不定方程ax by c多元一次不定方程 a1x1 a2x2anxn c勾股數(shù)費爾馬

3、大定理。習(xí)題要求 P29: 1, 2, 4; P31 : 2, 3。第三章：同余 4 學(xué)時自學(xué) 12學(xué)時 同余的定義、性質(zhì) 剩余類和完全剩余系 歐拉函數(shù)、簡化剩余系 歐拉定理、費爾馬小定理與在循環(huán)小數(shù)中的應(yīng)用 習(xí)題要求 p43 ：2， 6； p46 ：1； p49 ： 2，3； p53 1 ，2。第四章：同余式方程 4 學(xué)時自學(xué) 12學(xué)時同余方程概念子定理 高次同余方程的解數(shù)和解法 素數(shù)模的同余方程 威爾遜定理。習(xí)題要求 p60：1； p64 ：1，2； p69 ： 1，2。第五章：二次同余式和平方剩余 4 學(xué)時自學(xué) 12 學(xué)時二次同余式單素數(shù)的平方剩余與平方非剩余勒讓德符號二次互反律雅可比符

4、號、素數(shù)模同余方程的解法習(xí)題要求 p78 ：2； p81 ：1， 2， 3； p85 ：1，2； p89 ：2； p93 ： 1。 第一章：原根與指標 2 學(xué)時自學(xué) 8 學(xué)時指數(shù)的定義與根本性質(zhì)原根存在的條件指標與 n 次乘余 模 2 與合數(shù)模指標組、特征函數(shù)習(xí)題要求p123: 3。? 第一章整除一、主要容整除的定義、帶余除法定理、余數(shù)、最大公因數(shù)、最小公倍數(shù)、輾轉(zhuǎn)相除法、互素、兩兩互素、素數(shù)、合數(shù)、 算術(shù)根本定理、Eratosthesen篩法、x和x的性質(zhì)、n!的標準分 解式。二、根本要求通過本章的學(xué)習(xí)，能了解引進整除概念的意義，熟練掌握整除整除的定義以與它的根本性質(zhì)，并能應(yīng)用這些性質(zhì)，了解

5、解決整除問題的假設(shè)干方法，熟練掌握本章中二個著名的定理： 帶余除法定理和算術(shù)根本定理。 認真體會求二個數(shù)的最大公因數(shù)的求法的理論依據(jù)，掌握素數(shù)的定義以與證明素數(shù)有無窮多個的方法。能熟練求出二個整數(shù)的最大公因數(shù)和最小公倍 數(shù)，掌握高斯函數(shù)x的性質(zhì)與其應(yīng)用。三、重點和難點(1) 素數(shù)以與它有關(guān)的性質(zhì)，判別正整數(shù) a為素數(shù)的方法，算術(shù)根本定理與其應(yīng)用(2) 素數(shù)有無窮多個的證明方法。(3) 整除性問題的假設(shè)干解決方法。(4) x的性質(zhì)與其應(yīng)用，n!的標準分解式。四、自學(xué)指導(dǎo)整除是初等數(shù)論中最根本的概念之一，b I a的意思是存在一個整數(shù)q,使得等式a=bq 成立。因此這一標準作為我們討論整除性質(zhì)的根

6、底。也為我們提供了解決整除問題的方法。 即當(dāng)我們無法用整除語言來表達或討論整除問題時，可以將其轉(zhuǎn)化為我們很熟悉的等號問 題。對于整除的假設(shè)干性質(zhì)，最主要的性質(zhì)為傳遞性和線性組合性，即(1)a I b, b I c,那么有 a I c(2) a I b, a I c,貝U有 a I mb+nc讀者要熟練掌握并能靈活應(yīng)用。特別要注意，數(shù)論的研究對象是整數(shù)集合，比小學(xué)數(shù)學(xué) 中非負整數(shù)集合要大。本章中最重要的定理之一為帶余除法定理，即為設(shè)a是整數(shù)，b是非零整數(shù)，那么存在兩個整數(shù) q, r，使得a=bq+r(0 r冋)它可以重作是整除的推廣。同時也可以用帶余除法定理來定義整除性，(即當(dāng)余數(shù)r=0時)。帶

7、余除法可以將全體整數(shù)進行分類，從而可將無限的問題轉(zhuǎn)化為有限的問題。這是一種很重要的思想方法，它為我們解決整除問題提供了又一條常用的方法。同時也為我們建立同余理論建立了根底。讀者應(yīng)熟知常用的分類方法，例如把整數(shù)可分成奇數(shù)和偶數(shù)，特別對 素數(shù)的分類方法。例全體奇素數(shù)可以分成 4k+1, 4k+3;或6k+1, 6k+5等類型。和整除性一樣，二個數(shù)的最大公約數(shù)實質(zhì)上也是用等號來定義的，因此在解決此類問題時假設(shè)有必要可化為等式問題，最大公因數(shù)的性質(zhì)中最重要的性質(zhì)之一為a=bq+c，那么一定有(a, b) =(b, c),就是求二個整數(shù)的最大公約數(shù)的理論根據(jù)飛是解決關(guān)于最大公約數(shù)問 題的常用方法之一。讀

8、者應(yīng)有盡有認真體會該定理的證明過程?；ニ嘏c兩兩互素是二個不同的概念,既有聯(lián)系，又有區(qū)別。要認真體會這些相關(guān)的性質(zhì)， 例如，對于彳匚意 a ,b Z, 可設(shè)(a ,b ) =d，貝U a=dai ,b=db 1,貝U( ai ,b 1) =1，于是可對 ai ,b i使用相應(yīng)的定理，要注意，相關(guān)定理與推論中互素的條件是經(jīng)常出現(xiàn)的。讀者必須注 意定理成立的條件，也可以例舉反例來進行說明以加深影響。順便指出，假設(shè)|a I c,b I c,(a小 =1,那么ab I C是我們解決當(dāng)除數(shù)為合數(shù)時的一種方法。好處是不言而喻的。最小公倍數(shù)實際上與最大公因數(shù)為對偶命題。特別要指出的是a和b的公倍數(shù)是有無窮多個

9、。所以一般地在無窮多個數(shù)中尋找一個最小數(shù)是很困難的，為此在定義中所有公倍數(shù)中的最小的正整數(shù)。這一點實際上是應(yīng)用|自然數(shù)的最小自然數(shù)原理即自然數(shù)的任何一個子集 一定有一個最小自然數(shù)有在。最小公倍數(shù)的問題一般都可以通過以下式子轉(zhuǎn)化為最大公因數(shù) 的問題。兩者的關(guān)系為a ,b N, a ,b=-2a, b上述僅對二個正整數(shù)時成立。當(dāng)個數(shù)大于2時，上述式子不再成立。證明這一式子的關(guān) 鍵是尋找a , b的所有公倍數(shù)的形式，然后從中找一個最小的正整數(shù)。解決了兩個數(shù)的最小公倍數(shù)與最大公因數(shù)問題后，就可以求出|n個數(shù)的最小公倍數(shù)與最大公因數(shù)問題，可以兩個兩個地求。即有下面定理設(shè) ai,a2, an 是 n 個整

10、數(shù)，(印®) d2，(d2,a3) d?, (dni,aQ dn,那么(aa?, an) = dn,|設(shè)aia? m2，(m2,a3) m3, (m. i,an) m.,那么有印月2, an=mn，素數(shù)是數(shù)論研究的核心，許多中外聞名的題目都與素數(shù)有關(guān)。除1外任何正整數(shù)不是質(zhì)數(shù)即為合數(shù)。判斷一個的正整數(shù)是否為質(zhì)數(shù)可用判別定理去實現(xiàn)。判別定理又是證明素數(shù)無窮的關(guān)鍵。實際上，對于任何正整數(shù) n>1,由判別定理一定知存在素數(shù) p,使得p I n 即任何大于1的整數(shù)一定存在一個素因數(shù)p。素數(shù)有幾個屬于在本身的性質(zhì)，這些性質(zhì)是在 獨有的，讀者可以用反例來證明：素數(shù)這一條件必不可少。以加深對

11、它們的理解。|其中p Iab p I a或p I b也是常用的性質(zhì)之一 |。也是證明算術(shù)根本定理的根底。算術(shù)根本定理是整數(shù)理論中最重要的定理之一，即任何整數(shù)一定能分解成一些素數(shù)的乘積，而且分解是唯一的，不是任何數(shù)集都能滿足算術(shù)根本定理的，算術(shù)根本定理為我們提供 了解決其它問題的理論保障。它有許多應(yīng)用，由算術(shù)根本定理我們可以得到自然數(shù)的標準分解問題設(shè) a= P i 1 P k k ，b= p 1 1 p k k， i 0, i 0那么有(a，b)= p 11 . p kk i min( i, i)a，b= p 1 1 p k k i max( i,例如可求最大公約數(shù)，正整數(shù)正約數(shù)的個數(shù)等方面問題

12、，對具體的n,真正去分解是件不容易的事。對于較特殊的 n，例如|n!分解還是容易的。應(yīng)用x的性質(zhì)，n!的標準分解式可由一個具體的公式表示出來，這一公式結(jié)合x的性質(zhì)又提供了解決帶有乘除符號的整 除問題的方法。本章的許多問題都圍繞著整除而展開，讀者應(yīng)對整除問題的解決方法作一簡單的小結(jié)。五、例子選講補充知識 最小自然數(shù)原理：自然數(shù)的任意非空子集中一定存在最小自然數(shù)。 抽屜原理：(1) 設(shè)n是一個自然數(shù)，有n個盒子，n+1個物體，把n+1個物體放進n個盒子，至少 有一個盒子放了兩個或兩個以上物體；(2) km+1個元素，分成k組，至少有一組元素其個數(shù)大于或等于m+1；(3) 無限個元素分成有限組，至少

13、有一組其元素個數(shù)為無限。 梅森數(shù)：形如pn-i |的數(shù)叫梅森數(shù)，記成 M=2n-i I。° n 費爾馬數(shù)：n為非負整數(shù)，形如221的數(shù)叫費爾馬數(shù)，記成Fn=221。 設(shè)n=Pi1Pkk，設(shè)n的正因子個數(shù)為d(n)，所有正因子之和為(n )，貝U有d(n) (i 1) ( 21).( k 1)1，k 1 a/ 、 P11 P21 Pk 1(n )-P11P21 Pk 1 有關(guān)技巧1. 整數(shù)表示 a=aoX 10n+a1X 10n-1+an，a=2kb(b為奇數(shù))2. 整除的常用方法a. 用定義b. 對整數(shù)按被n除的余數(shù)分類討論c. 連續(xù)n個整數(shù)的積一定是n的倍數(shù)d. 因式分解疋bn=(

14、a-b)M,an+bn=(a+b) M,2 * ne. 用數(shù)學(xué)歸納法f. 要證明a|b，只要證明對任意素數(shù)p, a中p的幕指數(shù)不超過b中p的幕指數(shù)即可,用p(a)表示a中p的幕指數(shù)，貝U a|b p(a) p(b)例題選講例1請寫出10個連續(xù)正整數(shù)都是合數(shù)解：11!+2 , 11!+3,11! +11。例2.證明連續(xù)三個整數(shù)中，必有一個被 3整除。證：設(shè)三個連續(xù)正數(shù)為 a, a+1, a+2,而a只有3k, 3k+1, 3k+2三種情況，令a=3k，顯然 成立，a=3k+1 時，a+2=3(k+1) , a=3k+2 時，a+仁3(k+1)。例3.證明Ig2是無理數(shù)。證：假設(shè)Ig2是有理數(shù)，那

15、么存在二個正整數(shù) p, q，使得Ig2= p，由對數(shù)定義可得10p=2q , q那么有2p 5p =2q,那么同一個數(shù)左邊含因子5,右邊不含因子5,與算術(shù)根本定理矛盾。Ig2為無理數(shù)。例 4.求(21 n+4, 14n+3)解：原式=(21 n+4,14 n+3)=(7 n+1,14 n+3)=(7 n+1,7 n+2)=(7 n+1,1)=1例5.求2004!末尾零的個數(shù) 解：因為10=2X 5,而2比5多，所以只要考慮2004!中5的幕指數(shù)，即5 (2004!) = 200452004252004200412554200455例 6.證明(n! ) (n-1)! |( n!)!證：對任意素

16、數(shù)p,設(shè)(n! ) (n-1)!中素數(shù)p的指數(shù)為(n! ) !中p的指數(shù)B，那么(n(n1)!k 1(nx ) n (x )n!k 1 pkn(n 1)!k 1 pkk1(n.n!orp(n1!k1n!即，即左邊整除右邊例 7.證明 2003| (20022002+20042004-2005) 證： 2002 2002= (2003-1 ) 2002=2OO3IU+1 2OO42004= (2003+1) 2002=2OO3M+1 2OO22OO2+2OO4"OO4-2OO5=2OO3 (M1+M2-1 ) 由定義 2003| (2002"002+20042004-2005

17、)例8.設(shè)d(n)為n的正因子的個數(shù)，(n)為n的所有正因子之和，求d(1000)，33解：1000=2 5(1000)。 d(1000)=(3+1)(3+1)=16 ，(1000)= 2 454例9.設(shè)c不能被素數(shù)平方整除，假設(shè)a2| b2c，那么a| b證：由 p(c) < 1，且 p( a2) < p( b2c) 2p(a) <2p(b)+p(c) , p(a) <p(b)+罟即 p(a) < p(b) ,.alb例10.假設(shè)M為素數(shù)，那么n定為素數(shù)。證：假設(shè)n為合數(shù)，那么設(shè)n=ab，(1<a,b<n)2 ab-仁(2 ) b-1=(2 a-1)

18、 M為合數(shù)，與M為素數(shù)矛盾, n為素數(shù)。例 11.證明對任意 m,n，m# n,( Fn,F"=1。n 1 n 1 n 1證：不妨設(shè) n>m 那么 Fn-2= ( 21 ) ( 221) =(Fn-i-2)( 221)設(shè)( Fn,F m) =d, 那么 d|Fn, d|Fm d|2 但Fn為奇數(shù)，d = 1,即證。例 12. 設(shè) m,n 是正整數(shù)。證明(2m 1,2n 1)2(m,n)1證 : 不妨設(shè) m n 。由帶余數(shù)除法得mq1nr1 , 0 r1n.我們有2m 1 2q1n r1 2r12r1 12r1 (2q1n 1) 2r1 1由此與 2n 1| 2q1n1 得 ,

19、(2m1,2n 1)=(2n 1,2r1 1)注意到 (m,n ) (n,r1) , 假設(shè) r10 , 那么 (m,n )n , 結(jié)論成立 . 假設(shè) r1 0 , 那么繼續(xù)對 (2n 1,2r1 1) 作同樣的討論，由輾轉(zhuǎn)相除法知，結(jié)論成立。顯見， 2 用任一大于 1 的自然 a 代替，結(jié)論都成立。例 13. 證明：對任意的正整數(shù) n ，成立如下不等式 lg n k lg 2 。其中l(wèi)gn是數(shù)n的以10為底的對數(shù)，k是n的不同的素因數(shù)(正的)的個數(shù)。證：設(shè)n是大于1的整數(shù)(如果n =1，上述不等式顯然成立，因k=0)，卩仆卩?,，pk是n的k個 相異的素因素。 n 的素因數(shù)分解式為n p11p

20、22.pkk .( li ti U.-k),由于 Pi 2,(i 1,2., k)，從而n p1l1pl22.pklk 2l1 2l2 . 2lk 2l1 l2 . lk ，而 l1 l2 . lk k ，故 n 2 k 。將上述不等式取對數(shù)(設(shè)底a 1),那么有l(wèi)og a n kloga 2。特別有 lg n k lg 2 。例 14. 試證明任意一個整數(shù)與它的數(shù)字和的差必能被 9 整除，并且它與它的數(shù)字作任意調(diào)后 換后所成整數(shù)的差也能被 9 整除。證：設(shè)整數(shù)m的個位、十位、百位的數(shù)字分別為ai,a2，an，那么m可表作:n1m a110a 2100a 3.10 ann 1個(a1 a2 a

21、 3an ) (9a2 99a399. 9a n )n 1個(a1a 2 a 3an ) 9(a2 11a311. 1a n )所以 m (a1 a 2 a 3an)9(a211a3n 1個11. 1a n )因為a2 , a3,，an都是整數(shù)，所以任一整數(shù)與其數(shù)字之和的差必能被 9整除再設(shè)將 a1 , a2 ，an 按任一種順序排成 a'1, a'2， a'n，并令a1 a2. aa'1 a'2 . a'n ，m a 110a 2101an ，m' a'1 10a'2 . 10n 1a'n 。根據(jù)前面證明的結(jié)果，

22、知存在整數(shù) A，B,使m 9A,m'' 9B.因為 ' ，所以 m m ' 9A ' 9B 9(A B ) 。由于A-B是整數(shù)，這就證明了 m m'能被9整除。注：假設(shè)對某個整數(shù)k(1 k n)，有a'k 0，但當(dāng)k i n時，a'i 0，那么此時m'為整數(shù):m' a'1 10a'2 .10k 1 a'k ,即 m' a'k .a'2 a'1。如前證，此時結(jié)論正確。又當(dāng) m 為負整數(shù)與零時，結(jié)論顯然正確? 第二章 不定方程、主要容x2+y2=z2 通解公式、無

23、窮一次不定方程有解的條件、解數(shù)、解法、通解表示，不定方程 遞降法、費爾馬大定理。、根本要求1、了解不定方程的概念，理解對“解的認識，掌握一次不定方程ax by c 有解的條件，能熟練求解一次不定方程的特解，正整數(shù)解與通解。了解多元一次不定方程a1x1 a2 x2anXn c有解的條件，在有解的條件下的解法2、掌握不定方程x2+y2=z2在一定條件下的通解公式，并運用這個通解公式作簡單的應(yīng)用。3、對費爾馬大定理應(yīng)有在常識性的了解，掌握無窮遞降法求證不定方程x4+y4=z2無解的方法。4、掌握證明不定方程無解的假設(shè)干方法。、難點和重點1重點為求解一次不定方程的方法2掌握第二節(jié)中引證的應(yīng)用。1費爾馬

24、無窮遞降法。四、自學(xué)指導(dǎo)不定方程主要講解以下幾個問題i 給定一類不定方程，判別在什么條件下有解。ii 在有解的條件下，有多少解iii 在有解的條件下，求出所給的不定方程的所有解。元一次不定方程的一般形式為 ax+by=c。假設(shè)a ,b I c，那么該二元一次不定方程一定有解,假設(shè)一個特解，那么一切解可以用公式表示出來，因此求它的通解只要求出一個特解即可。求解二元一次不定方程的一個通解有好多種方法。讀者應(yīng)該總結(jié)一下，各種方法都有獨到之 處。特別要指出用最大公因數(shù)的方法。它的根據(jù)是求 a ,b 時所得的結(jié)果。由于注意通解 公式x=xo-bit，y=yo+ait中ai，bi的意義和位置。以免出錯。多

25、元一次不定方程a1x1 a2x2anxn c也有類似的結(jié)果，但在求解的過程中將它轉(zhuǎn)化二元一次不定方程組，從最后一個二元一次不定方程解起，可逐一解出X1,X2 ,Xn。所用的方法一般選擇最大公因數(shù)的方法。 由于n元一次不定方程可轉(zhuǎn)化為n-1個二元一次不定 方程組，故在通解中依賴于n-1個任意常數(shù)。但不象二元一次不定方程那樣有公式來表示。x2+y2=z2的正整數(shù)解稱為勾股數(shù)，在考慮這個方程時，我們對x ,y 作了一些限制，而這些限制并不影響其一般性。在條件x>0,y>0,z>0, (x,y)=1,2 I x的條件可以給出x2+y2=z2 的通解公式，x=2ab，y=a2-b2，z

26、2=a2+b2， a>b>0 , (a ,b)=1，a ,b 一奇一偶。假設(shè)將 2 I x 限為2 I y，那么也有相應(yīng)的一個通解公式。在證明這個通解公式的過程中，用到了引理uv=w2,u>0, v>0, (u ,v ) =1,貝U u=a2, v=b2, w=ab。 a>0, b>0, (a ,b ) =1。利用這個結(jié)論可以 求解某些不定方程。特別當(dāng) w=1或素數(shù)p。那么由uv=1或uv=P可將原不定方程轉(zhuǎn)化為不定方程組。從而獲得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望讀者能掌 握這種方法。為了解決著名的費爾馬大定理：xn+yn=zn ,

27、n?3無正整數(shù)解時，當(dāng)n=4時可以用較初等 的方法給出證明。證明由費爾馬本人給出的，一般稱為費爾馬無窮遞降法。其根本思想為由 一組解出發(fā)通過構(gòu)造得出另一組解， 使得兩組解之間有某種特定的關(guān)系， 而且這種構(gòu)造可以 無限重復(fù)的。從而可得到矛盾。因此無窮遞降法常用來證明某些不定方程無整數(shù)解。證明一類不定方程無解是研究不定方程鄰域中常見的形式，一般的要求解不定方程比證明不定方程無解要容易些。證明不定方程無解的證明方法常采用以下形式：(反證法)假設(shè)A有解 Ai有解 A有解 A有解，而A本身無解，這樣來構(gòu)造矛盾。從而 說明原不定方程無解。對于證明不定方程的無解性通常在幾種方法，一般是總的幾種方法交替使用。

28、特別要求 掌握：簡單同余法、因子分解法、不等式法，以與中學(xué)數(shù)學(xué)中所涉與的判別式法。五、例子選講例1:利用整數(shù)別離系數(shù)法求得不定方程15x+10y+6z=61。解：注意到z的系數(shù)最小，把原方程化為11Z=( 15x10y61) 2x 2y 10( 3x 2y 1)66令 t 1= -( 3x 2y 1) z，即-3 x+2y-6 11 + 1=06此時 y 系數(shù)最小，y 1(3x6t1 1) x 3t1 -1(x 1)令t 2=嚴1) z ,即x 2t2 1,反推依次可解得y=x+3t 1+t 2=2t 2+1+3t 1+t 2=1+3t 1+3t 2z=-2x-2y+10+t1=6-5t 1+

29、10t2x12t2y13ti3t2 t it 2 Zz65ti10t2原不定方程解為例2:證明.2是無理數(shù)證：假設(shè)2是有理數(shù)，那么存在自數(shù)數(shù)a,b使得滿足X2 2y2即a2 2b2，容易知道a是偶數(shù), 設(shè)a=2ai，代入得b2 2a1 ,又得到b為偶數(shù)，ay b a，設(shè)b 2S，那么aj 2bf ,這里b? ay 這樣可以進一步求得 a2，b2且有a>b>ai>bi> a2>b>但是自然數(shù)無窮遞降是不可能的，于是產(chǎn)生了矛盾，,2為無理數(shù)。例3:證明：整數(shù)勾股形的勾股中至少一個是 3的倍數(shù)。證：設(shè) N=3n± 1(m為整數(shù))，代=9吊±6葉

30、 1=3(3mi±2m)+1即一個整數(shù)假設(shè)不是3的倍數(shù)，那么其平方為3k+1,或者說3k+2不可能是平方數(shù)，設(shè)x,y為勾股整數(shù)，且x,y都不是3的倍數(shù)，那么x2, y2都是3k+1，但z2=x2+y2=3k+2形，這是不可能，勾股數(shù)中至少有一個是3的倍數(shù)。例4:求x2+y2=328的正整數(shù)解解： 328為偶數(shù)， x,y奇偶性一樣，即x±y為偶數(shù)，設(shè)x+y=2u,x-y=2v，代入原方程即 為u2+v2=164,同理令 u+v=2ui, u- v=2vi 有2 2ui vi 82,u i vi 2u 2, ui vi 2v 2u2 v； 4i, u2,v2 為一偶一奇，且 0

31、<u2<6u2=i, 2, 3, 4, 5 代方程，有解(4, 5) (5, 4)原方程解 x=i8,y=2,或 x=2,y=18。例5:求x2+xy-6=0的正整數(shù)解。解：原方程等價于x(x+y)=2 3,故有即有 x=2,y=1;x=1,y=5. x2, x3, x1, x6,xy3, xy2, xy6, xy1. 例6:證明不定方程x2-2xy2+5z+3=0無整數(shù)解。解：假設(shè)不定方程有解，那么x y2.y4 5z 3但 y4=0, 1(mod5), 對 y,z, y4-5z-3 = 2, 3(mod5)而一個平方數(shù)三0, 1, 4 (mod 5) y4-5z-3不可能為完全

32、平方，即y4 5z 3不是整數(shù)，所以原不定方程無解。例7:證明：x2y2 z2 8a 7無整數(shù)解證：假設(shè)原方程有解，那么有x2 y2 z2 8a 7(mod 8)注意到對于模8,有02 0, 12 1,224,321,42 0,52 1, 62 4, 721,因而每一個整數(shù)對于模8,必同余于0, 1, 4這三個數(shù)。不管 x2, y2, z2 如何變化，只能有 x2 y2 z2 0,1,2,3,4,5,6(mod8)而8a 7 7(mod8)，故8a 7不同余于x2y2 z2關(guān)于模8，所以假設(shè)錯誤，即8a 7 x2 y2z2，從而證明了原方程無解。例8:某人到銀行去兌換一 d元和c分的支票，出納

33、員出錯，給了他 c元和d元，此人直到 用去23分后才覺察其錯誤，此時他發(fā)現(xiàn)還有2d元和2c分，問該支票原為多少錢？解：由題意立式得：108 d 23 100 2d 2c即 98c199d23.令 u c 2d 得 98u 3d 23,令 v 33u d 得 3v u 23.所以u 3v 23(v為任意整數(shù))，代入得：d33u v98v3323,( 1)cu 2d199v6723,其中V是任意整數(shù)。又根據(jù)題意要求：d 0,0 c 100 .根據(jù)，僅當(dāng)V=8時滿足此要求，從而d 25, c 51.因此該支票原為25元51分.AVV*第二早同余、主要容同余的定義、性質(zhì)、剩余類和完全剩余系、歐拉函數(shù)、

34、簡化剩余系、歐拉定理、費爾馬小定理、循環(huán)小數(shù)、特殊數(shù) 2, 3, 4，5, 6，7, 8, 9，11，13的整除規(guī)律二、根本要求通過本章的學(xué)習(xí)，能夠掌握同余的定義和性質(zhì)，區(qū)別符號：“三和=之間的差異。能利用同余的一些根本性質(zhì)進行一些計算，深刻理解完全剩余系，簡化剩余系的定義、性質(zhì)與 構(gòu)造。能判斷一組數(shù)是否構(gòu)成模m的一個完全剩余系或一個簡化剩余系。能計算歐拉函數(shù)的 值，掌握歐拉定理、費爾馬小定理的容以與證明方法。能應(yīng)用這二個定理證明有關(guān)的整除問 題和求余數(shù)問題。能進行循環(huán)小數(shù)與分數(shù)的互化。三、難點和重點(1) 同余的概念與根本性質(zhì)(2) 完全剩余系和簡化剩余系的構(gòu)造、判別(3) 歐拉函數(shù)計算、歐

35、拉定理、費爾馬小定理的證明與應(yīng)用(4) 循環(huán)小數(shù)與分數(shù)的互化(5) 特殊數(shù)的整除規(guī)律。四、自學(xué)指導(dǎo)同余理論是初等數(shù)論中最核心的容之一，由同余定義可知，假設(shè)a= b(mod m),貝U a和b被m除后有一樣的余數(shù)。這里 m為正整數(shù)，一般要求m大于1,稱為模，|同余這一思想本質(zhì)是將整數(shù)按模m分類，然后討論每一個類中整數(shù)所具有的共性與不同類之間的差異。第同余還有二個等價的定義：用整除章中用帶余除法定理將整數(shù)分類解決一些問題的方法只不過是同余理論中的一個特殊例子。 從同余的定理上看，同余和整除實際上是同一回事，故來定義即m I a-b。用等號來定義a=b+mt。值得注意a和b關(guān)于m同余是個相對概念即它

36、是相對于模m來講，二個整數(shù)a和b關(guān)于一個整數(shù)模m同余。那么對于另一個整數(shù)模 m， a和b未必會同余。從定義上看，同余和整除是同一個事情，但引進了新的符號“三后，無論從問題的敘 述上，還是解決問題的方法上都有了顯著的變化，同時也帶來了一些新的知識和方法。在引 進了同余的代數(shù)性質(zhì)和自身性質(zhì)后，同余符號“三和等號“=相比，在形式上有幾乎致的性質(zhì)，這便于我們記憶。事實上在所有等號成立的運算中，只有除法運算是個例外，即 除法的消去律不成立。為此對于同余的除法運算我們有二種除法：(i )模不改變的除法，假設(shè) ak = bk(mod m) ，(k,m)=1，貝U a= b(mod m)(ii)模改變的除法,

37、 假設(shè) ak = bk(mod m) (k,m)=d,貝U a= b mod a這一點讀者要特別注意。完全剩余系和簡化剩余系是二個全新的概念，讀者只要搞清引成這些概念的過程。因為 同余關(guān)系是一個等價關(guān)系，利用等價關(guān)系可以進行將全體整數(shù)進行分類，弄清來朧去脈，對 于更深刻理解其本質(zhì)是很有好處的。完全剩余系或簡化剩余系是一個以整數(shù)為元素的集合， 在每個剩余類各取一個數(shù)組成的 m個不同數(shù)的集合，故一組完全剩余系包含 m個整數(shù)，由于 二個不同的剩余類中的數(shù)關(guān)于 m兩兩不同余，故可得判別一組數(shù)是否為模m的一個完全剩余 系的條件有二條為(1) 個數(shù)=m(2) 關(guān)于m兩兩不同余另外要能用完全剩余系構(gòu)造新的完

38、全剩余系。即有定理設(shè)(a，m) =1，x為m的完全剩余系，那么ax+b也是m的完全剩余系當(dāng)(g,m2)1時，能由 mi的完全剩余系和 m?的完全剩余系，構(gòu)造 mim?完全剩余系。為討論簡化剩余系，需要引進歐拉函數(shù)© (m),歐拉函數(shù)© (n)定義為不超過m且與m互素的正整數(shù)的個數(shù)，記為© (m,要掌握© (m)的計算公式，了解它的性質(zhì)。這些性質(zhì)最主要1的是當(dāng)(a ,b ) =1 時，© (ab) = © (a) © (b)，和(p ) p p現(xiàn)在在剩余類中把與 m互素的集合分出來，從中可在各個集合中任取一個數(shù)即可構(gòu)造模 m的

39、一個簡化剩余系。另一方面，簡化剩余數(shù)也可從模m的一個完全剩余系中得到簡化剩余系，一組完全剩余系中與 m互素的的數(shù)組成的© (n)個不同數(shù)的集合稱為 m簡化剩余系。同 樣簡化剩余系也有一個判別條件。判別一組整數(shù)是否為模m的簡化剩余系的條件為(2) 個數(shù)=© (m)(3) 關(guān)于m兩兩不同余(3) 每個數(shù)與m互素關(guān)于m的簡化剩余系也能用完全剩余系構(gòu)造新的簡化剩余系。設(shè)(a, m) =1, x為m的簡化剩余系，貝U ax也是m的簡化剩余系。當(dāng)(m, m2) 1時，能由g的簡化剩余系和m2的簡化剩余系，構(gòu)造口!口2簡化剩余系。歐拉定理、費爾馬小定理是同余理論非常重要的定理之一。要注意

40、歐拉定理和費爾馬定 理的條件和結(jié)論。歐拉定理：設(shè) m為大于 1的整數(shù)，(a，m) =1，那么有a (m) 1(modm)費爾馬小定理：假設(shè)p是素數(shù)，那么有就歐拉定理、費同余方法也是解ap a(mod p)除此以外，歐拉定理的證明的思想是非常好的，在各個地方都有應(yīng)用爾馬小定理來講，它在某些形如 an數(shù)的整除問題應(yīng)用起來顯得非常方便決整除問題的方法之一。另外同余方法在證明不定方程時也非常有用，即要掌握同余“三和相等“=的關(guān)系:相等必同余，同余未必相等，不同余肯定不相等。對于特殊數(shù)的整除規(guī)律要求能掌握其一般定理的證明，并 熟記一些特殊數(shù)的整除規(guī)律1、一個整數(shù)被2整除的充要條件是它的末位為偶數(shù)2、一個

41、整數(shù)被3整除的充要條件是它的各位數(shù)字之和能被3整除3、一個整數(shù)被9整除的充要條件是它的各位數(shù)字之和能被9整除4、一個整數(shù)被5整除的充要條件是它的末位為0或55、一個整數(shù)被4, 25整除的充要條件是它的末二位能被 4, 25整除6、一個整數(shù)被8, 125整除的充要條件是它的末三位能被 8, 125整除。7 設(shè)a an1000n k "000“ 1a。，那么7或11或13整除a的充要條件是7或 科假設(shè)1<i <p,那么有i | p那么與p為素數(shù)矛盾i=p,二 p|q-1又v q-1為偶數(shù),2|q-1, 2 p| q-1, q-1= 2pk,即 q=2pk+1例 4:證明 13

42、|42n+1+3n+2證：42n+1+3n+J 4 16n+93nnn -三3 (4+9)三 13X3 三0(13) 13|4 2n+1+3n+2例5：證明5y+3=x2無解證明：假設(shè)5y+3=x2有解，那么兩邊關(guān)于模5同余有 5y+3=x2(mod 5)即 3=x2(mod 5)而任一個平方數(shù) x = 0,1,4(mod 5) 30,1,4(mod 5)即得矛盾，即5y+3=x2無解例6:求111被7除的余數(shù)。50解:v 111111 被 7 整除, 11 1 = 11 (mod 7)= 4 (mod 7),即余數(shù)為 450例7:把0.042 63化為分數(shù)。解：設(shè) b=0.042 63，從而

43、 1000b=42. 63,100000b=4263.63 , 99000b=4263-42._4221 _ 469b一=。9900011000當(dāng)然也可用直化分數(shù)的方法做。例8:設(shè)一個數(shù)為62XY427是9,11的倍數(shù)，求X, Y解：因為 9|62XY427所以 9|6+2+X+Y+4+2+7 即 9|21+X+Y又因為 11|62XY427,有 11 | (7+4+X+6-2-Y-2)即 11| ( X-Y+13)因為 0 X, Y 9，所以有 2121+X+Y 39，4X-Y+1322,由此可知21+X+Y=27 X-Y+13=11或 21+X+Y=36 X-Y+13=22X+Y=6 X-

44、Y=-2或 X+Y=15 X-Y=9,解得 X=2, Y=4例9:證明：8a+7不可能是三個整數(shù)的平方和。證：由于每一個整數(shù)對于 8,必同余于0 , 1 , 2 , 3 , 4 , 5 , 6 , 7這八個數(shù)之一 注意到對于模8,有020,121,224,321,420,521, 624, 721,因而每一個整數(shù)對于模8,必同余于0 , 1 , 4這三個數(shù)不能 x2,y2,z2如何變化，只能有 x2 y2 z2 0,1,2,3,4,5,6(mod8)而8a 7 7mod8),故8a 7不同余于x2 y2 z2關(guān)于模88a 7 x2 y2 z2 ,從而證明了結(jié)論。?第四章同余式、主要容同余方程概

45、念與次數(shù)、解的定義,一次同余方程ax= b(modm)有解的充分必要條件，一次同余方程組，子定理，高次同余方程，素數(shù)模的同余方程，威爾遜定理 二、根本要求通過本章的學(xué)習(xí)要求掌握同余方程的一些根本概念，例同余方程的次數(shù)、解等，能解一次 同余方程，一次同余方程組，理解子定理并用它來解一次同余方程組，會解高次同余方程， 對于以素數(shù)模的同余方程的一般理論知識能理解。三、重點和難點(1) 子定理的容與證明，從中學(xué)會求出一次同余方程組的解并從中引伸更一般的情形，即 模不二二互素的情形。(2) 素數(shù)模的同余方程的一些根本理論性問題，并能與一般方程所類似的性質(zhì)作比擬。四、自學(xué)指導(dǎo)同余方程和不定方程一樣，我們同

46、樣要考慮以下三個問題，即|有解的條件，解數(shù)與如何求解，一般地說，對于一般的同余方程，由于僅有有限個解，只要把模m的一個完全剩余系一一代入驗算總解組那么所需的結(jié)果。因此上述三個問題已根本解決，只不過具體到某一個 同余方程計算起來困難一點而異。但對于解數(shù)，傳統(tǒng)的結(jié)果不再成立。例如一個同余方程的 解數(shù)可以大于其次數(shù)。讀者可以舉出反例來證明這一事實。要學(xué)好同余方程這一章。必須首先弄清同余方程的概念，特別是同余方程解的概念，互 | 一樣余的解是同一個解。其次有使原同余方程和新的同余方程互相等價的假設(shè)干變換。 移項運 算是傳統(tǒng)的，同余方程兩邊也可以加上模的假設(shè)干倍。相當(dāng)于同余方程兩邊加“零 。|無論是乘上

47、一數(shù)k或除去一個數(shù)k，為了保持其同解性，必須(k ,m)=1,這一點和同余的性質(zhì)有區(qū)別一次同余方程的一般形式為 ax=b(mod m)，我們討論的所有容都在這標準形式下進行 的?？偨Y(jié)一次同余方程與二元一次不定方程有相當(dāng)?shù)穆?lián)系，一次同余方程的求解可以由二元一次不定方程的求解方式給出。反之亦然。但要注意在對“解的認識上是不一致的，從而 導(dǎo)致有無窮組解和有限個解的區(qū)別。為了求ax= b(mod m)的一個特解，可在條件(a ,m)=1下進行。教材上有假設(shè)干種求解方式，供讀者在同樣問題選擇使用。一次同余方程組的標準形式為x=bi(mod m)x=b2(mod m)(1)x=bn(mod m)假設(shè)給出的

48、同余方程組不是標準形式，必須注意化為標準形式，同時我們得到的有解的判別定理與求法方法都是這一標準形式得到的。同余方程組(1) 有解的條件(mi ,mj) I bi-bj，1w i , j w k。在使用時一定要對所有可解進行驗算，進行有解的判別求解一次同余方程組(1)有兩種方法：待定系數(shù)法和子定町。二種方法各有特長。待 定系數(shù)法適應(yīng)的圍較廣，對模沒有什么要求。子定理有一個具體的公式，形式也較漂亮。但 對模要二二互素。子定理為下面定理：(子定理)k 2,m1,m2,.,mk 兩兩互素，m mim2.mk ,m mjMj,i 1,2,.k 那么一次同余式組x b1 (mod m1), x b2(m

49、od m2),.x bk (mod mk)的解為x M1M M 2M 2b2.M kM kbk (modm),其中 MjM； 1(modm),i 1,2,.k.對待定系數(shù)法和子定理要有深刻的理解。體會其實質(zhì)，這樣不必死記硬背。次數(shù)大于1的同余方程稱為高次同余方程，一般地高次同等方程可轉(zhuǎn)化一系列的高次同 余方程組。然后將每一個高次同余方程的解都求出， 最后利用子定理也可求出原同余方程的 解。求高次同余方程解的根本方法有兩條，一是小模，二是降次|。1k. -I-設(shè)|m= PP k | ;貝卩要求 f(x) 三0(mod m)的解只要求 f(x) 三0(mod p a )| (2)的解即可，其中p為

50、素數(shù)。a > 1 。對于(2)的解的求法我們用待定系數(shù)法。設(shè)f(x) = 0(mod p)的解為x=X1(mod p)為解。那么當(dāng)p卜f ' (x)時，f(x) = 0(mod p)的一個解X1可求出f(x) = 0(mod p )的一個解。方法如下：將 x=xi+pti 代入 f(x)= O(mod p2)有f(x i+pt i) = O(mod p ) f(x i)+pt f ' (x i) = O(mod p)f xL+bflxJ = O(mod p)ti=ti' + p t 2p代入 x=x 1 +pt 1=xi +p(t 1 ' +t 2p)=X

51、 2+ p2t 2那么x = X2(mod p2)即為f(x) = O(mod p2)的解。然后重復(fù)上述過程，即可由X2得f(x) = O(mod p a )的解X 3。最后求出f(x) = O(mod p a )的解x從上所述，關(guān)鍵是求素數(shù)模的同余方程f(x) = O(mod p)的解。f(x) = O(mod p)的性質(zhì)(1)同余方程的解與f(x)的分解之間的關(guān)系，這一點和代數(shù)方程幾乎一樣。注意素數(shù)p的條件必不可少。解數(shù)w次數(shù)。這一點和代數(shù)方程也一樣。此時,(2)同余方程的解數(shù)與次數(shù)之間有關(guān)系素數(shù)p的條件也必不可少本節(jié)的輔產(chǎn)品是著名的wilsom定理P為素數(shù)，那么有(p-1) !三-1(m

52、od p),例1:解一次同余式17x19(mod25)解：(17, 25) =1，原同余方程有解，利用形式分數(shù)的性質(zhì),同余方程解為196 187x7(mod 25)178 241x 2(mod12)例2:解同余方程組 x 6(mod10)x 1(mod15)解：(12, 10) |6+2 , (12, 15) |-2-1 , (10, 15) |6-1-原同余方程有解，且等位于x2(mod 4)x2(mod3)x2(mod 4)x6(mod2)x1 (mod 3)此時變成模兩兩互素x6(mod5)x1(mod 5)x1(mod3)x(mod5)由子定理可求得其解為：x 46(mod 60)例3

53、:解一次同余式組51x 57(mod 75)3x 1(mod4)解：用常規(guī)方法先求每一個一次同余式的解，得到以下一次同余式組x 7,32,57(mod75)x 3(mod 4)然后用子定理求解，所以同余方程組有3個解，且解分別為x 7(mod 300) , x 107 (mod 300) , x 207(mod 300)例 4:設(shè) 2p+1 是素數(shù)，那么(P!)2( 1)P 0(mod 2p 1)證：設(shè)n=2P+1,由假設(shè)n為素數(shù)，于是由威爾遜定理有(n-1)! = -1(mod n)由于(n-1)!+1 = (n-1)( n-2)(P+2)( p+1)p(p-1)3 2 1+1=1 (n -

54、1) 2( n -2) 2( n -3) (p-1) n-( p-1) p ( n-p)+1=p!( n-1)( n-2)(n-p)+1 = (p!) 2(-1) p+1(mod n) ( p! )2(-1) p +1 = 0(mod n) ( p!) 2+(-1) J 0(mod 2p+1)例5:解同余方程28x三21(mod 35)解：(28,35 ) =7|21 ,原同余方程有解，且有7個解原同余方程等價于4x=3(mod 5)而且 4x三 3(mod 5)解為 x= 2(mod 5)原同余方程解為 2, 7, 12, 17, 22, 27, 31 (mod 35)?第五章二次剩余理論、

55、主要容平方剩余與平方非剩余的概念、歐拉判別條件、勒讓德符號、二次互反律、雅可比符號、 素數(shù)模同余方程的解法根本要求通過本章的學(xué)習(xí)，掌握平方剩余與平方非剩余的概念，掌握勒讓德符號的定義、性質(zhì)計算 與利用它來判別一個二次同余方程是否有解，對于幾個較特殊的勒讓德符號的值， 要求能掌握它的推導(dǎo)方法。了解推可比符號的定義，性質(zhì)與功能，會解素數(shù)的模的二次同余方程。與 證明一些二次不定方程無解中的應(yīng)用。三、重點和難點(1) 歐拉判別定理：即a為p的平方剩余的條件。(2) 勒讓德符號，二次互反律。(3) 素數(shù)模同余方程的解法。四、自學(xué)指導(dǎo)對于一般的高次同余方程的求解歸納為模為 p"的情形。對于同余方程f(x) = O(mod p") 的求解依賴于f(x) = o(mod p)的解。而且對于一般的f(x)，求解f(x) = O(mod p)的解是很 困難的。本章討論f(x)為一個整系數(shù)的二次三項式