初等數(shù)論總復習題及知識點總結(jié)

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

2、而忽略習題的作用，則相當于只身來到寶庫而空手返回而異。數(shù)論有豐富的知識和悠久的歷史，作為數(shù)論的學習者，應該懂得一點數(shù)論的常識，為此在輔導材料的最后給大家介紹數(shù)論中著名的“哥德巴赫猜想”和費馬大定理的閱讀材料。初等數(shù)論自學安排第一章：整數(shù)的可除性（6學時）自學18學時整除的定義、帶余數(shù)除法最大公因數(shù)和輾轉(zhuǎn)相除法整除的進一步性質(zhì)和最小公倍數(shù)素數(shù)、算術(shù)基本定理x和x的性質(zhì)及其在數(shù)論中的應用習題要求：2，3 ； ：4 ；：1；：1，2，5；：1。第二章：不定方程（4學時）自學12學時二元一次不定方程多元一次不定方程勾股數(shù)費爾馬大定理。習題要求：1，2，4；：2，3。第三章：同余（4學時）自學12學時同

3、余的定義、性質(zhì)剩余類和完全剩余系歐拉函數(shù)、簡化剩余系歐拉定理、費爾馬小定理及在循環(huán)小數(shù)中的應用習題要求：2，6；：1；：2，3； 1，2。第四章：同余式（方程）（4學時）自學12學時同余方程概念孫子定理高次同余方程的解數(shù)和解法素數(shù)模的同余方程威爾遜定理。習題要求：1；：1，2；：1，2。第五章：二次同余式和平方剩余（4學時）自學12學時二次同余式單素數(shù)的平方剩余與平方非剩余勒讓德符號二次互反律雅可比符號、素數(shù)模同余方程的解法習題要求：2； ：1，2，3；：1，2；：2；：1。第一章：原根與指標（2學時）自學8學時指數(shù)的定義及基本性質(zhì)原根存在的條件指標及n次乘余模2及合數(shù)模指標組、特征函數(shù)習題要

4、求：3。 第一章 整除一、主要內(nèi)容整除的定義、帶余除法定理、余數(shù)、最大公因數(shù)、最小公倍數(shù)、輾轉(zhuǎn)相除法、互素、兩兩互素、素數(shù)、合數(shù)、算術(shù)基本定理、Eratosthesen篩法、x和x的性質(zhì)、n！的標準分解式。二、基本要求通過本章的學習，能了解引進整除概念的意義，熟練掌握整除 整除的定義以及它的基本性質(zhì)，并能應用這些性質(zhì)，了解解決整除問題的若干方法，熟練掌握本章中二個著名的定理：帶余除法定理和算術(shù)基本定理。認真體會求二個數(shù)的最大公因數(shù)的求法的理論依據(jù)，掌握素數(shù)的定義以及證明素數(shù)有無窮多個的方法。能熟練求出二個整數(shù)的最大公因數(shù)和最小公倍數(shù)，掌握高斯函數(shù)x的性質(zhì)及其應用。三、重點和難點（1）素數(shù)以及它

5、有關(guān)的性質(zhì)，判別正整數(shù)a為素數(shù)的方法，算術(shù)基本定理及其應用。（2）素數(shù)有無窮多個的證明方法。（3）整除性問題的若干解決方法。（4）x的性質(zhì)及其應用，n！的標準分解式。四、自學指導整除是初等數(shù)論中最基本的概念之一，ba的意思是存在一個整數(shù)q，使得等式a=bq成立。因此這一標準作為我們討論整除性質(zhì)的基礎。也為我們提供了解決整除問題的方法。即當我們無法用整除語言來敘述或討論整除問題時，可以將其轉(zhuǎn)化為我們很熟悉的等號問題。對于整除的若干性質(zhì)，最主要的性質(zhì)為傳遞性和線性組合性，即（1） ab, bc, 則有ac（2） ab, ac, 則有amb+nc讀者要熟練掌握并能靈活應用。特別要注意，數(shù)論的研究對象

