初等數(shù)論總復(fù)習(xí)題及知識(shí)點(diǎn)總結(jié)(共39頁)

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

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

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

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

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

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

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

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

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

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

11、都圍繞著整除而展開，讀者應(yīng)對整除問題的解決方法作一簡單的小結(jié)。五、例子選講補(bǔ)充知識(shí)最小自然數(shù)原理：自然數(shù)的任意非空子集中一定存在最小自然數(shù)。抽屜原理：（1）設(shè)n是一個(gè)自然數(shù)，有n個(gè)盒子，n+1個(gè)物體，把n+1個(gè)物體放進(jìn)n個(gè)盒子，至少有一個(gè)盒子放了兩個(gè)或兩個(gè)以上物體；（2）km+1個(gè)元素，分成k組，至少有一組元素其個(gè)數(shù)大于或等于m+1；（3）無限個(gè)元素分成有限組，至少有一組其元素個(gè)數(shù)為無限。梅森數(shù)：形如2n-1的數(shù)叫梅森數(shù)，記成Mn=2n-1。費(fèi)爾馬數(shù)：n為非負(fù)整數(shù)，形如的數(shù)叫費(fèi)爾馬數(shù)，記成Fn=。設(shè)n=，設(shè)n的正因子個(gè)數(shù)為d(n)，所有正因子之和為，則有有關(guān)技巧1. 整數(shù)表示a=a0×

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

13、3k+2三種情況，令a=3k，顯然成立，a=3k+1時(shí)，a+2=3(k+1)，a=3k+2時(shí)，a+1=3(k+1)。例3. 證明lg2是無理數(shù)。證：假設(shè)lg2是有理數(shù)，則存在二個(gè)正整數(shù)p，q，使得lg2=，由對數(shù)定義可得10=2，則有2·5 =2,則同一個(gè)數(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!末尾零的個(gè)數(shù)。解：因?yàn)?0=2×5，而2比5多，所以只要考慮2004！中5的冪指數(shù)，即5（2

14、004！）=例6.證明（n!）(n-1)!|(n!)!證：對任意素?cái)?shù)p,設(shè)（n!）(n-1)!中素?cái)?shù)p的指數(shù)為，（n!）!中p的指數(shù)，則，,即，即左邊整除右邊。例7. 證明2003|（+-2005）證： =（2003-1）2002=2003M1+1=（2003+1）2002=2003M2+1+-2005=2003（M1+M2-1）由定義2003|（+-2005）例8. 設(shè)d(n)為n的正因子的個(gè)數(shù)， (n)為n的所有正因子之和，求d(1000)， (1000)。解： 1000=23·53 d(1000)=(3+1)(3+1)=16， (1000)=例9. 設(shè)c不能被素?cái)?shù)平方整除，若a

15、2|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為素?cái)?shù)，則n一定為素?cái)?shù)。證：若n為合數(shù)，則設(shè)n=ab，（1<a,b<n） 2ab-1=(2a)b-1=(2a-1)M為合數(shù)，與Mn為素?cái)?shù)矛盾， n為素?cái)?shù)。例11. 證明對任意m,n，mn, (Fn,Fm)=1。證：不妨設(shè)n>m，則Fn-2=（）（）=(Fn-1-2) （）= Fn-1Fn-2Fm- F0設(shè)（Fn,Fm）=d,則d|Fn, d|Fmd|2但Fn為奇數(shù)，d=1, 即證。例12. 設(shè)m,n是正整數(shù)。

16、證明證 : 不妨設(shè)。由帶余數(shù)除法得 我們有由此及得,=注意到,若,則,結(jié)論成立.若,則繼續(xù)對作同樣的討論，由輾轉(zhuǎn)相除法知，結(jié)論成立。顯見，2用任一大于1的自然a代替，結(jié)論都成立。例13. 證明：對任意的正整數(shù)，成立如下不等式。其中是數(shù)的以10為底的對數(shù)，是的不同的素因數(shù)（正的）的個(gè)數(shù)。證：設(shè)是大于1的整數(shù)（如果=1，上述不等式顯然成立，因=0）， 是的個(gè)相異的素因素。的素因數(shù)分解式為.() , 由于，從而，而，故。將上述不等式取對數(shù)（設(shè)底）,則有。特別有。例14. 試證明任意一個(gè)整數(shù)與它的數(shù)字和的差必能被9整除，并且它與它的數(shù)字作任意調(diào)后換后所成整數(shù)的差也能被9整除。證： 設(shè)整數(shù)m的個(gè)位、十位

