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

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

2、容而忽略習(xí)題 的作用，則相當(dāng)于只身來(lái)到寶庫(kù)而空手返回而異。數(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í)題要求 p3:2，3 ；p8 :4 ；Pl2: 1 ；P17 :1， 2，5；p20: 1。第二章：不定方程（4學(xué)時(shí)）自學(xué)12學(xué)時(shí)二元一次不定方程 ax by二c多元一次不定方程a1x1 a2x2 anxn

3、=c 勾股數(shù)費(fèi)爾馬大定理。習(xí)題要求 P29: 1, 2, 4;P31 : 2, 3第三章：同余（4學(xué)時(shí)）自學(xué)12學(xué)時(shí)同余的定義、性質(zhì)剩余類(lèi)和完全剩余系歐拉函數(shù)、簡(jiǎn)化剩余系歐拉定理、費(fèi)爾馬小定理及在循環(huán)小數(shù)中的應(yīng)用習(xí)題要求 P43 :2，6；P46 :1 ；P49 :2，3 ；P531 ，2。第四章：同余式（方程）（4學(xué)時(shí)）自學(xué)12學(xué)時(shí)同余方程概念孫子定理高次同余方程的解數(shù)和解法素?cái)?shù)模的同余方程威爾遜定理。習(xí)題要求 P60 : 1； P64 : 1, 2； P69 : 1, 2。第五章：二次同余式和平方剩余（4學(xué)時(shí)）自學(xué)12學(xué)時(shí)二次同余式單素?cái)?shù)的平方剩余與平方非剩余勒讓德符號(hào)二次互反律雅可比符號(hào)

4、、素?cái)?shù)模同余方程的解法習(xí)題要求 P78 :2 ；P81: 1，2，3；P85 :1， 2 ；P89 :2 ；P93 :1 0第一章：原根與指標(biāo)（2學(xué)時(shí)）自學(xué)8學(xué)時(shí)指數(shù)的定義及基本性質(zhì)原根存在的條件指標(biāo)及n次乘余模2 及合數(shù)模指標(biāo)組、特征函數(shù)習(xí)題要求p123: 3。第一章整除、主要內(nèi)容整除的定義、帶余除法定理、余數(shù)、最大公因數(shù)、最小公倍數(shù)、輾轉(zhuǎn)相除法、互素、兩算術(shù)基本定理、Eratosthesen篩法、X和X的性質(zhì)、n!的標(biāo)準(zhǔn)分解兩互素、素?cái)?shù)、合數(shù)、二、基本要求通過(guò)本章的學(xué)習(xí)，能了解引進(jìn)整除概念的意義，熟練掌握整除整除的定義以及它的基本性質(zhì)，并能應(yīng)用這些性質(zhì)，了解解決整除問(wèn)題的若干方法，熟練掌握

5、本章中二個(gè)著名的定理： 帶余除法定理和算術(shù)基本定理。 認(rèn)真體會(huì)求二個(gè)數(shù)的最大公因數(shù)的求法的理論依據(jù)，掌握素?cái)?shù)的定義以及證明素?cái)?shù)有無(wú)窮多個(gè)的方法。能熟練求出二個(gè)整數(shù)的最大公因數(shù)和最小公倍 數(shù)，掌握高斯函數(shù)x的性質(zhì)及其應(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ù)有無(wú)窮多個(gè)的證明方法。（3）整除性問(wèn)題的若干解決方法。（4）x的性質(zhì)及其應(yīng)用，n!的標(biāo)準(zhǔn)分解式。四、自學(xué)指導(dǎo)整除是初等數(shù)論中最基本的概念之一，b I a的意思是存在一個(gè)整數(shù) q,使得等式a=bq 成立。因此這一標(biāo)準(zhǔn)作為我們討論整除性質(zhì)的基礎(chǔ)。也為我們提供了解決整除問(wèn)題的方法。

6、即當(dāng)我們無(wú)法用整除語(yǔ)言來(lái)敘述或討論整除問(wèn)題時(shí)，可以將其轉(zhuǎn)化為我們很熟悉的等號(hào)問(wèn) 題。(1)ab, b I c,則有 ac(2)ab, a I c,貝U有 amb+nc讀者要熟練掌握并能靈活應(yīng)用。特別要注意，數(shù)論的研究對(duì)象是整數(shù)集合，比小學(xué)數(shù)學(xué) 中非負(fù)整數(shù)集合要大。本章中最重要的定理之一為帶余除法定理，即為設(shè)a是整數(shù)，b是非零整數(shù)，則存在兩個(gè)整數(shù) q, r,使得a=bq+r(0蘭叫耳)它可以重作是整除的推廣。同時(shí)也可以用帶余除法定理來(lái)定義整除性，(即當(dāng)余數(shù)r=0時(shí))。帶余除法可以將全體整數(shù)進(jìn)行分類(lèi)，從而可將無(wú)限的問(wèn)題轉(zhuǎn)化為有限的問(wèn)題。這是一種很重要的思想方法，它為我們解決整除問(wèn)題提供了又一條常用