6、是整數(shù)集合，比小學數(shù)學中非負整數(shù)集合要大。本章中最重要的定理之一為帶余除法定理，即為設a是整數(shù)，b是非零整數(shù)，則存在兩個整數(shù)q，r，使得 a=bq+r （0）它可以重作是整除的推廣。同時也可以用帶余除法定理來定義整除性，（即當余數(shù)r=0時）。帶余除法可以將全體整數(shù)進行分類，從而可將無限的問題轉(zhuǎn)化為有限的問題。這是一種很重要的思想方法，它為我們解決整除問題提供了又一條常用的方法。同時也為我們建立同余理論建立了基礎。讀者應熟知常用的分類方法，例如把整數(shù)可分成奇數(shù)和偶數(shù)，特別對素數(shù)的分類方法。例全體奇素數(shù)可以分成4k+1，4k+3；或6k+1，6k+5等類型。和整除性一樣，二個數(shù)的最大公約數(shù)實質(zhì)上也

7、是用等號來定義的，因此在解決此類問題時若有必要可化為等式問題，最大公因數(shù)的性質(zhì)中最重要的性質(zhì)之一為 a=bq+c，則一定有（a，b）=（b，c），就是求二個整數(shù)的最大公約數(shù)的理論根據(jù)。也是解決關(guān)于最大公約數(shù)問題的常用方法之一。讀者應有盡有認真體會該定理的證明過程?；ニ嘏c兩兩互素是二個不同的概念，既有聯(lián)系，又有區(qū)別。要認真體會這些相關(guān)的性質(zhì)，例如，對于任意a ,bZ，可設（a ,b）=d，則a=da1 ,b=db1，則（a1 ,b1）=1，于是可對a1 ,b1使用相應的定理，要注意，相關(guān)定理及推論中互素的條件是經(jīng)常出現(xiàn)的。讀者必須注意定理成立的條件，也可以例舉反例來進行說明以加深影響。順便指出，

8、若ac，bc，（a ,b）=1，則abc是我們解決當除數(shù)為合數(shù)時的一種方法。好處是不言而喻的。最小公倍數(shù)實際上與最大公因數(shù)為對偶命題。特別要指出的是a和b的公倍數(shù)是有無窮多個。所以一般地在無窮多個數(shù)中尋找一個最小數(shù)是很困難的，為此在定義中所有公倍數(shù)中的最小的正整數(shù)。這一點實際上是應用自然數(shù)的最小自然數(shù)原理，即自然數(shù)的任何一個子集一定有一個最小自然數(shù)有在。最小公倍數(shù)的問題一般都可以通過以下式子轉(zhuǎn)化為最大公因數(shù)的問題。兩者的關(guān)系為a ,bN， a ,b=上述僅對二個正整數(shù)時成立。當個數(shù)大于2時，上述式子不再成立。證明這一式子的關(guān)鍵是尋找a , b的所有公倍數(shù)的形式，然后從中找一個最小的正整數(shù)。解決

9、了兩個數(shù)的最小公倍數(shù)與最大公因數(shù)問題后，就可以求出n個數(shù)的最小公倍數(shù)與最大公因數(shù)問題，可以兩個兩個地求。即有下面定理設是n個整數(shù)，則（）=設則有=素數(shù)是數(shù)論研究的核心，許多中外聞名的題目都與素數(shù)有關(guān)。除1外任何正整數(shù)不是質(zhì)數(shù)即為合數(shù)。判斷一個已知的正整數(shù)是否為質(zhì)數(shù)可用判別定理去實現(xiàn)。判別定理又是證明素數(shù)無窮的關(guān)鍵。實際上，對于任何正整數(shù)n1，由判別定理一定知存在素數(shù)p，使得pn 。即任何大于1的整數(shù)一定存在一個素因數(shù)p 。素數(shù)有幾個屬于內(nèi)在本身的性質(zhì)，這些性質(zhì)是在獨有的，讀者可以用反例來證明：素數(shù)這一條件必不可少。以加深對它們的理解。其中pabpa或pb也是常用的性質(zhì)之一。也是證明算術(shù)基本定理

10、的基礎。算術(shù)基本定理是整數(shù)理論中最重要的定理之一，即任何整數(shù)一定能分解成一些素數(shù)的乘積，而且分解是唯一的，不是任何數(shù)集都能滿足算術(shù)基本定理的，算術(shù)基本定理為我們提供了解決其它問題的理論保障。它有許多應用，由算術(shù)基本定理我們可以得到自然數(shù)的標準分解問題。設a=，b=，則有（a，b）= a，b= 例如可求最大公約數(shù)，正整數(shù)正約數(shù)的個數(shù)等方面問題，對具體的n，真正去分解是件不容易的事。對于較特殊的n，例如n！分解還是容易的。應用x的性質(zhì)，n！的標準分解式可由一個具體的公式表示出來，這一公式結(jié)合x的性質(zhì)又提供了解決帶有乘除符號的整除問題的方法。本章的許多問題都圍繞著整除而展開，讀者應對整除問題的解決方