17、、百位的數(shù)字分別為,，則可表作： 所以因?yàn)椋?，都是整數(shù)，所以任一整數(shù)與其數(shù)字之和的差必能被9整除。再設(shè)將,，按任一種順序排成,，并令，。根據(jù)前面證明的結(jié)果，知存在整數(shù)A，B，使因?yàn)椋?。由于A-B是整數(shù)，這就證明了能被9整除。注：若對某個(gè)整數(shù)，有，但當(dāng)時(shí)，則此時(shí)為整數(shù)：即。如前證，此時(shí)結(jié)論正確。又當(dāng)為負(fù)整數(shù)及零時(shí)，結(jié)論顯然正確。Ø 第二章 不定方程一、 主要內(nèi)容一次不定方程有解的條件、解數(shù)、解法、通解表示，不定方程x2+y2=z2通解公式、無窮遞降法、費(fèi)爾馬大定理。二、 基本要求1、 了解不定方程的概念，理解對“解”的認(rèn)識(shí)，掌握一次不定方程有解的條件，能熟練求解一次不定方程的特解

18、，正整數(shù)解及通解。了解多元一次不定方程有解的條件，在有解的條件下的解法。2、掌握不定方程x2+y2=z2在一定條件下的通解公式，并運(yùn)用這個(gè)通解公式作簡單的應(yīng)用。3、對費(fèi)爾馬大定理應(yīng)有在常識(shí)性的了解，掌握無窮遞降法求證不定方程x4+y4=z2無解的方法。4、掌握證明不定方程無解的若干方法。三、難點(diǎn)和重點(diǎn)（1）重點(diǎn)為求解一次不定方程的方法（2）掌握第二節(jié)中引證的應(yīng)用。（1） 費(fèi)爾馬無窮遞降法。四、自學(xué)指導(dǎo)不定方程主要講解以下幾個(gè)問題（i）給定一類不定方程，判別在什么條件下有解。（ii）在有解的條件下，有多少解（iii）在有解的條件下，求出所給的不定方程的所有解。 二元一次不定方程的一般形式為ax+

19、by=c 。若(a ,b)c，則該二元一次不定方程一定有解，若已知一個(gè)特解，則一切解可以用公式表示出來，因此求它的通解只要求出一個(gè)特解即可。求解二元一次不定方程的一個(gè)通解有好多種方法。讀者應(yīng)該總結(jié)一下，各種方法都有獨(dú)到之處。特別要指出用最大公因數(shù)的方法。它的根據(jù)是求（a ,b）時(shí)所得的結(jié)果。由于注意通解公式x=x0-b1t，y=y0+a1t中a1，b1的意義和位置。以免出錯(cuò)。多元一次不定方程也有類似的結(jié)果，但在求解的過程中將它轉(zhuǎn)化二元一次不定方程組，從最后一個(gè)二元一次不定方程解起，可逐一解出x1 ,x2 ,xn 。所用的方法一般選擇最大公因數(shù)的方法。由于n元一次不定方程可轉(zhuǎn)化為n-1個(gè)二元一次

20、不定方程組，故在通解中依賴于n-1個(gè)任意常數(shù)。但不象二元一次不定方程那樣有公式來表示。x2+y2=z2的正整數(shù)解稱為勾股數(shù)，在考慮這個(gè)方程時(shí)，我們對（x ,y）作了一些限制，而這些限制并不影響其一般性。在條件x>0，y>0，z>0，（x，y）=1，2x的條件可以給出x2+y2=z2的通解公式，x=2ab，y=a2-b2，z2=a2+b2，a>b>0 , (a ,b)=1，a ,b一奇一偶。若將2x限為2y，則也有相應(yīng)的一個(gè)通解公式。在證明這個(gè)通解公式的過程中，用到了引理 uv=w2，u>0，v>0，（u ,v）=1，則u=a2，v=b2，w=ab 。a

21、>0，b>0，（a ,b）=1 。利用這個(gè)結(jié)論可以求解某些不定方程。特別當(dāng)w=1或素?cái)?shù)p 。則由uv=1或uv=P 可將原不定方程轉(zhuǎn)化為不定方程組。從而獲得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望讀者能掌握這種方法。 為了解決著名的費(fèi)爾馬大定理：xn+yn=zn ，n3無正整數(shù)解時(shí)，當(dāng)n=4時(shí)可以用較初等的方法給出證明。證明由費(fèi)爾馬本人給出的，一般稱為費(fèi)爾馬無窮遞降法。其基本思想為由一組解出發(fā)通過構(gòu)造得出另一組解，使得兩組解之間有某種特定的關(guān)系，而且這種構(gòu)造可以無限重復(fù)的。從而可得到矛盾。因此無窮遞降法常用來證明某些不定方程無整數(shù)解。證明一類不定方程無解是研究不定方

22、程鄰域中常見的形式，一般的要求解不定方程比證明不定方程無解要容易些。證明不定方程無解的證明方法常采用以下形式：（反證法）若A有解A1有解A2有解An有解，而An本身無解，這樣來構(gòu)造矛盾。從而說明原不定方程無解。對于證明不定方程的無解性通常在幾種方法，一般是總的幾種方法交替使用。特別要求掌握：簡單同余法、因子分解法、不等式法，以及中學(xué)數(shù)學(xué)中所涉及的判別式法。五、例子選講例1：利用整數(shù)分離系數(shù)法求得不定方程15x+10y+6z=61。解：注意到z的系數(shù)最小，把原方程化為z=令t1=，即-3x+2y-6t1+1=0此時(shí)y系數(shù)最小，令t2 =,即,反推依次可解得y=x+3t1+t2=2t2+1+3t1

