1、第五章 二次同余式和平方剩余,一般二次同余式為 進而有 (a,p)=1 P=2時可直接驗證x=0，1是否是方程的解， 對一般奇素數(shù)有(p,2)=1,同余式兩邊同乘4a有 從而變成最簡形式 下面我們討論這一類方程什么時侯有解，有多少解，如何求解等問題.,1 歐拉判別條件 定義：m0,(a,m)=1,若對于整數(shù)a, 有解，則稱a是模m的平方乘余; 否則，稱a 是模m的平方非乘余。 對于 有下面的定理。,證：先證(3),設(shè) 是方程的解，則- 也滿足方程，但 不同余于- 關(guān)于模p,否則有 即 因為(p,a)=1,所以有 ,不可能，所以方程至少有兩解，又因 方程的數(shù)不超過次數(shù)，恰有兩解。,定理：（歐拉判

2、別定理）p2,(a,p)=1,則有 (1)a是模p的平方乘余的充要條件是 (2)a 是模P的平方非乘余充要條件是 (3)a是模p的平方乘余,則 有兩解,(1)因為(a,p)=1,由歐拉定理知 即有 即 或 但上兩式不能同時成立，否則有 又 若a 是模P的平方乘余，則 有兩解，由定理知 為p的倍數(shù),有 反之若 則由定理知 有解.,（2）若a 是模P的平方非乘余，則 不是P的倍數(shù)，即 不成立，只有 反之也對。,例：用歐拉判別定理判別 是否有解。 解：由歐拉判別定理 所以無解。 從上可知用歐拉判別定理判別當模比較大時，就比較麻煩，從理論上說a是否為平方乘余，只要在P的簡化系中去找即可，且若a是平方數(shù)

3、則一定為平方乘余，那么在P的簡化系中有多少個是平方乘余呢？我們有,定理：在模P的簡化系中，平方剩余和平方非剩余余各為 個 且 個平方乘余分別與 之一同余，而且僅與一數(shù)一同余。 證明如下:,證：由歐拉判別定理知平方剩余的個數(shù)是 的解數(shù)。但 其余式為0，由定理知 有 個解，即平方乘余的個數(shù)為 從而平方非剩余的個數(shù)為p-1- = 個。,又 中每一個數(shù)都是平方剩余，所以 有解，(i=1，2 ),且兩兩不同余，因為若則有 這是不可能的，所以 中兩兩不同余。,注：上述定理給出了找平方剩余的比比較簡單的辦法。 例1：求素數(shù)7的平方剩余和平方非剩余 解：因為1，4是平方數(shù)，所以是平方剩余，又9關(guān)于7同余于2，

4、所以2也是7的平方剩余，則在7的簡化系中已經(jīng)找到了3個平方剩余，則另外3個數(shù)3，5，6是7的平方非剩余。,常見素數(shù)的平方剩余和平方非剩余如下： 素數(shù) 平方剩余 平方非剩余 P=3， 1 2 P=5 1，4 2， 3 P=7 1，2，4 3，5，6 P=11 1，4，9，5，3 2，6，7，8，10 P=13 1，4，9，3，12，10 2，5，6，7，8，11,歐拉判別定理從理論上這對判別一般的a是否有解已經(jīng)是完善了，但缺點是計算量比較大。為了彌補計算量大的不足，我們要引進了勤讓德符號，使得判別更簡單。,2 勒讓德符號 定義：p是一個給定的奇素數(shù)，對于整數(shù)a定義勒讓德符號 例： 為了更方便地計

5、算勒讓德符號，我們給出其相關(guān)的性質(zhì)，即有下面的定理。,定理1：（1） （2） （3） （4） （5）,證：（1）由定義可得. （2）若P|a，則P|b，由定義有 又若（P，a）=1，則有 由于兩邊只能取1或-1，所以只能相等。 （3）由定義若 ，則有 則兩邊都為零相等 若 ， 則有 由于兩邊只能取1或-1，所以只能相等。,（4）顯然。 （5）由定義 由于兩邊只能取1或-1，所以有,定理2：設(shè)p是奇素數(shù)，則有,證：因為 把上述 個式子相乘得 因為 從而證明了結(jié)論。,定理3：（兩次互反律）設(shè)p，q是兩個不同的奇素數(shù)，則有 證：（略） 注：利用兩次互反律可以使求勒讓德符號變得更簡單。,例1：設(shè)p=4