7、的方法。同時(shí)也為我們建立同余理論建立了基礎(chǔ)。讀者應(yīng)熟知常用的分類(lèi)方法，例如把整數(shù)可分成奇數(shù)和偶數(shù)，特別對(duì) 素?cái)?shù)的分類(lèi)方法。例全體奇素?cái)?shù)可以分成4k+1, 4k+3;或6k+1, 6k+5等類(lèi)型。和整除性一樣，二個(gè)數(shù)的最大公約數(shù)實(shí)質(zhì)上也是用等號(hào)來(lái)定義的，因此在解決此類(lèi)問(wèn)題時(shí)若有必要可化為等式問(wèn)題，最大公因數(shù)的性質(zhì)中最重要的性質(zhì)之一為a=bq+c,則一定有(a, b) = (b, c),就是求二個(gè)整數(shù)的最大公約數(shù)的理論根據(jù)飛是解決關(guān)于最大公約數(shù)問(wèn) 題的常用方法之一。讀者應(yīng)有盡有認(rèn)真體會(huì)該定理的證明過(guò)程?；ニ嘏c兩兩互素是二個(gè)不同的概念,既有聯(lián)系，又有區(qū)別。要認(rèn)真體會(huì)這些相關(guān)的性質(zhì)， 例如，對(duì)于任意

8、a ,b Z，可設(shè)(a ,b) =d，貝U a=dai ,b=dbi，貝U( ai ,bi) =1，于是可對(duì) ai ,bi 使用相應(yīng)的定理，要注意，相關(guān)定理及推論中互素的條件是經(jīng)常出現(xiàn)的。讀者必須注意定理 成立的條件，也可以例舉反例來(lái)進(jìn)行說(shuō)明以加深影響。順便指出，若|a I c, b I c, (a ,b )=1,則ab I C是我們解決當(dāng)除數(shù)為合數(shù)時(shí)的一種方法。好處是不言而喻的。最小公倍數(shù)實(shí)際上與最大公因數(shù)為對(duì)偶命題。特別要指出的是a和b的公倍數(shù)是有無(wú)窮多個(gè)。所以一般地在無(wú)窮多個(gè)數(shù)中尋找一個(gè)最小數(shù)是很困難的，為此在定義中所有公倍數(shù)中的最小的正整數(shù)。這一點(diǎn)實(shí)際上是應(yīng)用|自然數(shù)的最小自然數(shù)原理即

9、自然數(shù)的任何一個(gè)子集 一定有一個(gè)最小自然數(shù)有在。最小公倍數(shù)的問(wèn)題一般都可以通過(guò)以下式子轉(zhuǎn)化為最大公因數(shù) 的問(wèn)題。兩者的關(guān)系為a ,b N, a ,b=（a,b ：上述僅對(duì)二個(gè)正整數(shù)時(shí)成立。當(dāng)個(gè)數(shù)大于2時(shí)，上述式子不再成立。證明這一式子的關(guān) 鍵是尋找a , b的所有公倍數(shù)的形式，然后從中找一個(gè)最小的正整數(shù)。解決了兩個(gè)數(shù)的最小公倍數(shù)與最大公因數(shù)問(wèn)題后，就可以求出|n個(gè)數(shù)的最小公倍數(shù)與最大公因數(shù)問(wèn)題，可以?xún)蓚€(gè)兩個(gè)地求。即有下而定理設(shè) aa,a.是 n 個(gè)整數(shù)，（aa?） = d?,鳥(niǎo)忌）=d3,（dnan） = dn,則（aa?,a.）設(shè)aa? = m2, （m2,a3）=m3,（mn,an） =m

10、n,則有aa?,an= m.,素?cái)?shù)是數(shù)論研究的核心，許多中外聞名的題目都與素?cái)?shù)有關(guān)。除1外任何正整數(shù)不是質(zhì)數(shù)即為合數(shù)。判斷一個(gè)已知的正整數(shù)是否為質(zhì)數(shù)可用判別定理去實(shí)現(xiàn)。判別定理又是證明素?cái)?shù)無(wú)窮的關(guān)鍵。實(shí)際上，對(duì)于任何正整數(shù) n1，由判別定理一定知存在素?cái)?shù) p,使得p I n。 即任何大于1的整數(shù)一定存在一個(gè)素因數(shù)p。素?cái)?shù)有幾個(gè)屬于內(nèi)在本身的性質(zhì)，這些性質(zhì)是 在獨(dú)有的，讀者可以用反例來(lái)證明：素?cái)?shù)這一條件必不可少。以加深對(duì)它們的理解。一其中pI ab= p I a或p I b也是常用的性質(zhì)之一 |。也是證明算術(shù)基本定理的基礎(chǔ)。算術(shù)基本定理是整數(shù)理論中最重要的定理之一，即任何整數(shù)一定能分解成一些素?cái)?shù)