23、+t2=1+3t1+3t2z=-2x-2y+10+t1=6-5t1+10t2原不定方程解為t1t2z.例2:證明是無理數(shù)證：假設(shè)是有理數(shù)，則存在自數(shù)數(shù)a,b使得滿足即，容易知道a是偶數(shù)，設(shè)a=2a1，代入得,又得到b為偶數(shù)，設(shè)，則,這里這樣可以進(jìn)一步求得a2，b2且有a>b>a1>b1> a2>b2>但是自然數(shù)無窮遞降是不可能的，于是產(chǎn)生了矛盾，為無理數(shù)。例3：證明：整數(shù)勾股形的勾股中至少一個(gè)是3的倍數(shù)。證：設(shè)N=3m±1(m為整數(shù)) ， N2=9m2±6m+1=3(3m2±2m)+1即一個(gè)整數(shù)若不是3的倍數(shù)，則其平方為3k+1

24、,或者說3k+2不可能是平方數(shù)，設(shè)x,y為勾股整數(shù)，且x,y都不是3的倍數(shù)，則x2,y2都是3k+1，但z2=x2+y2=3k+2形，這是不可能，勾股數(shù)中至少有一個(gè)是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=2u1,u-v=2v1有為一偶一奇，且0<u2<6u2=1，2，3，4，5代方程，有解（4，5）（5，4）原方程解x=18,y=2,或x=2,y=18。例5：求x2+xy-6=0的正整數(shù)解。解：原方程等價(jià)于x(x+y)=2·

25、;3,故有 ， 即有x=2,y=1; x=1,y=5.例6：證明不定方程x2-2xy2+5z+3=0無整數(shù)解。解：若不定方程有解，則但y40，1(mod5), 對y,z ，y4-5z-32，3(mod5)而一個(gè)平方數(shù)0，1，4（mod 5） y4-5z-3不可能為完全平方，即不是整數(shù)，所以原不定方程無解。例7：證明：無整數(shù)解證：若原方程有解，則有注意到對于模8，有因而每一個(gè)整數(shù)對于模8，必同余于0，1，4這三個(gè)數(shù)。不論如何變化，只能有而，故不同余于關(guān)于模8，所以假設(shè)錯(cuò)誤，即，從而證明了原方程無解。例8:某人到銀行去兌換一張d元和c分的支票，出納員出錯(cuò)，給了他c元和d元，此人直到用去23分后才發(fā)

26、覺其錯(cuò)誤，此時(shí)他發(fā)現(xiàn)還有2d元和2c分，問該支票原為多少錢？解：由題意立式得：即令得令得所以為任意整數(shù)），代入得：（1）其中v是任意整數(shù)。又根據(jù)題意要求：.根據(jù)(1)，僅當(dāng)v=8時(shí)滿足此要求，從而因此該支票原為25元51分.Ø 第三章 同余一、 主要內(nèi)容同余的定義、性質(zhì)、剩余類和完全剩余系、歐拉函數(shù)、簡化剩余系、歐拉定理、費(fèi)爾馬小定理、循環(huán)小數(shù)、特殊數(shù)2，3，4，5，6，7，8，9，11，13的整除規(guī)律二、 基本要求通過本章的學(xué)習(xí)，能夠掌握同余的定義和性質(zhì)，區(qū)別符號(hào)：“三”和=”之間的差異。能利用同余的一些基本性質(zhì)進(jìn)行一些計(jì)算，深刻理解完全剩余系，簡化剩余系的定義、性質(zhì)及構(gòu)造。能判斷

27、一組數(shù)是否構(gòu)成模m的一個(gè)完全剩余系或一個(gè)簡化剩余系。能計(jì)算歐拉函數(shù)的值，掌握歐拉定理、費(fèi)爾馬小定理的內(nèi)容以及證明方法。能應(yīng)用這二個(gè)定理證明有關(guān)的整除問題和求余數(shù)問題。能進(jìn)行循環(huán)小數(shù)與分?jǐn)?shù)的互化。三、難點(diǎn)和重點(diǎn)（1）同余的概念及基本性質(zhì)（2）完全剩余系和簡化剩余系的構(gòu)造、判別（3）歐拉函數(shù)計(jì)算、歐拉定理、費(fèi)爾馬小定理的證明及應(yīng)用（4）循環(huán)小數(shù)與分?jǐn)?shù)的互化（5）特殊數(shù)的整除規(guī)律。四、自學(xué)指導(dǎo)同余理論是初等數(shù)論中最核心的內(nèi)容之一，由同余定義可知，若ab(mod m)，則a和b被m除后有相同的余數(shù)。這里m為正整數(shù)，一般要求m大于1，稱為模，同余這一思想本質(zhì)上是將整數(shù)按模m分類，然后討論每一個(gè)類中整數(shù)所