11、法作一簡單的小結(jié)。五、例子選講補充知識最小自然數(shù)原理：自然數(shù)的任意非空子集中一定存在最小自然數(shù)。抽屜原理：（1）設n是一個自然數(shù)，有n個盒子，n+1個物體，把n+1個物體放進n個盒子，至少有一個盒子放了兩個或兩個以上物體；（2）km+1個元素，分成k組，至少有一組元素其個數(shù)大于或等于m+1；（3）無限個元素分成有限組，至少有一組其元素個數(shù)為無限。梅森數(shù)：形如2n-1的數(shù)叫梅森數(shù)，記成Mn=2n-1。費爾馬數(shù)：n為非負整數(shù)，形如的數(shù)叫費爾馬數(shù)，記成Fn=。設n=，設n的正因子個數(shù)為d(n)，所有正因子之和為，則有有關(guān)技巧1. 整數(shù)表示a=a010n+a110n-1+an，a=2kb(b為奇數(shù))

12、2.整除的常用方法a. 用定義b. 對整數(shù)按被n除的余數(shù)分類討論c. 連續(xù)n個整數(shù)的積一定是n的倍數(shù)d. 因式分解an-bn=(a-b)M1,an+bn=(a+b)M2, 2 ne. 用數(shù)學歸納法f. 要證明a|b，只要證明對任意素數(shù)p，a中p的冪指數(shù)不超過b中p的冪指數(shù)即可，用p(a)表示a中p的冪指數(shù)，則a|bp(a)p(b)例題選講例1.請寫出10個連續(xù)正整數(shù)都是合數(shù).解: 11!+2，11!+3，11！+11。例2. 證明連續(xù)三個整數(shù)中，必有一個被3整除。證：設三個連續(xù)正數(shù)為a，a+1，a+2，而a只有3k，3k+1，3k+2三種情況，令a=3k，顯然成立，a=3k+1時，a+2=3(

13、k+1)，a=3k+2時，a+1=3(k+1)。例3. 證明lg2是無理數(shù)。證：假設lg2是有理數(shù)，則存在二個正整數(shù)p，q，使得lg2=，由對數(shù)定義可得10=2，則有25 =2,則同一個數(shù)左邊含因子5，右邊不含因子5，與算術(shù)基本定理矛盾。lg2為無理數(shù)。例4. 求(21n+4，14n+3)解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1例5. 求2004!末尾零的個數(shù)。解：因為10=25，而2比5多，所以只要考慮2004！中5的冪指數(shù)，即5（2004?。?例6.證明（n!）(n-1)!|(n!)!證：對任意素數(shù)p,設（n!）(n-1)

14、!中素數(shù)p的指數(shù)為，（n!）!中p的指數(shù)，則，,即，即左邊整除右邊。例7. 證明2003|（20022002+20042004-2005）證： 20022002=（2003-1）2002=2003M1+120042004=（2003+1）2002=2003M2+120022002+20042004-2005=2003（M1+M2-1）由定義2003|（20022002+20042004-2005）例8. 設d(n)為n的正因子的個數(shù)， (n)為n的所有正因子之和，求d(1000)， (1000)。解： 1000=2353 d(1000)=(3+1)(3+1)=16， (1000)=例9. 設c

15、不能被素數(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) , a|b例10. 若Mn為素數(shù)，則n一定為素數(shù)。證：若n為合數(shù)，則設n=ab，（1a,bm，則Fn-2=（）（）=(Fn-1-2) （）= Fn-1Fn-2Fm- F0設（Fn,Fm）=d,則d|Fn, d|Fmd|2但Fn為奇數(shù)，d=1, 即證。例12. 設m,n是正整數(shù)。證明證 : 不妨設。由帶余數(shù)除法得 我們有由此及得,=注意到,若,則,結(jié)論成立.若,則繼續(xù)對作同樣的討論，由輾轉(zhuǎn)相除法知，結(jié)論成立。顯見，2用任一大于1的