11、的乘積，而且分解是唯一的，不是任何數(shù)集都能滿(mǎn)足算術(shù)基本定理的，算術(shù)基本定理為我們提供 了解決其它問(wèn)題的理論保障。它有許多應(yīng)用，由算術(shù)基本定理我們可以得到自|然數(shù)的標(biāo)準(zhǔn)分 解問(wèn)題。設(shè) a= p 孑1 P ,k ，b= pf1 . p 卜，cti aO” aO 則有（a, b） = p 11 p kk片=m i n（, R）a，b= p f p=m aX% 衛(wèi)）例如可求最大公約數(shù)，正整數(shù)正約數(shù)的個(gè)數(shù)等方面問(wèn)題，對(duì)具體的 n,真正去分解是件 不容易的事。對(duì)于較特殊的 n，例如|n!分解還是容易的。應(yīng)用x的性質(zhì)，n!的標(biāo)準(zhǔn)分解 式可由一個(gè)具體的公式表示出來(lái)J，這一公式結(jié)合x(chóng)的性質(zhì)又提供了解決帶有乘除符

12、號(hào)的整除問(wèn)題的方法。本章的許多問(wèn)題都圍繞著整除而展開(kāi)，讀者應(yīng)對(duì)整除問(wèn)題的解決方法作一簡(jiǎn)單的小結(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) 無(wú)限個(gè)元素分成有限組，至少有一組其元素個(gè)數(shù)為無(wú)限。 梅森數(shù)：形如2n-1的數(shù)叫梅森數(shù)，記成|Mn=2n-1。c nc n 費(fèi)爾馬數(shù)：n為非負(fù)整數(shù)，形如22+1的數(shù)叫費(fèi)爾馬數(shù)，記成 Fn= 22 +1。設(shè)n=

13、Pi.Pkk，設(shè)n的正因子個(gè)數(shù)為d(n)，所有正因子之和為-(n)，貝U有d （n ） =（ ： i 1） （： 2 1）.（ -k 1）P胃-1 P賞-1 二（n ）=Pkk 1 -1Pi -1P2 -1Pk -1有關(guān)技巧1. 整數(shù)表示 a=ao x|Qn+ai xiQn-1+an，a=2kb（b為奇數(shù)）2整除的常用方法a. 用定義b. 對(duì)整數(shù)按被n除的余數(shù)分類(lèi)討論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,只要證明對(duì)任意素?cái)?shù)p, a中p的幕指數(shù)不超過(guò)b中p的幕指數(shù)即可,用p(a)表

14、示a中p的幕指數(shù)，則a|b= p(a) wp(b)例題選講例1.請(qǐng)寫(xiě)出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, 3k+2三種情況，令a=3k，顯 然成立，a=3k+1 時(shí)，a+2=3(k+1), a=3k+2 時(shí)，a+1=3(k+1)。例3.證明Ig2是無(wú)理數(shù)。證：假設(shè)Ig2是有理數(shù)，則存在二個(gè)正整數(shù) p, q，使得Ig2=p，由對(duì)數(shù)定義可得10p=2q , q則有2p 5p =2q,則同一個(gè)數(shù)左邊含因子 5,右邊不含因子5,與算術(shù)基本定理矛盾。