28、具有的共性及不同類之間的差異。第一章中用帶余除法定理將整數(shù)分類解決一些問題的方法只不過是同余理論中的一個(gè)特殊例子。從同余的定理上看，同余和整除實(shí)際上是同一回事，故同余還有二個(gè)等價(jià)的定義：用整除來定義即 ma-b 。用等號(hào)來定義a=b+mt 。值得注意a和b關(guān)于m同余是個(gè)相對概念。即它是相對于模m來講，二個(gè)整數(shù)a和b關(guān)于一個(gè)整數(shù)模m同余。則對于另一個(gè)整數(shù)模m，a和b未必會(huì)同余。從定義上看，同余和整除是同一個(gè)事情，但引進(jìn)了新的符號(hào)“三”后，無論從問題的敘述上，還是解決問題的方法上都有了顯著的變化，同時(shí)也帶來了一些新的知識(shí)和方法。在引進(jìn)了同余的代數(shù)性質(zhì)和自身性質(zhì)后，同余符號(hào)“三”和等號(hào)“=”相比，在

29、形式上有幾乎一致的性質(zhì)，這便于我們記憶。事實(shí)上在所有等號(hào)成立的運(yùn)算中，只有除法運(yùn)算是個(gè)例外，即除法的消去律不成立。為此對于同余的除法運(yùn)算我們有二種除法：（i）模不改變的除法，若akbk(mod m) ，(k,m)=1，則ab(mod m)(ii)模改變的除法, 若akbk(mod m) (k,m)=d,則ab這一點(diǎn)讀者要特別注意。完全剩余系和簡化剩余系是二個(gè)全新的概念，讀者只要搞清引成這些概念的過程。因?yàn)橥嚓P(guān)系是一個(gè)等價(jià)關(guān)系，利用等價(jià)關(guān)系可以進(jìn)行將全體整數(shù)進(jìn)行分類，弄清來朧去脈，對于更深刻理解其本質(zhì)是很有好處的。完全剩余系或簡化剩余系是一個(gè)以整數(shù)為元素的集合，在每個(gè)剩余類各取一個(gè)數(shù)組成的m個(gè)

30、不同數(shù)的集合，故一組完全剩余系包含m個(gè)整數(shù)，由于二個(gè)不同的剩余類中的數(shù)關(guān)于m兩兩不同余，故可得判別一組數(shù)是否為模m的一個(gè)完全剩余系的條件有二條為（1） 個(gè)數(shù)=m（2） 關(guān)于m兩兩不同余另外要能用已知完全剩余系構(gòu)造新的完全剩余系。即有定理設(shè)（a，m）=1，x為m的完全剩余系，則ax+b也是m的完全剩余系。當(dāng)時(shí)，能由的完全剩余系和的完全剩余系，構(gòu)造完全剩余系。為討論簡化剩余系，需要引進(jìn)歐拉函數(shù)(m)，歐拉函數(shù)(m)定義為不超過m且與m互素的正整數(shù)的個(gè)數(shù)，記為(m)，要掌握(m)的計(jì)算公式，了解它的性質(zhì)。這些性質(zhì)最主要的是當(dāng)（a ,b）=1時(shí)，(ab) = (a) (b)，和現(xiàn)在在剩余類中把與m互素

31、的集合分出來，從中可在各個(gè)集合中任取一個(gè)數(shù)即可構(gòu)造模m的一個(gè)簡化剩余系。另一方面，簡化剩余數(shù)也可從模m的一個(gè)完全剩余系中得到簡化剩余系，一組完全剩余系中與m互素的的數(shù)組成的(m)個(gè)不同數(shù)的集合稱為m簡化剩余系。同樣簡化剩余系也有一個(gè)判別條件。判別一組整數(shù)是否為模m的簡化剩余系的條件為（2） 個(gè)數(shù)=(m)（3） 關(guān)于m兩兩不同余（3） 每個(gè)數(shù)與m互素關(guān)于m的簡化剩余系也能用已知完全剩余系構(gòu)造新的簡化剩余系。設(shè)（a，m）=1，x為m的簡化剩余系，則ax也是m的簡化剩余系。當(dāng)時(shí)，能由的簡化剩余系和的簡化剩余系，構(gòu)造簡化剩余系。歐拉定理、費(fèi)爾馬小定理是同余理論非常重要的定理之一。要注意歐拉定理和費(fèi)爾馬

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