16、自然a代替，結(jié)論都成立。例13. 證明：對任意的正整數(shù)，成立如下不等式。其中是數(shù)的以10為底的對數(shù)，是的不同的素因數(shù)（正的）的個數(shù)。證：設是大于1的整數(shù)（如果=1，上述不等式顯然成立，因=0）， 是的個相異的素因素。的素因數(shù)分解式為.() , 由于，從而，而，故。將上述不等式取對數(shù)（設底）,則有。特別有。例14. 試證明任意一個整數(shù)與它的數(shù)字和的差必能被9整除，并且它與它的數(shù)字作任意調(diào)后換后所成整數(shù)的差也能被9整除。證： 設整數(shù)m的個位、十位、百位的數(shù)字分別為,，則可表作： 所以因為，,，都是整數(shù)，所以任一整數(shù)與其數(shù)字之和的差必能被9整除。再設將,，按任一種順序排成,，并令，。根據(jù)前面證明的結(jié)

17、果，知存在整數(shù)A，B，使因為，所以。由于A-B是整數(shù)，這就證明了能被9整除。注：若對某個整數(shù)，有，但當時，則此時為整數(shù)：即。如前證，此時結(jié)論正確。又當為負整數(shù)及零時，結(jié)論顯然正確。 第二章 不定方程一、 主要內(nèi)容一次不定方程有解的條件、解數(shù)、解法、通解表示，不定方程x2+y2=z2通解公式、無窮遞降法、費爾馬大定理。二、 基本要求1、 了解不定方程的概念，理解對“解”的認識，掌握一次不定方程有解的條件，能熟練求解一次不定方程的特解，正整數(shù)解及通解。了解多元一次不定方程有解的條件，在有解的條件下的解法。2、掌握不定方程x2+y2=z2在一定條件下的通解公式，并運用這個通解公式作簡單的應用。3、對

18、費爾馬大定理應有在常識性的了解，掌握無窮遞降法求證不定方程x4+y4=z2無解的方法。4、掌握證明不定方程無解的若干方法。三、難點和重點（1）重點為求解一次不定方程的方法（2）掌握第二節(jié)中引證的應用。（1） 費爾馬無窮遞降法。四、自學指導不定方程主要講解以下幾個問題（i）給定一類不定方程，判別在什么條件下有解。（ii）在有解的條件下，有多少解（iii）在有解的條件下，求出所給的不定方程的所有解。 二元一次不定方程的一般形式為ax+by=c 。若(a ,b)c，則該二元一次不定方程一定有解，若已知一個特解，則一切解可以用公式表示出來，因此求它的通解只要求出一個特解即可。求解二元一次不定方程的一個

19、通解有好多種方法。讀者應該總結(jié)一下，各種方法都有獨到之處。特別要指出用最大公因數(shù)的方法。它的根據(jù)是求（a ,b）時所得的結(jié)果。由于注意通解公式x=x0-b1t，y=y0+a1t中a1，b1的意義和位置。以免出錯。多元一次不定方程也有類似的結(jié)果，但在求解的過程中將它轉(zhuǎn)化二元一次不定方程組，從最后一個二元一次不定方程解起，可逐一解出x1 ,x2 ,xn 。所用的方法一般選擇最大公因數(shù)的方法。由于n元一次不定方程可轉(zhuǎn)化為n-1個二元一次不定方程組，故在通解中依賴于n-1個任意常數(shù)。但不象二元一次不定方程那樣有公式來表示。x2+y2=z2的正整數(shù)解稱為勾股數(shù)，在考慮這個方程時，我們對（x ,y）作了一

20、些限制，而這些限制并不影響其一般性。在條件x0，y0，z0，（x，y）=1，2x的條件可以給出x2+y2=z2的通解公式，x=2ab，y=a2-b2，z2=a2+b2，ab0 , (a ,b)=1，a ,b一奇一偶。若將2x限為2y，則也有相應的一個通解公式。在證明這個通解公式的過程中，用到了引理 uv=w2，u0，v0，（u ,v）=1，則u=a2，v=b2，w=ab 。a0，b0，（a ,b）=1 。利用這個結(jié)論可以求解某些不定方程。特別當w=1或素數(shù)p 。則由uv=1或uv=P 可將原不定方程轉(zhuǎn)化為不定方程組。從而獲得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望讀者能掌握這種