15、二Ig2 為無(wú)理數(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!末尾零的個(gè)數(shù) 解：因?yàn)?0=2X 5,而2比5多,所以只要考慮2004!中5的幕指數(shù)，即5 (2004!)2004200420042004右話(huà) 丁 歹例 6.證明(n!) (n-1)!|(n!)!證：對(duì)任意素?cái)?shù)p,設(shè)(n!) (n-1)!中素?cái)?shù)p的指數(shù)為，(n!) !中p的指數(shù)B，則(n -1)!k 4=ot即_ ,即左邊整除右邊例 7.證明 2003|( 20022002+20042004-20

16、05)證：20022002= (2003-1) 2002=2003Mi+120042004= (2003+1) 2002=2003M2+120022004 2002+2004-2005=2003 (M1+M2-1)由定義 2003| (2002202+2004204-2005)(1000)。例8.設(shè)d(n)為n的正因子的個(gè)數(shù)，二(n)為n的所有正因子之和，求d(1000),解： 1000=23 53d(1000)=(3+1)(3+1)=16,二(1000)=例9.設(shè)c不能被素?cái)?shù)平方整除，若a2|b2c，則a|b證：由已知 p(c) 1，且 p(a2)p(b2c) 2p(a) 2p(b)+p(c

17、), p(a) p(b)+學(xué)即 p(a) p(b) , a|b例10.若Mn為素?cái)?shù)，則n定為素?cái)?shù)。證：若n為合數(shù)，則設(shè)n=ab，(1a,bm，則 Fn-2= ( 2 2心-1 ) ( 2丄 1) =(Fn-1-2) ( 22心-1)=Fn-lF n-2Fm- Fo設(shè)（Fn,Fm） =d,則 d|Fn, d|Fm= d|2但Fn為奇數(shù)， d=1,即證。例12.設(shè)m,n是正整數(shù)。證明0 _1,2n _1）=尹，證：不妨設(shè)m _n。由帶余數(shù)除法得m =q 1n門(mén)，0乞門(mén)乞n.我們有2m _ 1 _ 2q們 r1 - 2“ 2r1 _ 1 _ 2r1 （2q們 _ 1） 2口 - 1由此及 2n -

18、1| 2q1n -1 得,（2m -1,2n -1）=（2n -1,2r1 -1）注意到（m,n） tn,），若=0 ,則（m，n）=n，結(jié)論成立 若ro0 ,則繼續(xù)對(duì)（2n _1,2r1 一1）作同樣的討 論，由輾轉(zhuǎn)相除法知，結(jié)論成立。顯見(jiàn)，2用任一大于1的自然a代替，結(jié)論都成立。例13.證明：對(duì)任意的正整數(shù)n，成立如下不等式lgn _k lg2。其中n是數(shù)n的以10為底的對(duì)數(shù)，k是n的不同的素因數(shù)（正的）的個(gè)數(shù)。證：設(shè)n是大于1的整數(shù)（如果n=1，上述不等式顯然成立，因k =0），P1, P2-， Pk是n的k個(gè) 相異的素因素。n的素因數(shù)分解式為n = p11p22.pkk .（h 1,i

19、 =1,.,k）,由于 pi 逹（i=12.,k），從而n = p11p22.pkk -21 -2,2 . 2lk =22 . lk，而i1 I2 . lk -k，故 n - 2 k。將上述不等式取對(duì)數(shù)（設(shè)底a 1 ），則有l(wèi)og a n :-k log a 2。特別有l(wèi)gn -k lg2。例14.試證明任意一個(gè)整數(shù)與它的數(shù)字和的差必能被9整除，并且它與它的數(shù)字作任意調(diào)后換后所成整數(shù)的差也能被9整除。證：設(shè)整數(shù)m的個(gè)位、十位、百位的數(shù)字分別為ai ,a2，an，則m可表作:m二a-10a 2 - 100a 3n i . -10n-an 1個(gè)二（a 1亠a? 亠已3亠 亠a.）亠（9a 2亠99

20、a3亠 亠99. 9an ）n J個(gè)r-=（a1 川日2 ：七3-. a.）：卜9（日2 11a 3 川川 111an ）n J個(gè)n fi所以 m -（a1 a2 - a 3 -.-an） =9（a2 -.-11a3 -.-. -.-11. 1a n）因?yàn)閍?,日3,，an都是整數(shù)，所以任一整數(shù)與其數(shù)字之和的差必能被 9整除再設(shè)將a1 ,aan按任一種順序排成a1 ,a2，an，并令二=日1- a? -. - an ，；二=al a 2 . - a n ， m =a 1 - 10a 2 -. - 10n an ，m =a1 -10a2 .- 10n 丄an 。根據(jù)前面證明的結(jié)果，知存在整數(shù) A

21、，B，使m ；=9A,m_L=9B.因?yàn)椋?；，所以 m _m 9A 一；J_9B =9(A _B ) 0由于A-B是整數(shù)，這就證明了 m -m能被9整除。注：若對(duì)某個(gè)整數(shù)k(1 k n)，有ak =0，但當(dāng)k :i 0，y0，z0，（x，y） =i, 2 I x的條件可以給出x2+y2=z2 的通解公式，x=2ab, y=a2-b2, z2=a2+b2, ab0 , (a ,b)=1, a ,b一奇一偶。若將 2 I x 限為 2I y,則也有相應(yīng)的一個(gè)通解公式。在證明這個(gè)通解公式的過(guò)程中，用到了引理uv=w2, u0,v0, ( u ,v)=1，則 u=a2, v=b2, w=ab。a0,

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