33、9整除的充要條件是它的各位數(shù)字之和能被9整除。4、 一個(gè)整數(shù)被5整除的充要條件是它的末位為0或5。5、 一個(gè)整數(shù)被4，25整除的充要條件是它的末二位能被4，25整除。6、 一個(gè)整數(shù)被8，125整除的充要條件是它的末三位能被8，125整除。7、 設(shè)，則7或11或13整除a的充要條件是7或11或13整除五、例子選講例1：求3406的末二位數(shù)。解： （3，100）=1，31（mod 100）(100)= (22·52)=40, 3401(mol 100) 3406=(340)10·36(32)2·32-19×9-17129(mod 100) 末二位數(shù)為29。例

34、2：證明（a+b）pap+bp(mod p)證：由費(fèi)爾馬小定理知對一切整數(shù)有：apa（p），bpb(P)，由同余性質(zhì)知有：ap+bpa+b(p)又由費(fèi)爾馬小定理有（a+b）pa+b (p)（a+b）pap+bp(p)例3：設(shè)素?cái)?shù)p>2，則2P-1的質(zhì)因數(shù)一定是2pk+1形。證：設(shè)q是2-1的質(zhì)因數(shù)，由于2-1為奇數(shù)， q2， （2·q）=1,由條件q|2p-1,即21（mod q），又 （q,2）=1，21（mod q）設(shè)i是使得21（mod p）成立最小正整數(shù)若1<i<p，則有i|p則與p為素?cái)?shù)矛盾 i=p, p|q-1又 q-1為偶數(shù)，2|q-1, 2p|q-1

35、,q-1=2pk , 即q=2pk+1例4：證明13|42n+1+3n+2證：42n+1+3n+24·16n+9·3n 3n (4+9)13×3n·0(13) 13|42n+1+3n+2例5：證明5y+3=x2無解證明：若5y+3=x2有解，則兩邊關(guān)于模5同余有5y+3x2(mod 5)即3x2(mod 5)而任一個(gè)平方數(shù)x20,1,4(mod 5) 30,1,4(mod 5) 即得矛盾，即5y+3=x2無解例6：求被7除的余數(shù)。解：被7整除，11（mod 7）4（mod 7），即余數(shù)為4。例7：把化為分?jǐn)?shù)。解：設(shè)b=，從而1000b=,b=，99000

36、b=4263-42b=。當(dāng)然也可用直化分?jǐn)?shù)的方法做。例8：設(shè)一個(gè)數(shù)為62XY427是9，11的倍數(shù)，求X，Y解：因?yàn)?|62XY427所以9|6+2+X+Y+4+2+7， 即9|21+X+Y又因?yàn)?1|62XY427， 有11 |（7+4+X+6-2-Y-2）即11|（X-Y+13）因?yàn)?X，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不可能是三個(gè)整數(shù)的平方和。證：由于每一個(gè)整數(shù)對于8，必同余于0，1

37、，2，3，4，5，6，7這八個(gè)數(shù)之一注意到對于模8，有因而每一個(gè)整數(shù)對于模8，必同余于0，1，4這三個(gè)數(shù)不能如何變化，只能有而，故不同余于關(guān)于模8，從而證明了結(jié)論。Ø 第四章 同余式一、 主要內(nèi)容 同余方程概念及次數(shù)、解的定義，一次同余方程axb(mod m)有解的充分必要條件，一次同余方程組，孫子定理，高次同余方程，素?cái)?shù)模的同余方程，威爾遜定理。二、基本要求通過本章的學(xué)習(xí)要求掌握同余方程的一些基本概念，例同余方程的次數(shù)、解等，能解一次同余方程，一次同余方程組，理解孫子定理并用它來解一次同余方程組，會(huì)解高次同余方程，對于以素?cái)?shù)模的同余方程的一般理論知識(shí)能理解。三、重點(diǎn)和難點(diǎn)（1） 孫

38、子定理的內(nèi)容與證明，從中學(xué)會(huì)求出一次同余方程組的解并從中引伸更一般的情形，即模不二二互素的情形。（2） 素?cái)?shù)模的同余方程的一些基本理論性問題，并能與一般方程所類似的性質(zhì)作比較。四、自學(xué)指導(dǎo)同余方程和不定方程一樣，我們同樣要考慮以下三個(gè)問題，即有解的條件，解數(shù)及如何求解，一般地說，對于一般的同余方程，由于僅有有限個(gè)解，只要把模m的一個(gè)完全剩余系一一代入驗(yàn)算總解組則所需的結(jié)果。因此上述三個(gè)問題已基本解決，只不過具體到某一個(gè)同余方程計(jì)算起來困難一點(diǎn)而異。但對于解數(shù)，傳統(tǒng)的結(jié)果不再成立。例如一個(gè)同余方程的解數(shù)可以大于其次數(shù)。讀者可以舉出反例來證明這一事實(shí)。要學(xué)好同余方程這一章。必須首先弄清同余方程的概