21、方法。 為了解決著名的費爾馬大定理：xn+yn=zn ，n3無正整數(shù)解時，當n=4時可以用較初等的方法給出證明。證明由費爾馬本人給出的，一般稱為費爾馬無窮遞降法。其基本思想為由一組解出發(fā)通過構(gòu)造得出另一組解，使得兩組解之間有某種特定的關(guān)系，而且這種構(gòu)造可以無限重復的。從而可得到矛盾。因此無窮遞降法常用來證明某些不定方程無整數(shù)解。證明一類不定方程無解是研究不定方程鄰域中常見的形式，一般的要求解不定方程比證明不定方程無解要容易些。證明不定方程無解的證明方法常采用以下形式：（反證法）若A有解A1有解A2有解An有解，而An本身無解，這樣來構(gòu)造矛盾。從而說明原不定方程無解。對于證明不定方程的無解性通常

22、在幾種方法，一般是總的幾種方法交替使用。特別要求掌握：簡單同余法、因子分解法、不等式法，以及中學數(shù)學中所涉及的判別式法。五、例子選講例1：利用整數(shù)分離系數(shù)法求得不定方程15x+10y+6z=61。解：注意到z的系數(shù)最小，把原方程化為z=令t1=，即-3x+2y-6t1+1=0此時y系數(shù)最小，令t2 =,即,反推依次可解得y=x+3t1+t2=2t2+1+3t1+t2=1+3t1+3t2z=-2x-2y+10+t1=6-5t1+10t2原不定方程解為t1t2z.例2:證明是無理數(shù)證：假設是有理數(shù)，則存在自數(shù)數(shù)a,b使得滿足即，容易知道a是偶數(shù)，設a=2a1，代入得,又得到b為偶數(shù)，設，則,這里這

23、樣可以進一步求得a2，b2且有aba1b1 a2b2但是自然數(shù)無窮遞降是不可能的，于是產(chǎn)生了矛盾，為無理數(shù)。例3：證明：整數(shù)勾股形的勾股中至少一個是3的倍數(shù)。證：設N=3m1(m為整數(shù)) ， N2=9m26m+1=3(3m22m)+1即一個整數(shù)若不是3的倍數(shù)，則其平方為3k+1,或者說3k+2不可能是平方數(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奇偶性相同，即xy為偶數(shù)，設x+y=2u, x-y=2v，代入原方程即為u2+v2=

24、164,同理令u+v=2u1,u-v=2v1有為一偶一奇，且0u22，則2P-1的質(zhì)因數(shù)一定是2pk+1形。證：設q是2-1的質(zhì)因數(shù)，由于2-1為奇數(shù)， q2， （2q）=1,由條件q|2p-1,即21（mod q），又 （q,2）=1，21（mod q）設i是使得21（mod p）成立最小正整數(shù)若1ip，則有i|p則與p為素數(shù)矛盾 i=p, p|q-1又 q-1為偶數(shù)，2|q-1, 2p|q-1,q-1=2pk , 即q=2pk+1例4：證明13|42n+1+3n+2證：42n+1+3n+2416n+93n 3n (4+9)133n0(13) 13|42n+1+3n+2例5：證明5y+3=x

25、2無解證明：若5y+3=x2有解，則兩邊關(guān)于模5同余有5y+3x2(mod 5)即3x2(mod 5)而任一個平方數(shù)x20,1,4(mod 5) 30,1,4(mod 5) 即得矛盾，即5y+3=x2無解例6：求被7除的余數(shù)。解：111111被7整除，11（mod 7）4（mod 7），即余數(shù)為4。例7：把化為分數(shù)。解：設b=，從而1000b=,100000b=，99000b=4263-42b=。當然也可用直化分數(shù)的方法做。例8：設一個數(shù)為62XY427是9，11的倍數(shù)，求X，Y解：因為9|62XY427所以9|6+2+X+Y+4+2+7， 即9|21+X+Y又因為11|62XY427， 有1

26、1 |（7+4+X+6-2-Y-2）即11|（X-Y+13）因為0X，Y9， 所以有21 21+X+Y39，4 X-Y+13 22，由此可知21+X+Y=27，X-Y+13=11或21+X+Y=36，X-Y+13=22X+Y=6，X-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，有因而每一個整數(shù)對于模8，必同余于0，1，4這三個數(shù)不能如何變化，只能有而，故不同余于關(guān)于模8，從而證明了結(jié)論。 第四章 同余式一、 主要內(nèi)容 同余方程概念及次數(shù)、解的定義

27、，一次同余方程axb(mod m)有解的充分必要條件，一次同余方程組，孫子定理，高次同余方程，素數(shù)模的同余方程，威爾遜定理。二、基本要求通過本章的學習要求掌握同余方程的一些基本概念，例同余方程的次數(shù)、解等，能解一次同余方程，一次同余方程組，理解孫子定理并用它來解一次同余方程組，會解高次同余方程，對于以素數(shù)模的同余方程的一般理論知識能理解。三、重點和難點（1） 孫子定理的內(nèi)容與證明，從中學會求出一次同余方程組的解并從中引伸更一般的情形，即模不二二互素的情形。（2） 素數(shù)模的同余方程的一些基本理論性問題，并能與一般方程所類似的性質(zhì)作比較。四、自學指導同余方程和不定方程一樣，我們同樣要考慮以下三個問

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

29、須（k ,m）=1，這一點和同余的性質(zhì)有區(qū)別。一次同余方程的一般形式為axb(mod m)，我們討論的所有內(nèi)容都在這標準形式下進行的?？偨Y(jié)一次同余方程與二元一次不定方程有相當?shù)穆?lián)系，一次同余方程的求解可以由二元一次不定方程的求解方式給出。反之亦然。但要注意在對“解”的認識上是不一致的，從而導致有無窮組解和有限個解的區(qū)別。為了求axb(mod m)的一個特解，可在條件(a ,m)=1下進行。教材上有若干種求解方式，供讀者在同樣問題選擇使用。一次同余方程組的標準形式為xb1(mod m1)xb2(mod m2) (1)xbn(mod mn)若給出的同余方程組不是標準形式，必須注意化為標準形式，同時