23、中常見(jiàn)的形式，一般的要求解不定方程比證明不定方程無(wú)解要容易些。證明不定方程無(wú)解的證明方法常采用以下形式：(反證法)若A有解=Ai有解= A有解= A有解，而A本身無(wú)解，這樣來(lái)構(gòu)造矛盾。從而 說(shuō)明原不定方程無(wú)解。對(duì)于證明不定方程的無(wú)解性通常在幾種方法，一般是總的幾種方法交替使用。特別要求 掌握：簡(jiǎn)單同余法、因子分解法、不等式法，以及中學(xué)數(shù)學(xué)中所涉及的判別式法。五、例子選講 例1:利用整數(shù)分離系數(shù)法求得不定方程 15x+10y+6z=61。解：注意到z的系數(shù)最小，把原方程化為iiZ=(=5x -10y - 61) = -2x -2y 10(七x - 2y - 1)66令 t1= 1( -3x 2y

24、 1) z，即-3x+2y-6t1 +1=01 1此時(shí) y 系數(shù)最小， y 二？(3x 6t1 -1)=x 3t1 -(x -1)令t2 = *(x -1r z ,即x =212 1,反推依次可解得y=x+3ti+t2=2t2+1+3t1+t2=1+3t1+3t2z=-2x-2y+10+t1 =6-5t1+10t2X =1 +2t2原不定方程解為y =1 +3ti +3t2 tlt2 Z.z =6 _5ti _10t2例2：證明2是無(wú)理數(shù)證：假設(shè)2是有理數(shù)，則存在自數(shù)數(shù)a,b使得滿(mǎn)足x2 =2y2即a2 =2b2，容易知道a是偶數(shù), 設(shè) a=2ai，代入得 b2 =2aj ,又得到 b 為偶數(shù)

25、，ai : b : a，設(shè) b =2bi，則 aj =2bf,這里 b? : ai 這樣可以進(jìn)一步求得 a2，b2且有 abaibi a2b2但是自然數(shù)無(wú)窮遞降是不可能的，于是產(chǎn)生了矛盾，2為無(wú)理數(shù)。例3:證明：整數(shù)勾股形的勾股中至少一個(gè)是3的倍數(shù)。證：設(shè) N=3m i（m 為整數(shù)）， N2=9m2土6m+i=3（3m2土2m）+i即一個(gè)整數(shù)若不是3的倍數(shù)，則其平方為3k+i,或者說(shuō)3k+2不可能是平方數(shù)，設(shè)x,y為勾 股整數(shù)，且x,y都不是3的倍數(shù)，則x2,y2都是3k+i，但z2=x2+y2=3k+2形，這是不可能， 勾股數(shù)中至少有一個(gè)是3的倍數(shù)。例4:求x2+y2=328的正整數(shù)解解：

26、328為偶數(shù)， x,y奇偶性相同，即xy為偶數(shù)，設(shè)x+y=2u, x-y=2v，代入原方程即 為2 2 /u +v =164,同理令 u+v=2ui,u-v=2vi 有2 2ui vi 82, ui vi =2u 2, ui vi =2/2u 2 vf =4i, u 2,v2 為一偶一奇，且 0u26u2=i, 2, 3, 4, 5 代方程，有解(4, 5) (5, 4)原方程解 x=i8,y=2，或 x=2,y=i8。2例5:求x +xy-6=0的正整數(shù)解。解：原方程等價(jià)于x（x+y）=2 3,故有 例6:證明不定方程x2-2xy2+5z+3=0無(wú)整數(shù)解。/ =2,x +y =3,=3,x

27、=,+y =2,x +y =6,=6,x y =i.即有 x=2,y=i; x=i,y=5.解：若不定方程有解，則x =y2 _ ,y4_3但 y = 0, 1(mod5), 對(duì) y,z , y4-5z-3=2, 3(mod5)而一個(gè)平方數(shù)三0, 1, 4 (mod 5) y4-5z-3不可能為完全平方，即，y4_5z_3不是整數(shù)，所以原不定方程無(wú)解。例7:證明：x2 y2 z8a 7無(wú)整數(shù)解證：若原方程有解，則有x2 y2 z 8a 7(mod 8)注意到對(duì)于模8,有02 = 0,12 =1, 22 =4, 32 =1,42 =0, 52 = 1,62 =4, 72 = 1,因而每一個(gè)整數(shù)對(duì)

28、于模8,必同余于0, 1, 4這三個(gè)數(shù)。不論 x2, y2, z2 如何變化，只能有 x2 y2 z 0,1,2,3,4,5,6(mod8)而8a 7(mod8)，故8a 7不同余于x2 y2 z2關(guān)于模8，所以假設(shè)錯(cuò)誤，即8a 7 x2 y2 z2，從而證明了原方程無(wú)解。例8:某人到銀行去兌換一張d元和c分的支票，出納員出錯(cuò)，給了他 c元和d元，此人直 到用去23分后才發(fā)覺(jué)其錯(cuò)誤，此時(shí)他發(fā)現(xiàn)還有2d元和2c分，問(wèn)該支票原為多少錢(qián)？解：由題意立式得：108 d 23 =100 2d 2c即 98c -199d =23.令 u =C - 2d 得 98u 3d =23,令v =33u -d 彳得

29、 3v -u =23.所以u(píng) =3j -23(v為任意整數(shù))，代入得：d =33u -v =98v -3323,( 1)c =u - 2d =199v -6723,其中V是任意整數(shù)。又根據(jù)題意要求：d -0,0 :c ：100.根據(jù)（1）,僅當(dāng)v=8時(shí)滿(mǎn)足此要求，從而d =25,c因此該支票原為25元51分.第三章同余一、主要內(nèi)容同余的定義、性質(zhì)、剩余類(lèi)和完全剩余系、歐拉函數(shù)、簡(jiǎn)化剩余系、歐拉定理、費(fèi)爾馬小定理、循環(huán)小數(shù)、特殊數(shù) 2, 3, 4，5, 6，7, 8, 9，11，13的整除規(guī)律二、基本要求通過(guò)本章的學(xué)習(xí)，能夠掌握同余的定義和性質(zhì)，區(qū)別符號(hào)：“三”和=”之間的差異。能利用同余的一些

30、基本性質(zhì)進(jìn)行一些計(jì)算，深刻理解完全剩余系，簡(jiǎn)化剩余系的定義、性質(zhì)及 構(gòu)造。能判斷一組數(shù)是否構(gòu)成模 m的一個(gè)完全剩余系或一個(gè)簡(jiǎn)化剩余系。能計(jì)算歐拉函數(shù) 的值，掌握歐拉定理、費(fèi)爾馬小定理的內(nèi)容以及證明方法。能應(yīng)用這二個(gè)定理證明有關(guān)的整 除問(wèn)題和求余數(shù)問(wèn)題。能進(jìn)行循環(huán)小數(shù)與分?jǐn)?shù)的互化。三、難點(diǎn)和重點(diǎn)（1）同余的概念及基本性質(zhì)（2）完全剩余系和簡(jiǎn)化剩余系的構(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)容之一，由同余定義可知，若a= b（mod m）,則a和b被m除后有相同的余數(shù)。這里 m為正整

