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

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

2、到它的內(nèi)容而忽略習(xí)題 的作用，則相當(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 ；Pl7 :1，2，5；p20 :1。第二章：不定方程（4學(xué)時）自學(xué)12學(xué)時二元一次不定方程ax by c多元一次不定方程a1x1 a2x2a

3、nxn c勾股數(shù)費爾馬大定理。習(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。第一章整除、主要內(nèi)容整除的定義、帶余除法定理、余數(shù)、最大公因數(shù)、最小公倍數(shù)、輾轉(zhuǎn)相除法、互素、兩兩互素、素數(shù)、合數(shù)、算術(shù)基本定理、Eratosthesen篩法x和x的性質(zhì)、n!的標準分解式二、基本要求通過本章的學(xué)習(xí)，能了解引進整除概念的意義，熟練掌握整除整除的定義以及它的基本

5、性質(zhì)，并能應(yīng)用這些性質(zhì)，了解解決整除問題的若干方法，熟練掌握本章中二個著名的定理： 帶余除法定理和算術(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）整除性問題的若干解決方法。（4）x的性質(zhì)及其應(yīng)用，n!的標準分解式。四、自學(xué)指導(dǎo)整除是初等數(shù)論中最基本的概念之一，b I a的意思是存在一個整數(shù)q,使得等式a=bq 成立。因此這一標準作為我

6、們討論整除性質(zhì)的基礎(chǔ)。也為我們提供了解決整除問題的方法。 即當(dāng)我們無法用整除語言來敘述或討論整除問題時，可以將其轉(zhuǎn)化為我們很熟悉的等號問 題。對于整除的若干性質(zhì)，最主要的性質(zhì)為傳遞性和線性組合性，即（1） a I b, b I c,貝U有 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|b)它可以重作是整除的推廣。同時也可以用帶余除法定理來定義整除性，(即當(dāng)

7、余數(shù)r=0時)。帶余除法可以將全體整數(shù)進行分類，從而可將無限的問題轉(zhuǎn)化為有限的問題。這是一種很重要的思想方法，它為我們解決整除問題提供了又一條常用的方法。同時也為我們建立同余理論建立了基礎(chǔ)。讀者應(yīng)熟知常用的分類方法，例如把整數(shù)可分成奇數(shù)和偶數(shù)，特別對 素數(shù)的分類方法。例全體奇素數(shù)可以分成 4k+1, 4k+3;或6k+1, 6k+5等類型。和整除性一樣，二個數(shù)的最大公約數(shù)實質(zhì)上也是用等號來定義的，因此在解決此類問題時若有必要可化為等式問題，最大公因數(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)的。讀者必須注 意定理成立的條件，也可以例舉反例來進行說明以加深影響。順便指出，若|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 是

10、 n 個整數(shù)，（aa?） d2，（d2,a3） d3, （dn i,an） dn,則（aa2, an） 込J設(shè)??？（m（2,a3）（mn i,an） m.,則有aa2, an=mn，素數(shù)是數(shù)論研究的核心，許多中外聞名的題目都與素數(shù)有關(guān)。除1外任何正整數(shù)不是質(zhì)數(shù)即為合數(shù)。判斷一個已知的正整數(shù)是否為質(zhì)數(shù)可用判別定理去實現(xiàn)。判別定理又是證明素數(shù)無窮的關(guān)鍵。實際上，對于任何正整數(shù) n1，由判別定理一定知存在素數(shù) p,使得p I n。 即任何大于1的整數(shù)一定存在一個素因數(shù)p。素數(shù)有幾個屬于內(nèi)在本身的性質(zhì)，這些性質(zhì)是 在獨有的，讀者可以用反例來證明：素數(shù)這一條件必不可少。以加深對它們的理解。一其中pI a

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

12、解是件 不容易的事。對于較特殊的 n，例如|n!分解還是容易的。應(yīng)用x的性質(zhì)，n!的標準分解 式可由一個具體的公式表示出來J，這一公式結(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）無限個元素分成有限組，至少有一組其元素個數(shù)為無限

13、。 梅森數(shù)：形如pn-i |的數(shù)叫梅森數(shù)，記成 M=2n-i I。n n 費爾馬數(shù)：n為非負整數(shù)，形如221的數(shù)叫費爾馬數(shù)，記成Fn=221。設(shè)n=Pi1Pkk，設(shè)n的正因子個數(shù)為d（n），所有正因子之和為（n ），貝q有d(n) (i 1) ( 21).( k 1)()P11 11 P22 11 Pkk 11(n)P11 P2 廠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. 因式分解an-bn=(a-b)M, an+bn=(a+b) M

14、, 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ù)，則存在二個正整數(shù) p, q，使得Ig2

15、= p，由對數(shù)定義可得10p=2q , q則有2p5 p =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!) = 200452004252004200412554200449955例 6.證明(n! ) (n-1)! |( n!)!證：對任意素數(shù)p,設(shè)(n! ) (n-1)!中

16、素數(shù)p的指數(shù)為(n! ) !中p的指數(shù)B，則(n1)!k 1(n1)!k 1(nx ) n (x )n!k 1 pkn(n 1)!k 1 pkk1.n!1)!-P(n1)!k1n!-kP即，即左邊整除右邊例 7.證明 2003| (+-2005)2002證：=(2003-1)=2003M+1=(2003+1) 2002=2003M+1 +-2005=2003 (M1+M2-1 ) 由定義 2003| (+-2005)例8.設(shè)d(n)為n的正因子的個數(shù),3a解：1000=2 5(n)為n的所有正因子之和，求d(1000),(1000)。d(1000)=(3+1)(3+1)=16 ,(1000)=