6、n+3是素質(zhì)，試證當q=2p+1也是素數(shù)時，梅素數(shù)Mp不是素數(shù)。 證： q=8n+7, q|24n+3-1，即q |Mp， Mp不是素數(shù)。,例2：證明形如4m+1的素數(shù)有無窮多個。 證：假設(shè)形如4m+1的素數(shù)只有有限個，設(shè)為p1pk，顯然(2p1pk)2+1的最小素因數(shù)p是奇數(shù)，且p與p1pk不同 設(shè)p為4m+3形的素數(shù)，但p整除(2p1pk)2+1， 表明(2p1pk)2+10（mod p） 即x2(-1)(mod p)有解，即 ， 但 矛盾， p為4m+1形，這與4m+1的素數(shù)只有k個矛盾。,例3：證明不定方程x2+23y=17無解。 證：只要證x217(mod 23)無解即可， 171(

7、mod 4) x217(mod 23)無解，即原方程無解。,例4：若3是素數(shù)p平方剩余，問p是什么形式的素數(shù)？ 解： 由反轉(zhuǎn)定律 ， 注意到p3，p只能為 且 只能下列情況 或 或,3 雅可比符號 對于勒讓德符號 可以判別 是否有解，但對于 判別是否有解，理論上可化為 然后進行綜合判別，但這是不容易的，為此介紹一個更為實用的符號 定義：給定正奇數(shù)m= 對任意的整數(shù)a定義 稱 為雅可比符號,注：1、雅可比符號是勒讓德符號 的推廣。 2、雅可比符號為1時， 不一定有解。例 ,但 無解。 3、雅可比符號為-1時，則 一定無解。 因為若 =-1，則至少有一個i使得 =-1,即 無解，則 無解.,下面給

8、出雅可比符號的類似于勒讓德符號性質(zhì)，定理1 : (1) (2) (3) (4),定理2：設(shè)p是正奇數(shù)，則有 定理3：（兩次互反律）設(shè)p，q是兩個不同的正奇數(shù)，則有,關(guān)于雅可比符號這一些性質(zhì)在此就不一一證明了，關(guān)鍵是要用雅可比符號的性質(zhì)為計算勒讓德符號 提供方便，即我們可以在計算勒讓德符號時把其當成是雅可比符號，這樣就不要求是奇素數(shù)的條件了。 來判別下面的方程是否有解。,例1： 判別 是否有解？ 解：因為563=7*80+3,又 所以原方程無解。 注：在計算勒讓德符號 時，可以不要管143是否為素數(shù)而直接用二次互反律，為計算提供了方便。,例2：若 則p 不能寫成 的形式 證：若p= ,則有若P|

9、x, 則有 p|y 于是可設(shè) 于是有 ，不可能。 所以有(p,x)=1,則有 矛盾，所以假設(shè)錯誤， p 不能寫成 的形式。,例3：證明：形如8k+7的素數(shù)有無窮多個。 證：假設(shè)形如8k+7的素數(shù)只有有限多個，設(shè)為 共k個，記 設(shè)q是N的素因數(shù)，則有 則q=8k+1或8k+7.若N的所有素因數(shù)都是8k+1的形式，則N也是8k+1的形式，但任何數(shù)的平方用8模同余1 ，有 有矛盾， 說明N至少有一個8k+7的素因數(shù)q,顯然q不同于 (i=1,2,.k),這與8k+7的素因數(shù)只有k個矛盾，所以假設(shè)錯誤，即形如8k+7的素數(shù)有無窮多個。,4 合數(shù)模兩次同余方程 下面討論 有解的條件和解數(shù) 設(shè) ， 為奇素

10、數(shù)。 首先上述方程等價于方程組 （*）,定理1：設(shè)P是奇素數(shù)，（a，p）=1，則有 （1）若 =-1，則 無解。 （2）若 =1，則 有兩解。,證（1）顯然 （2）若 有解，則 有解，所以有 =1。 反之，若 =1，則 恰有兩解，記為 ，由于（p，a）=1,所以 又因p為奇素數(shù)，所以有(p，2）=1則 ，所以有 由上一章的定理知 有解，并由此可得到得 的兩解。,定理2：若(a,2)=1，則 （1） =1時， 有一解 （2） =2時， 有解的充要條件是a=4k+1，且若有解，則有兩解。 （3） 時，則 有解的充要條件是a=8k+1，且若有解，則有四解。,證：若 有解，則x為奇數(shù)，設(shè)x=1+2t代入得 當 =2時，則有 當 時，則 當 =1時，顯然 是方程的解 反之若上述條件成立，則有 當 =1時， 有解 當 =2時， 有解,當 時， （1）當 =3， 時， 有解 （2）當 3時，考慮 的x可以寫成 的形式，代入 有 即 ， 即 是滿足 的解。,同理 的解為 同樣的方法有 對一切 3時有 的解為 對模 來說是四個解為,例：解方程 解：因為57=7*8+1，且 =6，所以由定理知有四解。將 代入 有 所以 代入 有 有 所以 代入 得 即 所以有 是 的解，