31、數(shù)，一般要求 m大于1,稱(chēng)為模，同余這一思想 本質(zhì)上是將整數(shù)按模 m分類(lèi)，然后討論每一個(gè)類(lèi)中整數(shù)所具有的共性及不同類(lèi)之間的差異 |。 第一章中用帶余除法定理將整數(shù)分類(lèi)解決一些問(wèn)題的方法只不過(guò)是同余理論中的一個(gè)特殊 例子。從同余的定理上看，同余和整除實(shí)際上是同一回事，故 |同余還有二個(gè)等價(jià)的定義：- 用整除來(lái)定義即 ml a-b。用等號(hào)來(lái)定義a=b+mt。值得注意a和b關(guān)于m同余是個(gè)相 對(duì)概念。即它是相對(duì)于模 m來(lái)講，二個(gè)整數(shù)a和b關(guān)于一個(gè)整數(shù)模m同余。則對(duì)于另一個(gè) 整數(shù)模m1，a和b未必會(huì)同余。從定義上看，同余和整除是同一個(gè)事情，但引進(jìn)了新的符號(hào)“三”后，無(wú)論從問(wèn)題的敘 述上，還是解決問(wèn)題的方

32、法上都有了顯著的變化，同時(shí)也帶來(lái)了一些新的知識(shí)和方法。在引 進(jìn)了同余的代數(shù)性質(zhì)和自身性質(zhì)后，同余符號(hào)“三”和等號(hào)“=”相比，在形式上有幾乎一致的性質(zhì)，這便于我們記憶。事實(shí)上在所有等號(hào)成立的運(yùn)算中，只有除法運(yùn)算是個(gè)例外，即 除法的消去律不成立。為此對(duì)于同余的除法運(yùn)算我們有二種除法：(i)模不改變的除法，若 ak=bk(mod m) ，(k,m)=1，則 a= b(mod m)(ii) 模改變的除法， 若 ak = bk(mod m) (k,m)=d,貝U a= bm mod a)1這一點(diǎn)讀者要特別注意。完全剩余系和簡(jiǎn)化剩余系是二個(gè)全新的概念，讀者只要搞清引成這些概念的過(guò)程。因?yàn)?同余關(guān)系是一個(gè)等

33、價(jià)關(guān)系，利用等價(jià)關(guān)系可以進(jìn)行將全體整數(shù)進(jìn)行分類(lèi)，弄清來(lái)朧去脈，對(duì) 于更深刻理解其本質(zhì)是很有好處的。完全剩余系或簡(jiǎn)化剩余系是一個(gè)以整數(shù)為元素的集合， 在每個(gè)剩余類(lèi)各取一個(gè)數(shù)組成的 m個(gè)不同數(shù)的集合，故一組完全剩余系包含 m個(gè)整數(shù)，由于 二個(gè)不同的剩余類(lèi)中的數(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)(g,m2)=1時(shí)，能由 m!的完全剩余系和 m2的完全剩余系，構(gòu)造 口!口2完全剩余系。為討論