39、念，特別是同余方程解的概念，互相同余的解是同一個(gè)解。其次有使原同余方程和新的同余方程互相等價(jià)的若干變換。移項(xiàng)運(yùn)算是傳統(tǒng)的，同余方程兩邊也可以加上模的若干倍。相當(dāng)于同余方程兩邊加“零”。無論是乘上一數(shù)k或除去一個(gè)數(shù)k，為了保持其同解性，必須（k ,m）=1，這一點(diǎn)和同余的性質(zhì)有區(qū)別。一次同余方程的一般形式為axb(mod m)，我們討論的所有內(nèi)容都在這標(biāo)準(zhǔn)形式下進(jìn)行的?？偨Y(jié)一次同余方程與二元一次不定方程有相當(dāng)?shù)穆?lián)系，一次同余方程的求解可以由二元一次不定方程的求解方式給出。反之亦然。但要注意在對“解”的認(rèn)識(shí)上是不一致的，從而導(dǎo)致有無窮組解和有限個(gè)解的區(qū)別。為了求axb(mod m)的一個(gè)特解，可在

40、條件(a ,m)=1下進(jìn)行。教材上有若干種求解方式，供讀者在同樣問題選擇使用。一次同余方程組的標(biāo)準(zhǔn)形式為xb1(mod m1)xb2(mod m2) (1)xbn(mod mn)若給出的同余方程組不是標(biāo)準(zhǔn)形式，必須注意化為標(biāo)準(zhǔn)形式，同時(shí)我們得到的有解的判別定理及求法方法都是這一標(biāo)準(zhǔn)形式得到的。同余方程組（1）有解的條件(mi ,mj) bi-bj ，1i，jk 。在使用時(shí)一定要對所有可解進(jìn)行驗(yàn)算，進(jìn)行有解的判別求解一次同余方程組（1）有兩種方法：待定系數(shù)法和孫子定理。二種方法各有特長。待定系數(shù)法適應(yīng)的范圍較廣，對模沒有什么要求。孫子定理有一個(gè)具體的公式，形式也較漂亮。但對模要求是二二互素。孫子

41、定理為下面定理：（孫子定理）兩兩互素，則一次同余式組 的解為 其中對待定系數(shù)法和孫子定理要有深刻的理解。體會(huì)其實(shí)質(zhì)，這樣不必死記硬背。次數(shù)大于1的同余方程稱為高次同余方程，一般地高次同等方程可轉(zhuǎn)化一系列的高次同余方程組。然后將每一個(gè)高次同余方程的解都求出，最后利用孫子定理也可求出原同余方程的解。求高次同余方程解的基本方法有兩條，一是小模，二是降次。設(shè)m=；則要求f(x) 0(mod m)的解只要求f(x) 0(mod p) (2)的解即可，其中p為素?cái)?shù)。1 。對于（2）的解的求法我們用待定系數(shù)法。 設(shè)f(x) 0(mod p)的解為xx1(mod p)為解。則當(dāng)p f(x)時(shí)， f(x) 0(

42、mod p)的一個(gè)解x1可求出f(x) 0(mod p2)的一個(gè)解。方法如下：將x=x1+pt1代入 f(x) 0(mod p2)有f(x1+pt1) 0(mod p2)f(x1)+pt1f(x1) 0(mod p2)+ 0(mod p) t1=t1+ p t2代入 x=x1+pt1=x1+p(t1+t2p2)=x2+ p2t2則 xx2(mod p2)即為f(x) 0(mod p)的解。然后重復(fù)上述過程，即可由x2得f(x) 0(mod p)的解 x3 。最后求出f(x) 0(mod p)的解從上所述，關(guān)鍵是求素?cái)?shù)模的同余方程f(x) 0(mod p)的解。f(x) 0(mod p)的性質(zhì)（

43、1）同余方程的解與f(x)的分解之間的關(guān)系，這一點(diǎn)和代數(shù)方程幾乎一樣。注意素?cái)?shù)p的條件必不可少。（2）同余方程的解數(shù)與次數(shù)之間有關(guān)系 解數(shù)次數(shù)。這一點(diǎn)和代數(shù)方程也一樣。此時(shí)，素?cái)?shù)p的條件也必不可少本節(jié)的輔產(chǎn)品是著名的wilsom定理。P為素?cái)?shù)，則有(p-1)！-1(mod p)，實(shí)際上wilsom定理的逆定理也成立。故wilsom定理可以作為素?cái)?shù)成立主要條件。五、例子選講補(bǔ)充知識(shí)定義1：當(dāng)（a，m）=1時(shí)，若ab，則記b，稱為形式分?jǐn)?shù)。根據(jù)定義和記號(hào)，則，則有下列性質(zhì)1、2、若（d，m）=1，且利用形式分?jǐn)?shù)的性質(zhì)把分母變成1，從而一次同余式的解。例1：解一次同余式解：（17，25）=1，原同余