17、 2 454例9.設(shè)c不能被素數(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.若M為素數(shù)，則n定為素數(shù)。證：若n為合數(shù)，則設(shè)n=ab，(1a,bm則Fn-2= ( 22nn 1n 11 )( 22 1 1)=(Fn-1-2)( 22n 1 1 )設(shè)(Fn,Fm) =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è) mn

18、。由帶余數(shù)除法得mq1nr1,0r1 n.我們有2m 1 2q1n r1 2r1 2r1 12r1 (2q1n1)2r1 1由此及 2n1| 2q1n1得, (2m1,2n1)=(2n1,2r1 1)注意到 (m,n )(n，n),若r10 ,貝U (m ,n )n , 結(jié)論成立 .若 r10 , 則繼續(xù)對 (2n1,2r1 1)作同樣的討論，由輾轉(zhuǎn)相除法知，結(jié)論成立。顯見， 2 用任一大于 1 的自然 a 代替，結(jié)論都成立。例 13. 證明：對任意的正整數(shù) n ，成立如下不等式 lgn k lg2。其中Ign是數(shù)n的以10為底的對數(shù)，k是n的不同的素因數(shù)(正的)的個數(shù)。證：設(shè)n是大于1的整數(shù)

19、(如果n =1，上述不等式顯然成立，因k =0)，Pi, P2,，Pk是n的k個 相異的素因素。 n 的素因數(shù)分解式為npl1 P2 . pkk.( li1,i12.K),由于 Pi 2,(i 1,2,k)，從而nP1l1 P l22 . Pklk2l12l2.2lk2l1 l2 . lk ，而 l1 l2 . lk k ，故 n 2 k 。a 1),則有 loga n k loga 2。將上述不等式取對數(shù)(設(shè)底特別有 lgn k lg 2 。例14試證明任意一個整數(shù)與它的數(shù)字和的差必能被 9整除，并且它與它的數(shù)字作任意調(diào)后 換后所成整數(shù)的差也能被9整除。證：設(shè)整數(shù)m的個位、十位、百位的數(shù)字分

20、別為ai,a2，an，則m可表作：m a0,y0,z0, (x,y)=1,2 I x的條件可以給出x2+y2=z2 的通解公式，x=2ab，y=a2-b2，z2=a2+b2， ab0 , (a ,b)=1，a ,b 一奇一偶。若將 2 I x 限為2 I y，則也有相應(yīng)的一個通解公式。在證明這個通解公式的過程中，用到了引理uv=w2,u0, v0, (u ,v ) =1,貝U u=a2, v=b2, w=ab。 a0, b0, (a ,b ) =1。利用這個結(jié)論可以 求解某些不定方程。特別當(dāng) w=1或素數(shù)p。則由uv=1或uv=P可將原不定方程轉(zhuǎn)化為不定 方程組。從而獲得一些不定方程的解。上述

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

22、。從而說明原不定方程無解。對于證明不定方程的無解性通常在幾種方法，一般是總的幾種方法交替使用。特別要求 掌握：簡單同余法、因子分解法、不等式法，以及中學(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(3x 6t1 1) x 3t1 -1(x 1)令t2 =1) z ,即x 2t2 1,反推依次可解得y=x+3t 1+t 2=2t

23、 2+1+3t 1+t 2=1+3t 1+3t 2z=-2x-2y+10+t1=6-5t 1+10t2x 1 2t2原不定方程解為y 1 3t! 3t2 t it 2 乙z 6 5ti 10t2例2：證明,2是無理數(shù)證：假設(shè).2是有理數(shù)，則存在自數(shù)數(shù)a,b使得滿足X2 2y2即a2 2b2，容易知道a是偶數(shù),設(shè)a=2ai，代入得b2 2a2 ,又得到b為偶數(shù)，a 1 b a，設(shè)b 2bi，則aj 2bi2 ,這里b2 ai 這樣可以進一步求得 a2，b2且有abaibi a2b但是自然數(shù)無窮遞降是不可能的，于是產(chǎn)生了矛盾，.2為無理數(shù)。例3:證明：整數(shù)勾股形的勾股中至少一個是 3的倍數(shù)。證：設(shè)

24、 N=3n 1(m為整數(shù))，代=9吊6葉 1=3(3mi2m)+1即一個整數(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 2比 V!82,u! V! 2u 2, U! V! 2v 2U； V； 41, U2,V2 為一偶

25、一奇，且 0U26U2=1, 2, 3, 4, 5 代方程，有解(4, 5) (5, 4)原方程解 x=i8,y=2,或 x=2,y=i8。例5:求x2+xy-6=0的正整數(shù)解。解：原方程等價于x(x+y)=2 3,故有即有 x=2,y=1; x=i,y=5. x2,x3x1,x6,xy3, xy2, xy6, xy1.例6:證明不定方程x2-2xy2+5z+3=0無整數(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不可能為完全平方，即、屮5

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

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

28、、費爾馬 小定理、循環(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ù)的 值，掌握歐拉定理、費爾馬小定理的內(nèi)容以及證明方法。能應(yīng)用這二個定理證明有關(guān)的整除 問題和求余數(shù)問題。能進行循環(huán)小數(shù)與分數(shù)的互化。三、難點和重點（1）同余的概念及基本性質(zhì)（2）完全剩余系和簡化剩余系的構(gòu)造、判別（3）歐拉函數(shù)計算、歐拉定理、費爾馬

29、小定理的證明及應(yīng)用（4）循環(huán)小數(shù)與分數(shù)的互化（5）特殊數(shù)的整除規(guī)律。四、自學(xué)指導(dǎo)同余理論是初等數(shù)論中最核心的內(nèi)容之一，由同余定義可知，若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同余是個

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

31、ii)模改變的除法, 若 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兩兩不同余另外要能用已知

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

33、余系中得到簡化剩余系，一組完全剩余系中與 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)(mi，m2)1時，能由m!的簡化剩余系和m?的簡化剩余系，構(gòu)造mm?簡化剩余系。歐拉定理、費爾馬小定理是同余理論非常重要的定理之一。要注意歐拉定理和費爾馬定 理的條件和結(jié)論。歐拉定理：設(shè) m為大于 1的整數(shù)，(a，m)

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

35、整數(shù)被9整除的充要條件是它的各位數(shù)字之和能被 9整除。|4、一個整數(shù)被5整除的充要條件是它的末位為0或5。5、一個整數(shù)被4, 25整除的充要條件是它的末二位能被 4, 25整除。|6、一個整數(shù)被8, 125整除的充要條件是它的末三位能被 8, 125整除。|7 設(shè)a an1000n an ,1000n 1a0，則7或11或13整除a的充要條件是 7或 科若1i 1 。對于(2)的解的求法我們用待定系數(shù)法。設(shè)f(x)= O(mod p)的解為x= xi(mod p)為解。則當(dāng)p卜f (x)時，f(x)= O(mod p)的一個解xi可求出f(x) = O(mod pP為素數(shù)，則有(p-i) !三

36、-i(mod p)，實際上wilsom定理的逆定理也成立。故 wilsom定理可以作為素數(shù)成立主要條件。五、例子選講補充知識i定義 仁當(dāng)(a，n) =i時，若ab i(mod m)，則記b - (modm)，稱為形式分數(shù)。ac1根據(jù)定義和記號，則-表示c -關(guān)于模m，則有下列性質(zhì)aa c c mti /、丄丄 “ i(mod m),ti,t2 乙a a mt2 若(d， m) =i，且 a dai ,c dci,則- c-(mod m).a ai)的一個解。方法如下：將 x=x汁pt i 代入 f(x) = O(mod p2)有f(x i+pt i) = O(mod p )f(x i)+pt

37、if (x i) = O(mod p )f x+ti f ,(xi) = O(mod p) ti=ti + p t 2 p代入 x=x i +pt i=xi +p(t i +t 2p2)=x 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

38、的 條件必不可少。(2) 同余方程的解數(shù)與次數(shù)之間有關(guān)系解數(shù)w次數(shù)。這一點和代數(shù)方程也一樣。此時， 素數(shù)p的條件也必不可少本節(jié)的輔產(chǎn)品是 著名的 wilsom 定理。利用形式分數(shù)的性質(zhì)把分母變成1,從而一次同余式的解例1:解一次同余式17x19(mod25)解：(17, 25) =1，原同余方程有解，利用形式分數(shù)的性質(zhì),同余方程解為7(mod 25)196 18X178 24x 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

39、(mod 3)x 2(mod 4)此時變成模兩兩互素x 6(mod2)x 1(mod3)x 6(mod5)x 1(mod 5)x 1(mod 3)x (mod5)由孫子定理可求得其解為：x 46(mod 60)例3:解一次同余式組51x 57(mod75)3x 1(mod4)解：用常規(guī)方法先求每一個一次同余式的解，得到下列一次同余式組x 7,32,57(mod75)x 3(mod4)然后用孫子定理求解，所以同余方程組有3個解，且解分別為x 7(mod 300) , x 107(mod 300) , x 207(mod 300)例 4：設(shè) 2p+1 是素數(shù)，則(P!)2( 1)p O(mod 2

40、p 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-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) p= 0(mod 2p+1)例5:解同余方程28x三21(mod 35)解：(28,35 ) =7|21 ,原同余方程有解，

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

42、用。三、重點和難點(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ù)的二次三項式時情形?？傻玫蕉瓮嗍降臉藴市问絰2 = a(mod p) (a ,p)=1 p 為奇素數(shù)。 (1)以下內(nèi)容都是在標準形式下得到的。其中p為奇素數(shù)。平方剩余和平方非剩余是以同余方程(1)是否有解來定義的。因此平方剩余和平方非剩余只要在模p的一個簡化剩余系中找即可。實際上，模m的全體平方剩余和全體平方非剩余構(gòu)成了模p的一個簡化剩余系