34、簡(jiǎn)化剩余系，需要引進(jìn)歐拉函數(shù) (m)，歐拉函數(shù) (n)定義為不超過(guò)m且與m互 素的正整數(shù)的個(gè)數(shù)，記為 (m,要掌握 (m)的計(jì)算公式，了解它的性質(zhì)。這些性質(zhì)最主要 的是當(dāng)(a ,b ) =1 時(shí)， (ab) = (a) (b)，和傘(p)二 卩肚一1現(xiàn)在在剩余類(lèi)中把與 m互素的集合分出來(lái)，從中可在各個(gè)集合中任取一個(gè)數(shù)即可構(gòu)造模 m的一個(gè)簡(jiǎn)化剩余系。另一方面，簡(jiǎn)化剩余數(shù)也可從模m的一個(gè)完全剩余系中得到簡(jiǎn)化剩余系，一組完全剩余系中與 m互素的的數(shù)組成的 (n)個(gè)不同數(shù)的集合稱(chēng)為 m簡(jiǎn)化剩余系。同 樣簡(jiǎn)化剩余系也有一個(gè)判別條件。判別一組整數(shù)是否為模m的簡(jiǎn)化剩余系的條件為(2) 個(gè)數(shù)= (m)(3)

35、關(guān)于m兩兩不同余(3) 每個(gè)數(shù)與m互素關(guān)于m的簡(jiǎn)化剩余系也能用已知完全剩余系構(gòu)造新的簡(jiǎn)化剩余系。設(shè)(a, m) =1, x為m的簡(jiǎn)化剩余系，貝U ax也是m的簡(jiǎn)化剩余系。當(dāng)(m,m2)=1時(shí)，能由g的簡(jiǎn)化剩余系和m2的簡(jiǎn)化剩余系，構(gòu)造口!口2簡(jiǎn)化剩余系。歐拉定理、費(fèi)爾馬小定理是同余理論非常重要的定理之一。要注意歐拉定理和費(fèi)爾馬定 理的條件和結(jié)論。歐拉定理：設(shè) m為大于 1的整數(shù)，(a，m) =1，則有a (m)三 1(mod m)費(fèi)爾馬小定理：若p是素?cái)?shù)，則有1ap 三 a(mod p)除此以外，歐拉定理的證明的思想是非常好的，在各個(gè)地方都有應(yīng)用。 |就歐拉定理、費(fèi) 爾馬小定理來(lái)講，它在某些形

36、如 an數(shù)的整除問(wèn)題應(yīng)用起來(lái)顯得非常方便|。同余方法也是解 決整除問(wèn)題的方法之一。另外同余方法在證明不定方程時(shí)也非常有用，即要掌握同余“三”和相等“=”的關(guān)系:相等必同余，同余未必相等，不同余肯定不相等。對(duì)于特殊數(shù)的整除規(guī)律要求能掌握其一般定理的證明，并 熟記一些特殊數(shù)的整除規(guī)律1、一個(gè)整數(shù)被2整除的充要條件是它的末位為偶數(shù) 2、一個(gè)整數(shù)被3整除的充要條件是它的各位數(shù)字之和能被3整除3、一個(gè)整數(shù)被9整除的充要條件是它的各位數(shù)字之和能被9整除4、一個(gè)整數(shù)被5整除的充要條件是它的末位為0或55、一個(gè)整數(shù)被4, 25整除的充要條件是它的末二位能被 4, 25整除6、一個(gè)整數(shù)被8, 125整除的充要條

37、件是它的末三位能被 8, 125整除。若1i p,則有i | p則與p為素?cái)?shù)矛盾 i=p, p|q-1又 q-1 為偶數(shù)，2|q-1, 2p|q-1,q-1=2pk ,即 q=2pk+1例4:證明13|廠(chǎng)1+322n+1n+2nn證：.4+3= 4 16+9-3三3n (4+9)三 13X3n三0(13) 13|0+1+3+2例5：證明5y+3=x2無(wú)解證明：若5y+3=x2有解，則兩邊關(guān)于模5同余有 5y+3=x2(mod 5)即 3=x2(mod 5)而任一個(gè)平方數(shù) x2=0,1,4(mod 5) 3 三 0,1,4(mod 5)即得矛盾，即5y+3=x2無(wú)解例6:求111被7除的余數(shù)。5