30、我們得到的有解的判別定理及求法方法都是這一標準形式得到的。同余方程組（1）有解的條件(mi ,mj) bi-bj ，1i，jk 。在使用時一定要對所有可解進行驗算，進行有解的判別求解一次同余方程組（1）有兩種方法：待定系數(shù)法和孫子定理。二種方法各有特長。待定系數(shù)法適應的范圍較廣，對模沒有什么要求。孫子定理有一個具體的公式，形式也較漂亮。但對模要求是二二互素。孫子定理為下面定理：（孫子定理）兩兩互素，則一次同余式組 的解為 其中對待定系數(shù)法和孫子定理要有深刻的理解。體會其實質(zhì)，這樣不必死記硬背。次數(shù)大于1的同余方程稱為高次同余方程，一般地高次同等方程可轉(zhuǎn)化一系列的高次同余方程組。然后將每一個高次

31、同余方程的解都求出，最后利用孫子定理也可求出原同余方程的解。求高次同余方程解的基本方法有兩條，一是小模，二是降次。設m=；則要求f(x) 0(mod m)的解只要求f(x) 0(mod p) (2)的解即可，其中p為素數(shù)。1 。對于（2）的解的求法我們用待定系數(shù)法。 設f(x) 0(mod p)的解為xx1(mod p)為解。則當p f(x)時， f(x) 0(mod p)的一個解x1可求出f(x) 0(mod p2)的一個解。方法如下：將x=x1+pt1代入 f(x) 0(mod p2)有f(x1+pt1) 0(mod p2)f(x1)+pt1f(x1) 0(mod p2)+ 0(mod p

32、) t1=t1+ p t2代入 x=x1+pt1=x1+p(t1+t2p2)=x2+ p2t2則 xx2(mod p2)即為f(x) 0(mod p)的解。然后重復上述過程，即可由x2得f(x) 0(mod p)的解 x3 。最后求出f(x) 0(mod p)的解從上所述，關(guān)鍵是求素數(shù)模的同余方程f(x) 0(mod p)的解。f(x) 0(mod p)的性質(zhì)（1）同余方程的解與f(x)的分解之間的關(guān)系，這一點和代數(shù)方程幾乎一樣。注意素數(shù)p的條件必不可少。（2）同余方程的解數(shù)與次數(shù)之間有關(guān)系 解數(shù)次數(shù)。這一點和代數(shù)方程也一樣。此時，素數(shù)p的條件也必不可少本節(jié)的輔產(chǎn)品是著名的wilsom定理。P

