【正文】 或除去一個數(shù)k，為了保持其同解性，必須（k ,m）=1，這一點和同余的性質(zhì)有區(qū)別。同余方程組（1）有解的條件(mi ,mj) ∣bibj ，1≤i，j≤k 。次數(shù)大于1的同余方程稱為高次同余方程，一般地高次同等方程可轉(zhuǎn)化一系列的高次同余方程組。方法如下：將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則 x≡x2(mod p2)即為f(x) ≡0(mod p)的解。P為素數(shù)，則有(p1)！≡1(mod p)，實際上wilsom定理的逆定理也成立。2(n2)三、重點和難點（1）歐拉判別定理：即a為p的平方剩余的條件。 （1）以下內(nèi)容都是在標準形式下得到的。 p=8K+1或8K1時，2是p的平方剩余，p=8K+3或8K3時，2是p的平方非剩余。在=1的條件下，如何求出x2≡a(mod p)的解。例：解同余方程x2≡73(mod137)解 ∵ =1，∴x2≡73(mod137)有二個解因為p=137，故0y≤34取q=3，則2為3一平方非剩余。例2：若3是素數(shù)p平方剩余，問p是什么形式的素數(shù)？解：∵ 由反轉(zhuǎn)定律，注意到p3，p只能為p1(mod 3)且 ∴ 只能下列情況 ∴ 或例3：證明形如4m+1的素數(shù)有無窮多個。又由于兩個4h+1形式的數(shù)的乘積仍為4h+1形式的數(shù)，故形式的數(shù)的奇因數(shù)必為4h+1形式的數(shù)。因此形如的素數(shù)有無窮多個。解：286=2143，433是素數(shù)，(143，443)=1奇數(shù)143不是素數(shù)，但可用判定可比符號計算的生勒讓德符號 ∴原方程有解。指數(shù)是指使at≡(modm)的最小的正整數(shù)d。五、例子選講例1：試10是模17的原根。故2關(guān)于模q的階為4p=q1，所以2是模q的一個原根。7在2003！中的最高冪指數(shù)是 。1φ（1）＋φ（P）＋…φ（）= 。（6分）九、解不定方程 （6分）《初等數(shù)論》模擬試卷（A）答案一、16，2340，9360 素數(shù) 7 331 15 5，25 81 311 1401 51 2，291 查書二、孫子定理三、 見書四、 證：由條件可得c為奇數(shù)，b為偶數(shù)如果p（x）=0有根q，若q為偶數(shù)，則有為奇數(shù)，而p（q）=0為偶數(shù)，不可能，若q為奇數(shù)，則有為奇數(shù)，而p（q）=0為偶數(shù)，也不可能，所以沒有整數(shù)根五、 證：由歐拉定理由費爾馬定理六、（5，11）=1，（4，11）=1，（3，11）=1由歐拉定理得，進一步有，對任何正整數(shù)ｋ，ｍ，ｎ有即有１１| 七、 見例。通解為 。二、解同余方程組（12分）三、 敘述并且證明費爾馬定理。九、98764539。1X能被3，4，7整除，這個最小的正整數(shù)是 。2003！中末尾連續(xù)有 個零。（12分）四、 如果整系數(shù)的二次三項式 時的值都是奇數(shù)，證明 沒有整數(shù)根（6分）五、 設(shè)Ｐ為奇素數(shù)，則有（8分）（1）（2）六、 證明：對任何正整數(shù)ｋ，ｍ，ｎ　有１１| （6分）七、證明：是無理數(shù)。的末位數(shù)是 。n， 若則n為 。根據(jù)本章定理2，有而q是奇素數(shù)，必有之一，但不管那一種，均有，因此所以由定理，2是模q的非平方剩余，即。要弄清p和pα的原根之間的關(guān)系，及pα與2pα的原根之間的關(guān)系。四、自學指導：上章介紹了x2≡a(modm)的解數(shù)。設(shè)。顯然q的任意素因數(shù)a異于2，且是同余式的解。從而，這樣由費馬定理，有。例1：設(shè)p=4n+3是素數(shù)，試證當q=2p+1也是素數(shù)時，梅素數(shù)Mp不是素數(shù)。而不能有x2=a+py這樣可淘汰滿足y≡vi(mod g)的各個y的值。即計算=1或1 。這為我們提供了計算模p的平方剩余的方法，另一個為歐拉判別定理a ≡1(mod p)，這個定理的證明依賴于高次同余方程的素數(shù)模p，次數(shù)等于解數(shù)的條件，再結(jié)合歐拉定理即可得到，但缺點是計算量比較大。本章討論f(x)為一個整系數(shù)的二次三項式時情形。了解推可比符號的定義，性質(zhì)及功能，會解素數(shù)的模的二次同余方程。1+1≡1這一點和代數(shù)方程也一樣。 設(shè)f(x) ≡0(mod p)的解為x≡x1(mod p)為解。孫子定理為下面定理：（孫子定理）兩兩互素，則一次同余式組 的解為 其中對待定系數(shù)法和孫子定理要有深刻的理解。教材上有若干種求解方式，供讀者在同樣問題選擇使用。移項運算是傳統(tǒng)的，同余方程兩邊也可以加上模的若干倍。四、自學指導同余方程和不定方程一樣，我們同樣要考慮以下三個問題，即有解的條件，解數(shù)及如何求解，一般地說，對于一般的同余方程，由于僅有有限個解，只要把模m的一個完全剩余系一一代入驗算總解組則所需的結(jié)果。例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+62Y2）即11|（XY+13）因為0X，Y9， 所以有21 21+X+Y39，4 XY+13 22，由此可知21+X+Y=27，XY+13=11或21+X+Y=36，XY+13=22X+Y=6，XY=2或X+Y=15，XY=9，解得X=2，Y=4。q）=1,由條件q|2p1,即2≡1（mod q），又∵ （q,2）=1，2≡1（mod q）設(shè)i是使得2≡1（mod p）成立最小正整數(shù)若1ip，則有i|p則與p為素數(shù)矛盾∴ i=p, ∴ p|q1又∵ q1為偶數(shù)，2|q1,∴ 2p|q1,q1=2pk , 即q=2pk+1例4：證明13|42n+1+3n+2證：∵42n+1+3n+2≡4 一個整數(shù)被8，125整除的充要條件是它的末三位能被8，125整除。就歐拉定理、費爾馬小定理來講，它在某些形如a數(shù)的整除問題應(yīng)用起來顯得非常方便。另一方面，簡化剩余數(shù)也可從模m的一個完全剩余系中得到簡化剩余系，一組完全剩余系中與m互素的的數(shù)組成的φ(m)個不同數(shù)的集合稱為m簡化剩余系。為此對于同余的除法運算我們有二種除法：（i）模不改變的除法，若ak≡bk(mod m) ，(k,m)=1，則a≡b(mod m)(ii)模改變的除法, 若ak≡bk(mod m) (k,m)=d,則a≡b這一點讀者要特別注意。從同余的定理上看，同余和整除實際上是同一回事，故同余還有二個等價的定義：①用整除來定義即 m∣ab 。能判斷一組數(shù)是否構(gòu)成模m的一個完全剩余系或一個簡化剩余系。 x=1,y=5.例6：證明不定方程x22xy2+5z+3=0無整數(shù)解。1(m為整數(shù)) ， ∴N2=9m2177。證明不定方程無解的證明方法常采用以下形式：（反證法）若A有解A1有解A2有解……An有解，而An本身無解，這樣來構(gòu)造矛盾。上述解不定方程的方法叫因子分解法。在條件x0，y0，z0，（x，y）=1，2∣x的條件可以給出x2+y2=z2的通解公式，x=2ab，y=a2b2，z2=a2+b2，ab0 , (a ,b)=1，a ,b一奇一偶。它的根據(jù)是求（a ,b）時所得的結(jié)果。（1） 費爾馬無窮遞降法。216。例14. 試證明任意一個整數(shù)與它的數(shù)字和的差必能被9整除，并且它與它的數(shù)字作任意調(diào)后換后所成整數(shù)的差也能被9整除。由帶余數(shù)除法得 我們有由此及得,=注意到,若,則,則繼續(xù)對作同樣的討論，由輾轉(zhuǎn)相除法知，結(jié)論成立。例7. 證明2003|（20022002+200420042005）證：∵ 20022002=（20031）2002=2003M1+120042004=（2003+1）2002=2003M2+1∴20022002+200420042005=2003（M1+M21）由定義2003|（20022002+200420042005）例8. 設(shè)d(n)為n的正因子的個數(shù)， (n)為n的所有正因子之和，求d(1000)， (1000)。例2. 證明連續(xù)三個整數(shù)中，必有一個被3整除。對于較特殊的n，例如n！分解還是容易的。即任何大于1的整數(shù)一定存在一個素因數(shù)p 。當個數(shù)大于2時，上述式子不再成立。順便指出，若a∣c，b∣c，（a ,b）=1，則ab∣c是我們解決當除數(shù)為合數(shù)時的一種方法。讀者應(yīng)熟知常用的分類方法，例如把整數(shù)可分成奇數(shù)和偶數(shù)，特別對素數(shù)的分類方法。即當我們無法用整除語言來敘述或討論整除問題時，可以將其轉(zhuǎn)化為我們很熟悉的等號問題。能熟練求出二個整數(shù)的最大公因數(shù)和最小公倍數(shù)，掌握高斯函數(shù)[x]的性質(zhì)及其應(yīng)用。第四章：同余式（方程）（4學時）自學12學時同余方程概念孫子定理高次同余方程的解數(shù)和解法素數(shù)模的同余方程威爾遜定理。初等數(shù)論學習總結(jié)本課程只介紹初等數(shù)論的的基本內(nèi)容。第三章：同余（4學時）自學12學時同余的定義、性質(zhì)剩余類和完全剩余系歐拉函數(shù)、簡化剩余系歐拉定理、費爾馬小定理及在循環(huán)小數(shù)中的應(yīng)用習題要求：2，6；：1；：2，3； 1，2。認真體會求二個數(shù)的最大公因數(shù)的求法的理論依據(jù)，掌握素數(shù)的定義以及證明素數(shù)有無窮多個的方法。也為我們提供了解決整除問題的方法。同時也為我們建立同余理論建立了基礎(chǔ)。讀者必須注意定理成立的條件，也可以例舉反例來進行說明以加深影響。兩者的關(guān)系為a ,b∈N， [a ,b]=上述僅對二個正整數(shù)時成