44、方程有解，利用形式分?jǐn)?shù)的性質(zhì)，同余方程解為 例2：解同余方程組解：（12，10）|6+2，（12，15）|-2-1，（10，15）|6-1 原同余方程有解，且等位于 此時(shí)變成模兩兩互素由孫子定理可求得其解為：例3：解一次同余式組解: 用常規(guī)方法先求每一個(gè)一次同余式的解，得到下列一次同余式組然后用孫子定理求解，所以同余方程組有3個(gè)解，且解分別為，例4：設(shè)2p+1是素?cái)?shù)，則 證：設(shè)n=2p+1,由假設(shè)n為素?cái)?shù)，于是由威爾遜定理有(n-1)! -1(mod n)由于(n-1)!+1(n-1)(n-2)(p+2)(p+1)p(p-1)3·2·1+11·(n-1)·

45、;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)解： （28,35）=7|21， 原同余方程有解，且有7個(gè)解原同余方程等價(jià)于4x3(mod 5)而且4x3(mod 5)解為x2(mod 5) 原同余方程解為2，7，12，17，22，27，31（mod 35）Ø 第五章 二次剩余理論一、 主要內(nèi)容平方剩余與平方非剩余

46、的概念、歐拉判別條件、勒讓德符號(hào)、二次互反律、雅可比符號(hào)、素?cái)?shù)模同余方程的解法二、基本要求通過本章的學(xué)習(xí)，掌握平方剩余與平方非剩余的概念，掌握勒讓德符號(hào)的定義、性質(zhì)計(jì)算及利用它來判別一個(gè)二次同余方程是否有解，對于幾個(gè)較特殊的勒讓德符號(hào)的值，要求能掌握它的推導(dǎo)方法。了解推可比符號(hào)的定義，性質(zhì)及功能，會(huì)解素?cái)?shù)的模的二次同余方程。及證明一些二次不定方程無解中的應(yīng)用。三、重點(diǎn)和難點(diǎn)（1）歐拉判別定理：即a為p的平方剩余的條件。（2）勒讓德符號(hào)，二次互反律。（3）素?cái)?shù)模同余方程的解法。 四、自學(xué)指導(dǎo)對于一般的高次同余方程的求解歸納為模為p的情形。對于同余方程f(x)0(mod p)的求解依賴于f(x)

47、o(mod p)的解。而且對于一般的f(x)，求解f(x) 0(mod p)的解是很困難的。本章討論f(x)為一個(gè)整系數(shù)的二次三項(xiàng)式時(shí)情形?？傻玫蕉瓮嗍降臉?biāo)準(zhǔn)形式x2 a(mod p) (a ,p)=1 p為奇素?cái)?shù)。 （1）以下內(nèi)容都是在標(biāo)準(zhǔn)形式下得到的。其中p為奇素?cái)?shù)。平方剩余和平方非剩余是以同余方程（1）是否有解來定義的。因此平方剩余和平方非剩余只要在模p的一個(gè)簡化剩余系中找即可。實(shí)際上，模m的全體平方剩余和全體平方非剩余構(gòu)成了模p的一個(gè)簡化剩余系。因?yàn)槠椒绞Ｓ嗪推椒椒鞘Ｓ喔髡家话?，且平方剩余與下列數(shù)列12，22，同余。這為我們提供了計(jì)算模p的平方剩余的方法，另一個(gè)為歐拉判別定理a 1

48、(mod p)，這個(gè)定理的證明依賴于高次同余方程的素?cái)?shù)模p，次數(shù)等于解數(shù)的條件，再結(jié)合歐拉定理即可得到，但缺點(diǎn)是計(jì)算量比較大。為了彌補(bǔ)計(jì)算量大的不足，引進(jìn)了勒讓德符號(hào)，根據(jù)定義可得到一系列性質(zhì)，其中=1或=1的p及=-1，=-1的p的值需要記憶，即有1、 p=4K+1時(shí)，-1是p的平方剩余，p=4K+3時(shí)，-1是p的平方非剩余。2、 p=8K+1或8K-1時(shí)，2是p的平方剩余，p=8K+3或8K-3時(shí)，2是p的平方非剩余。3、 對一些較小的素?cái)?shù)其平方剩余和平方非剩余列表如下：P 平方剩余 平方非剩余3 1 25 1，4 2，37 1，2，4 3，5，611 1，3，4，5，9 2，6，7，8，

49、1013 1，3，4，12，9，10 2，5，6，7，8，11其余性質(zhì)要理解，特別是二次互反律的條件為p，g為二個(gè)不同的奇素?cái)?shù)。勒讓德符號(hào)計(jì)算的最大困難對a要進(jìn)行素因數(shù)分解，往往很煩，也很困難。為了彌補(bǔ)這個(gè)困難，再引進(jìn)雅可比符號(hào)，由雅可比符號(hào)的定義出發(fā)可建立形式上和勒讓德符號(hào)完全一致的性質(zhì)。由于雅可比符號(hào)是勒讓德符號(hào)的推廣，因此雅可比符號(hào)在這里的主要功能是為了計(jì)算勒讓德符號(hào)的值。本章主要解決以下三個(gè)問題1、已知素?cái)?shù)p判別同余方程x2a(mod p)是否有解。即計(jì)算=1或-1 。2、已知a，求所有使及=1或=-1的p的一般形式。3、在=1的條件下，如何求出x2a(mod p)的解。若x1為一個(gè)解