33、為素數(shù)，則有(p-1)！-1(mod p)，實際上wilsom定理的逆定理也成立。故wilsom定理可以作為素數(shù)成立主要條件。五、例子選講補充知識定義1：當（a，m）=1時，若ab，則記b，稱為形式分數(shù)。根據(jù)定義和記號，則，則有下列性質(zhì)1、2、若（d，m）=1，且利用形式分數(shù)的性質(zhì)把分母變成1，從而一次同余式的解。例1：解一次同余式解：（17，25）=1，原同余方程有解，利用形式分數(shù)的性質(zhì)，同余方程解為 例2：解同余方程組解：（12，10）|6+2，（12，15）|-2-1，（10，15）|6-1 原同余方程有解，且等位于 此時變成模兩兩互素由孫子定理可求得其解為：例3：解一次同余式組解: 用

34、常規(guī)方法先求每一個一次同余式的解，得到下列一次同余式組然后用孫子定理求解，所以同余方程組有3個解，且解分別為，例4：設2p+1是素數(shù)，則 證：設n=2p+1,由假設n為素數(shù)，于是由威爾遜定理有(n-1)! -1(mod n)由于(n-1)!+1(n-1)(n-2)(p+2)(p+1)p(p-1)321+11(n-1)2(n-2)2(n-3)(p-1)n-(p-1)p(n-p)+1p!(n-1)(n-2)(n-p)+1(p!)2(-1)p+1(mod n) (p!)2(-1)p +10(mod n) (p!)2+(-1)p0(mod 2p+1)例5：解同余方程28x21(mod 35)解： （2

35、8,35）=7|21， 原同余方程有解，且有7個解原同余方程等價于4x3(mod 5)而且4x3(mod 5)解為x2(mod 5) 原同余方程解為2，7，12，17，22，27，31（mod 35） 第五章 二次剩余理論一、 主要內(nèi)容平方剩余與平方非剩余的概念、歐拉判別條件、勒讓德符號、二次互反律、雅可比符號、素數(shù)模同余方程的解法二、基本要求通過本章的學習，掌握平方剩余與平方非剩余的概念，掌握勒讓德符號的定義、性質(zhì)計算及利用它來判別一個二次同余方程是否有解，對于幾個較特殊的勒讓德符號的值，要求能掌握它的推導方法。了解推可比符號的定義，性質(zhì)及功能，會解素數(shù)的模的二次同余方程。及證明一些二次不定

36、方程無解中的應用。三、重點和難點（1）歐拉判別定理：即a為p的平方剩余的條件。（2）勒讓德符號，二次互反律。（3）素數(shù)模同余方程的解法。 四、自學指導對于一般的高次同余方程的求解歸納為模為p的情形。對于同余方程f(x)0(mod p)的求解依賴于f(x) o(mod p)的解。而且對于一般的f(x)，求解f(x) 0(mod p)的解是很困難的。本章討論f(x)為一個整系數(shù)的二次三項式時情形?？傻玫蕉瓮嗍降臉藴市问絰2 a(mod p) (a ,p)=1 p為奇素數(shù)。 （1）以下內(nèi)容都是在標準形式下得到的。其中p為奇素數(shù)。平方剩余和平方非剩余是以同余方程（1）是否有解來定義的。因此平方剩余

37、和平方非剩余只要在模p的一個簡化剩余系中找即可。實際上，模m的全體平方剩余和全體平方非剩余構(gòu)成了模p的一個簡化剩余系。因為平方剩余和平方非剩余各占一半，且平方剩余與下列數(shù)列12，22，同余。這為我們提供了計算模p的平方剩余的方法，另一個為歐拉判別定理a 1(mod p)，這個定理的證明依賴于高次同余方程的素數(shù)模p，次數(shù)等于解數(shù)的條件，再結(jié)合歐拉定理即可得到，但缺點是計算量比較大。為了彌補計算量大的不足，引進了勒讓德符號，根據(jù)定義可得到一系列性質(zhì)，其中=1或=1的p及=-1，=-1的p的值需要記憶，即有1、 p=4K+1時，-1是p的平方剩余，p=4K+3時，-1是p的平方非剩余。2、 p=8K

38、+1或8K-1時，2是p的平方剩余，p=8K+3或8K-3時，2是p的平方非剩余。3、 對一些較小的素數(shù)其平方剩余和平方非剩余列表如下：P 平方剩余 平方非剩余3 1 25 1，4 2，37 1，2，4 3，5，611 1，3，4，5，9 2，6，7，8，1013 1，3，4，12，9，10 2，5，6，7，8，11其余性質(zhì)要理解，特別是二次互反律的條件為p，g為二個不同的奇素數(shù)。勒讓德符號計算的最大困難對a要進行素因數(shù)分解，往往很煩，也很困難。為了彌補這個困難，再引進雅可比符號，由雅可比符號的定義出發(fā)可建立形式上和勒讓德符號完全一致的性質(zhì)。由于雅可比符號是勒讓德符號的推廣，因此雅可比符號在這