38、0解：I 111111 被 7 整除， 11.*. 1 = 11 (mod 7)= 4 (mod 7),即余數(shù)為 450例7:把0.042 63化為分?jǐn)?shù)。解：設(shè) b=0.042 63，從而 1000b=42. 63,100000b=4263.63，99000b=4263-42._4221 _ 469b=。9900011000當(dāng)然也可用直化分?jǐn)?shù)的方法做。例8:設(shè)一個(gè)數(shù)為62XY427是9,11的倍數(shù)，求X , Y解：因?yàn)?9|62XY427所以 9|6+2+X+Y+4+2+7 即 9|21+X+Y又因?yàn)?11 |62XY427,有 11 |(7+4+X+6-2-Y-2)即 11| (X-Y+13

39、)因?yàn)?乞X, 丫冬9,所以有2仁21+X+Y139，4 X-Y+13 1 。對(duì)于(2)的解的求法我們用待定系數(shù)法。設(shè)f(x)= O(mod p)的解為x= Xi(mod p)為解。則當(dāng)p卜f (x)時(shí)，f(x)= O(mod p)的一個(gè)解xi可求出f(x) = O(mod p2)的一個(gè)解。方法如下：將 x=xi+pti 代入 f(x) = O(mod p2)有f(xi+pti) = O(mod p )= f(x i)+pt if (xi) = O(mod p )= f-x + t1 f，(x1) = O(mod p)二 ti=ti + p t 2p代入 x=x i +pt i=xi +p(t

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

41、。P為素?cái)?shù)，則有(p-i)!三-i(mod p),實(shí)際上wilsom定理的逆定理也成立。故 wilsom定理可以作為素?cái)?shù)成立主要條件。五、例子選講補(bǔ)充知識(shí)i定義 仁當(dāng)(a，m) =i時(shí)，若ab三i(modm)，則記b三丄(mod m)，稱(chēng)為形式分?jǐn)?shù)。根據(jù)定義和記號(hào)，則aa-表示c丄關(guān)于模m，則有下列性質(zhì)=Ci (mod m). aic2、若(d，m) =i，且 a =da,c =dG,則利用形式分?jǐn)?shù)的性質(zhì)把分母變成1,從而一次同余式的解例1:解一次同余式17x三19(mod25) 解：(17, 25) =1,原同余方程有解，利用形式分?jǐn)?shù)的性質(zhì),同余方程解為三 7(mod 25)19 _ -6

42、_ 18 _ -717-824-1x 三-2(mod12)例2:解同余方程組 x =6(mod10)x 三 1(mod15)解：(12, 10) |6+2, (12, 15) |-2-1, (10, 15) |6-1原同余方程有解，且等位于X 三2(mod4)x 三一2(mod3)”収三一2(mod4)x 三6(mod2)此時(shí)變成模兩兩互素二彳x 三1(mod3)x 三6(mod5)x 三 1(mod5)x 三 1(mod3).X 三(mod5)由孫子定理可求得其解為：x =46(mod 60)例3:解一次同余式組”51x 三 57(mod75)I 3x 三 1(mod4)解：用常規(guī)方法先求每

43、一個(gè)一次同余式的解，得到下列一次同余式組X 三 7,32,57(mod75)x 三 3(mod4)然后用孫子定理求解，所以同余方程組有3個(gè)解，且解分別為x 三 7(mod300) , x 三 107(mod 300), x 三 207(mod 300)例 4：設(shè) 2p+1 是素?cái)?shù)，則(P!)2(-1)p = O(mod 2p 1)證：設(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+1=1 ( n-1) 2( n -2) 2( n -3)(p-1) n-( p-1

44、) 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)p= 0(mod 2p+1)例5:解同余方程28x三21(mod 35)解：(28,35) =7|21,原同余方程有解，且有7個(gè)解原同余方程等價(jià)于4x= 3(mod 5) 而且 4灼 3(mod 5)解為 x= 2(mod 5)原同余方程解為 2, 7, 12, 17, 22, 27, 31 (mod 35)第五章二次剩余理論一、主要內(nèi)容平方剩余與平方非剩余的概念、歐拉判別條件、勒讓德符號(hào)、二次互反律、雅可

45、比符號(hào)、素?cái)?shù)模同余方程的解法二、基本要求通過(guò)本章的學(xué)習(xí)，掌握平方剩余與平方非剩余的概念，掌握勒讓德符號(hào)的定義、性質(zhì)計(jì)算及利用它來(lái)判別一個(gè)二次同余方程是否有解，對(duì)于幾個(gè)較特殊的勒讓德符號(hào)的值，要求能掌握它的推導(dǎo)方法。了解推可比符號(hào)的定義，性質(zhì)及功能，會(huì)解素?cái)?shù)的模的二次同余方程。及 證明一些二次不定方程無(wú)解中的應(yīng)用。三、重點(diǎn)和難點(diǎn)(1)歐拉判別定理：即a為p的平方剩余的條件。(2) 勒讓德符號(hào)，二次互反律。(3) 素?cái)?shù)模同余方程的解法。四、自學(xué)指導(dǎo)對(duì)于一般的高次同余方程的求解歸納為模為 p的情形。對(duì)于同余方程f(x) = O(mod p) 的求解依賴(lài)于f(x) = o(mod p)的解。而且對(duì)于一般的f(x)，求解f(x) = O(mod p)的解是 很困難的。本章討論f(x)為一個(gè)整系數(shù)的二次三項(xiàng)式時(shí)情形?？傻玫蕉瓮嗍降臉?biāo)準(zhǔn)形式x = a(mod p) (a