50、，則另一個(gè)解為-x1 。上述已敘述了問題（1）、（2），現(xiàn)在只剩下解（3）解的方法。除了書上介紹的公方法，我們再補(bǔ)充另一個(gè)方法即高斯逐步淘汰法。五、例子選講補(bǔ)充知識(shí)高斯逐步淘汰法：首先，不妨設(shè)0<a<p是0<x<，故x2<，因解同余方程x2a(mod p)（1）相當(dāng)于不定方程x2=a+py，故0<y= ，因而在求y的值時(shí)，不必考慮大于的整數(shù)，這就大大縮小了討論的范圍。其次，任取素?cái)?shù)qp，求出q的平方非剩余為a1 ,a2as并以v1 ,v2,vs表示同余方程a+pya1 (mod q) ,a+pya2(mod q)，a+pyas(mod q)的解，由于平方數(shù)一

51、定為任何模的平方剩余，故若取yvi(mod q)，則a+py是q的平方非剩余，因而a+py一定不是平方數(shù)。而不能有x2=a+py這樣可淘汰滿足yvi(mod g)的各個(gè)y的值。取不同的q，淘汰y的值，直至留下的數(shù)較少是計(jì)算不太麻煩時(shí)，即可直接代入并求出（1）的解。例：解同余方程x273(mod137)解 =1，x273(mod137)有二個(gè)解因?yàn)閜=137，故0<y34取q=3，則2為3一平方非剩余。解同余方程73+137y3(mod3) 得y2(mod 3)，從不大于34的正整數(shù)中淘汰形如y=2+3t的數(shù)，即有下面1，3，4，6，7，9，10，12，13，15，16，18，19，21，

52、22，24，25，27，28，30，31，33，34。再取q=5，2，3為g的平方非剩余的同余方程73+137y2(mod5) ，73+137y3(mod5)解為y2(mod5) ,y0(mod5)，再從前面的數(shù)中淘汰形如y=2+5t和y=5t，有下面1，3，4，6，9，13，16，18，19，21，24，28，31，33，34。又取q=7，3，5，6為g的三個(gè)平方非剩余的同余方程73+137y3,5,6(mod7)的y0,4,6(mod7)淘汰y=4+7t,7t,6+7t,就只留下了1,3,9,16,19,24,31,33 。將上述數(shù)代入137y+73=x2及137×3+73=48

53、4=222故x±22(mod137)為本題同余方程的解。例1：設(shè)p=4n+3是素?cái)?shù)，試證當(dāng)q=2p+1也是素?cái)?shù)時(shí)，梅素?cái)?shù)Mp不是素?cái)?shù)。證： q=8n+7, q|24n+3-1，即q |Mp， Mp不是素?cái)?shù)。例2：若3是素?cái)?shù)p平方剩余，問p是什么形式的素?cái)?shù)？解： 由反轉(zhuǎn)定律，注意到p>3，p只能為p1(mod 3)且 只能下列情況 或例3：證明形如4m+1的素?cái)?shù)有無窮多個(gè)。證：假設(shè)形如4m+1的素?cái)?shù)只有有限個(gè)，設(shè)為p1pk，顯然(2p1pk)2+1的最小素因數(shù)p是奇數(shù)，且p與p1pk不同，設(shè)p為4m+3形的素?cái)?shù)，但p整除(2p1pk)2+1，表明(2p1pk)2+10（mod p

54、）即x2(-1)(mod p)有解，即，但矛盾，p為4m+1形，這與4m+1的素?cái)?shù)只有k個(gè)矛盾。例4：證明不定方程x2+23y=17無解。證：只要證x217(mod 23)無解即可， 171(mod 4) x217(mod 23)無解，即原方程無解。例5設(shè)x為整數(shù)，證明形如的整數(shù)的所有奇因數(shù)都有4h+1的形式，（其中h為整數(shù)）證：設(shè)2n+1是整數(shù)的任一奇素因數(shù)，于是有即可以證明，這時(shí)，否則有，這是不可能的。因此，由是奇素?cái)?shù)，便有。從而，這樣由費(fèi)馬定理，有。但是因此有由此可知，n必為偶數(shù)，記n=2h,便有2n+1=4h+1.這樣便證明了整數(shù)的的所有奇素因數(shù)形式必為4h+1形式。又由于兩個(gè)4h+1形式的數(shù)的乘積仍為4h+1形式的數(shù)，故形式的數(shù)的奇因數(shù)必為4h+1形式的數(shù)。證2：由上面可知，-1是模2n+1的平方剩余，即 其中2n+1是奇素?cái)?shù)。由定理3知從而 ，故，所以n是偶數(shù)，其余同上。例6：證明：形如的素?cái)?shù)