39、里的主要功能是為了計算勒讓德符號的值。本章主要解決以下三個問題1、已知素數(shù)p判別同余方程x2a(mod p)是否有解。即計算=1或-1 。2、已知a，求所有使及=1或=-1的p的一般形式。3、在=1的條件下，如何求出x2a(mod p)的解。若x1為一個解，則另一個解為-x1 。上述已敘述了問題（1）、（2），現(xiàn)在只剩下解（3）解的方法。除了書上介紹的公方法，我們再補充另一個方法即高斯逐步淘汰法。五、例子選講補充知識高斯逐步淘汰法：首先，不妨設0ap是0x，故x2，因解同余方程x2a(mod p)（1）相當于不定方程x2=a+py，故0y= ，因而在求y的值時，不必考慮大于的整數(shù)，這就大大縮小

40、了討論的范圍。其次，任取素數(shù)qp，求出q的平方非剩余為a1 ,a2as并以v1 ,v2,vs表示同余方程a+pya1 (mod q) ,a+pya2(mod q)，a+pyas(mod q)的解，由于平方數(shù)一定為任何模的平方剩余，故若取yvi(mod q)，則a+py是q的平方非剩余，因而a+py一定不是平方數(shù)。而不能有x2=a+py這樣可淘汰滿足yvi(mod g)的各個y的值。取不同的q，淘汰y的值，直至留下的數(shù)較少是計算不太麻煩時，即可直接代入并求出（1）的解。例：解同余方程x273(mod137)解 =1，x273(mod137)有二個解因為p=137，故03，p只能為p1(mod 3

41、)且 只能下列情況 或例3：證明形如4m+1的素數(shù)有無窮多個。證：假設形如4m+1的素數(shù)只有有限個，設為p1pk，顯然(2p1pk)2+1的最小素因數(shù)p是奇數(shù)，且p與p1pk不同，設p為4m+3形的素數(shù)，但p整除(2p1pk)2+1，表明(2p1pk)2+10（mod p）即x2(-1)(mod p)有解，即，但矛盾，p為4m+1形，這與4m+1的素數(shù)只有k個矛盾。例4：證明不定方程x2+23y=17無解。證：只要證x217(mod 23)無解即可， 171(mod 4) x217(mod 23)無解，即原方程無解。例5設x為整數(shù)，證明形如的整數(shù)的所有奇因數(shù)都有4h+1的形式，（其中h為整數(shù)）

42、證：設2n+1是整數(shù)的任一奇素因數(shù)，于是有即可以證明，這時，否則有，這是不可能的。因此，由是奇素數(shù)，便有。從而，這樣由費馬定理，有。但是因此有由此可知，n必為偶數(shù)，記n=2h,便有2n+1=4h+1.這樣便證明了整數(shù)的的所有奇素因數(shù)形式必為4h+1形式。又由于兩個4h+1形式的數(shù)的乘積仍為4h+1形式的數(shù)，故形式的數(shù)的奇因數(shù)必為4h+1形式的數(shù)。證2：由上面可知，-1是模2n+1的平方剩余，即 其中2n+1是奇素數(shù)。由定理3知從而 ，故，所以n是偶數(shù)，其余同上。例6：證明：形如的素數(shù)有無窮多個。證：設N是任意正整數(shù)，是不超過N的一切形如的素數(shù)。記。顯然q的任意素因數(shù)a異于2，且是同余式的解。由.又由于是不是q的因數(shù)，故，從而。因此形如的素數(shù)有無窮多個。例7: 解如下二次同余式解： (1)125=53。先解。它的一個解是x=1。再解。令，則有.化簡得，得到,從而有，所以的一個解為,最后解。設。代入有，化簡得即它的一個解是.因此是同余式的一個解，所以由定理，的兩個解是，例8：判斷同余方程是否有解。解：286=2143，433是素數(shù)，(143，443)=1奇數(shù)143不是素數(shù)，但可用判定可比符號計算的生勒讓德符號 原方程有解。 第六章 原根與指標一、 主要內(nèi)容原根、指數(shù)的定義及基本性質(zhì)、原根存在的條件、指標及n次乘