第三章二次剩余

1、第三章第三章 二次剩余二次剩余本章內(nèi)容一、二次剩余的概念一、二次剩余的概念二、模為奇素數(shù)的平方剩余與平方非剩余二、模為奇素數(shù)的平方剩余與平方非剩余 三、勒讓德符號三、勒讓德符號 四、雅可比符號四、雅可比符號五、小結(jié)五、小結(jié)重點重點：二次同余方程有解的判斷與求解二次同余方程有解的判斷與求解3.1 二次剩余的概念二次同余式的一般形式是二次同余式的一般形式是)(mod02mcbxax)(mod0ma 其中其中m是正整數(shù)，是正整數(shù)， 。上式等價于同余式上式等價于同余式2(mod)ydmacbdbaxy4,22)(mod2max1),(ma 定義定義1 設(shè)設(shè)m是正整數(shù)，若同余式是正整數(shù)，若同余式有解，則

2、有解，則a叫做模叫做模m的的平方剩余平方剩余(或二次剩余或二次剩余)，記為，記為QR；否則否則a叫做模叫做模m的的平方非剩余平方非剩余(或二次非剩余或二次非剩余)，記為，記為NR 。例例1 1 分別求出模分別求出模1111，1212的二次剩余和二次非剩余。的二次剩余和二次非剩余。解：解： 模模1111的二次剩余是：的二次剩余是：1 1，3 3，4 4，5 5，9 9； 二次非剩余是：二次非剩余是：2 2，6 6，7 7，8 8，1010。模模1212的二次剩余是：的二次剩余是：1 1； 二次非剩余是：二次非剩余是：5，7，11。例例2 求滿足同余式求滿足同余式 的所有的點。的所有的點。 )7(

3、mod232xxy解：解： 模模7的二次剩余是：的二次剩余是：1，2，4；二次非剩余是：；二次非剩余是：3，5，6。 對對 ，分別求出，分別求出 對應(yīng)的的值為對應(yīng)的的值為 )7(mod6 , 5 , 4 , 3 , 2 , 1 , 0 xy)7(mod0 x)7(mod22y)7(mod4 , 3y)7(mod1x)7(mod42y)7(mod5 , 2y)7(mod3x)7(mod42y)7(mod5 , 2y)7(mod4x)7(mod02y)7(mod0y)7(mod6x)7(mod02y)7(mod0y)7(mod2x)7(mod52y無解無解)7(mod5x)7(mod62y無解無解

4、3.2 模為奇素數(shù)的平方剩余與平方非剩余2(mod11)xa 例例如如： 111,2,3, 4,5 .取取模模的的一一個個簡簡化化系系為為可以驗證：可以驗證：11 111 12211(mod11); ( 2)1(mod11);11 111 122( 1)1(mod11); 21(mod11); 而而11 111 111 122231(mod11); 41(mod11);51(mod11).11 111 122( 3)1(mod11);( 4)1(mod11); 11 12( 5)1(mod11). 模模11的平方剩余為的平方剩余為1，-2，3，4，5；平方非剩余為平方非剩余為-1，2，-3，-

5、4，-5.2(mod11)xa 例例如如：模模11的平方剩余為的平方剩余為1，-2，3，4，5.22(mod11)3,8(mod11);xx 方方程程的的解解為為：21(mod11)1,10(mod11);xx方方程程的的解解為為：23(mod11)5,6(mod11);xx方方程程的的解解為為：24(mod11)2,9(mod11);xx方方程程的的解解為為：25(mod11)4,7(mod11).xx方方程程的的解解為為：例1 利用定理判斷補充 模重復平方計算法補充 模重復平方計算法 符號表示如下：QR QR=QR QR NR=NRNR NR=QR 若用數(shù)字代替符號QR與NR，易見：QR如

6、同+1 NR如同-1 定理定理2 設(shè)設(shè)p是奇素數(shù)，則模是奇素數(shù)，則模p的簡化剩余系中平方剩余與的簡化剩余系中平方剩余與平方非剩余的個數(shù)各為平方非剩余的個數(shù)各為 ，且，且 個平方剩余與序列個平方剩余與序列中的一個數(shù)同余，且僅與一個數(shù)同余。中的一個數(shù)同余，且僅與一個數(shù)同余。21p21p222)21( ,2 ,1p 7,1,2,3 .p 例例如如：取取則則其其簡簡化化系系為為模模7的平方剩余為的平方剩余為1，2，-3；平方非剩余為平方非剩余為 -1，-2，3.22211 (mod7);23 (mod7); 32 (mod7). 且且有有：3.3 勒讓德符號勒讓德符號利用歐拉判別條件雖然可以判定利用歐

7、拉判別條件雖然可以判定 x2 a (mod p) 的解的存在性，但對較大的素數(shù)模，實際運用很困難。的解的存在性，但對較大的素數(shù)模，實際運用很困難。通過引入勒讓德符號，本節(jié)給出了較方便的判別方法。通過引入勒讓德符號，本節(jié)給出了較方便的判別方法。目的：目的：快速判斷整數(shù)快速判斷整數(shù)a是否為素數(shù)是否為素數(shù)p的平方剩余。的平方剩余。, 0, 1, 1paappapa|若的平方非剩余是模若的平方剩余是模若 定義定義 設(shè)設(shè)p是素數(shù)是素數(shù), 定義勒讓德定義勒讓德Legendre符號如符號如下：下：123451111 0.55555( )( )( )( )( ) ，如如, 1, 1與與4 4是模是模5 5的平

8、方剩余，的平方剩余，2 2與與3 3是模是模5 5的平方非剩余，的平方非剩余，所所以以有有由此定義，歐拉判別法則可以表示成如下形式：由此定義，歐拉判別法則可以表示成如下形式： 定理定理2 設(shè)設(shè)p是奇素數(shù)，則對任意整數(shù)是奇素數(shù)，則對任意整數(shù)a，有，有 )(mod21papap定理定理1 1 Legendre符號基本性質(zhì)符號基本性質(zhì) 11 (1,2,)22 (Gauss ( 1) .)mpaa , ppakk =ppmap 設(shè)設(shè) 是是奇奇素素數(shù)數(shù), , 是是整整數(shù)數(shù), ,如如果果整整數(shù)數(shù)中中模模 的的最最小小正正剩剩余余大大于于的的個個數(shù)數(shù)是是, ,則則 引引理理( () ), ,2p于于的的最最

9、小小正正剩剩余余 則則121,1,2,2tpa aaaaa 證證 設(shè)設(shè)是是整整數(shù)數(shù)關(guān)關(guān)2pp于于模模 的的小小于于的的最最小小正正剩剩余余, ,12 ,mb bb是是一一切切大大1211!(1)(2)()22pppaaaa 1212 (mod)tma aa b bbp 1212( 1)()()() (mod)mtma aapbpbpbp ()(mod)jjpbbp 0 (mod)jiijpakakakakp或或111.22ijppkkp因因為為 12, mpbpbpbp是是模模 兩兩兩兩不不同同余余的的. .1212, tma aapbpbpbp易易知知是是模模 兩兩兩兩不不同同余余的的. .

10、12,ta aap事事實實上上, ,是是模模 兩兩兩兩不不同同余余的的, ,若若有有 (mod),jipbap ,ijk k則則有有使使( , )1, 0 (mod),ijp akkp因因所所以以這這不不可可能能, ,12121,1,2,2tmpa aapbpbpb 是是的的一一1211!(1)(2)()22pppaaaa 1212(1)()()()mtma aapbpbpb1(1)! (mod)2mpp 于于是是1(, )1, 1,2,2pak pk 因因為為1 2p 所所以以個個整整數(shù)數(shù)個個排排列列. .12 (1) (mod)pmaapp 因因此此引引理理得得證證. .1,ap 注注意意

11、到到 ( 1) .map 故故 212118 (i) ( 1)(ii) ( ,2)1, ( 1)pkpakpppapap 設(shè)設(shè) 是是奇奇素素數(shù)數(shù)定定理理若若3 32 2則則 , ,1,0,1,2,2kkakpakprrp kp 證證 因因11,2,2pk 對對求求和和 有有111222111()pppkkkkakakprp12211118ptmijkijpakapabp 即即 121111()2ptmmijjkijjakpapbbmpp 由引理由引理的證明的證明12211128pmjkjakppmpbp 122111, (1)28pmjkjpakapmpbp 因因此此1122111(1)(1)

12、2ppmjkkjakakmpm pbpp12211 (1) (mod2)8pkpakamp 所所以以2 2的倍數(shù)的倍數(shù)12,00,akpapp 若若則則21 (mod2)8pm 于于是是212 8pmr 22112222( 1)( 1)( 1)pprmp 由由引引理理121 (mod2)pkakamp 若若 為為奇奇數(shù)數(shù), , 則則112211 +2( 1)( 1)( 1)ppkkakaktppmap 由由引引理理121 +2pkakmtp 即即 證明：證明：由由 定理定理3 有有1122, ( 1).pqqppq 顯顯然然 只只需需證證明明等等式式二次互反律的證明：二次互反律的證明：1122

13、11, ( 1)pqhkqhpkpqqppq 于于是是112211 ( 1), ( 1)pqhkqhpkpqqppq 為為此此 只只需需證證明明, ,11221111 22pqhkqhpkpqpq1111 , 22pqpq令令22pq考考察察長長為為, ,寬寬為為 的的矩矩形形內(nèi)內(nèi)的的整整點點個個數(shù)數(shù). .:如如下下圖圖11.OABCp q一一方方面面, ,矩矩形形內(nèi)內(nèi)所所含含的的整整數(shù)數(shù)點點個個數(shù)數(shù)為為qhSTp另另一一方方面面, ,在在直直線線上上, ,整整點點個個數(shù)數(shù)為為, ,故故在在三三角角1(,0)A p1(0,)Cq(0,0)O(,)2 2p qBqyxp xy( ,0)S hTA

14、C1(,0)A p1(0,)Cq(0,0)O(,)2 2p qBqyxp xy( ,0)S hTAC11phqhOABp 形形內(nèi)內(nèi)的的整整點點個個數(shù)數(shù)為為. .11.qkpkOBCq 同同理理, ,三三角角形形內(nèi)內(nèi)的的整整點點個個數(shù)數(shù)為為(0, )NkMOABC故故矩矩形形內(nèi)內(nèi)的的整整點點1111pqhkqhpkpq 11111111 .22pqhkqhpkpqp qpq從從而而至至此此, ,二二次次互互反反律律得得證證. . ,qyxp 因因為為直直線線上上無無整整點點個個數(shù)數(shù)為為例例 計算如下勒讓德符號的值。計算如下勒讓德符號的值。 ,322,171732271372003911(1) (

15、2) (3) nmm是否為素數(shù)是否為素數(shù)q=0q=1q=-1q=2out:01停止停止否否是，計算是，計算nmodm=q218( 1)m 12( 1)m返回返回1212rkkkrqppp121111()222212( 1)ipppmimmmpppikkk,21riikkk,21為奇數(shù)；為奇數(shù)；為偶數(shù)。為偶數(shù)。 1 ,3p求求所所有有奇奇素素數(shù)數(shù)它它以以 為為其其例例二二次次剩剩余余. .31:p 即即求求滿滿足足條條件件的的分分析析所所有有奇奇素素數(shù)數(shù). .3 1 3.ppp解解 設(shè)設(shè) 是是奇奇素素數(shù)數(shù), ,易易知知滿滿足足條條件件的的由由二二次次互互反反律律123( 1)3ppp 121,

16、1 (mod4)( 1)1, 1 (mod4)ppp 當當因因 當當11, 1 (mod6)3311, 1 (mod6)3ppp 當當當當1 (mod4)1 (mod4)31 1 (mod6)1 (mod6)ppppp 所所以以或或311 (mod12) 1 (mod12)ppp 即即 或或 3 1 (mod12)pp 故故 是是模模 二二次次剩剩余余的的充充要要條條件件是是2 ,.1,dpdp 設(shè)設(shè) 是是奇奇素素數(shù)數(shù)是是整整 例例數(shù)數(shù) 如如果果則則22 ,ppxdy假假若若 有有表表達達式式( , )1.dp dp 證證 由由題題設(shè)設(shè)1 1知知, ,22 |, |.p xp xpdy 若若則

17、則( , )1, |.p dp y 因因所所以以2222|,|,pxpy于于是是有有222|,pxdyp從從而而 這這不不可可能能. .|,( , )1.pxp x 故故于于是是( , )1.p y 進進而而2221ddydyxppppp此此時時與與題題設(shè)設(shè)矛矛盾盾. .22pxdy 一一定定不不能能表表示示為為的的形形式式. .對于奇素數(shù)對于奇素數(shù)p，利用計算，利用計算Legendre符號可以判定方程符號可以判定方程x2 a (mod p) (1)是否有解。是否有解。對于一般的正整數(shù)對于一般的正整數(shù)m， 如何判定方程如何判定方程是否有解呢？是否有解呢？x2 a (mod m) (2) 四、雅

18、可比符號對于一般的正整數(shù)對于一般的正整數(shù)m，如果它的標準分解式是，如果它的標準分解式是1212kkmppp 那么判定方程那么判定方程 x2 a (mod m) (2)是否有解，是否有解，可歸結(jié)為對形如方程可歸結(jié)為對形如方程x2 a (mod p) (1) 的可解性判定。的可解性判定。 因此，在理論上，利用因此，在理論上，利用Legendre符號可以判定符號可以判定方程方程(2)是否有解。是否有解。 但是，寫出正整數(shù)的標準分解式常會遇到實際困難，但是，寫出正整數(shù)的標準分解式常會遇到實際困難， 所以利用所以利用LegendreLegendre符號判定方程符號判定方程(2)(2)的可解性并不容的可解

19、性并不容易實現(xiàn)。易實現(xiàn)。 例如，取例如，取m = 45 = 3 3 5，則，則251822222( 1)1453355( ) ( )( )( ) ( ) ，3 1 5 12228282828352( 1)145335533( ) ( )( )( ) ( )( ) ( ) . .rpapama1rppm1ipa 定義定義 設(shè)設(shè) 是奇素數(shù)是奇素數(shù) 的乘積。對任意整的乘積。對任意整數(shù)數(shù) ，定義雅可比，定義雅可比(Jacobi)符號為符號為()iap其其中中右右端端的的（1 i k）是）是Legendre符號。符號。 例如，取例如，取m = 45 = 3 3 5，則，則251822222( 1)145

20、3355( ) ( )( )( ) ( ) ，3 1 5 12228282828352( 1)145335533( ) ( )( )( ) ( )( ) ( ) . .當當m為奇素數(shù)時，則上式為勒讓德符號。為奇素數(shù)時，則上式為勒讓德符號。 注意注意：(1) 當當m是奇素數(shù)時，是奇素數(shù)時，Jacobi符號就是符號就是Legendre符號。符號。 前者是前者是后者的推廣。后者的推廣。 (2) 雅可比符號為雅可比符號為1時，不能判斷時，不能判斷a是否為模是否為模m的平方的平方剩余。例如剩余。例如333( 1)( 1)1119717 因為因為 ，而同余式組，而同余式組 的每個同的每個同余式都無解，所以

21、余式都無解，所以3是模是模119的平方非剩余。的平方非剩余。177119)17(mod3)7(mod322xx 如果如果 ，則，則 ； ( ,)1a m 20am設(shè)設(shè)m是奇數(shù)，則雅可比符號有以下性質(zhì)：是奇數(shù)，則雅可比符號有以下性質(zhì)：1),(ma122mama ，如果，如果 ，則，則 ； mbmamab(3)mamma(2) ；11m(1)21) 1(1mm，81) 1(2mmm(4)(5) 設(shè)設(shè)m,n都是奇數(shù)，則都是奇數(shù)，則 。nmmnnm2121) 1(12, 2,rmp ppmN NZ理理 若若，則則得得引引，使使221111112,2.2288rriiiippmmNN121122rmp

22、pp 證證明明：12111(12)(12)(12)12222rppp 1122riipN 2222121188rmp pp 22212111(18)(18)(18)18888rppp 21128riipN 定理定理1 1 設(shè)設(shè)m = p1p2pk是奇數(shù)，其中是奇數(shù)，其中p1, p2, pk是素數(shù)，是素數(shù)，則下面的結(jié)論成立：則下面的結(jié)論成立：121(1)( 1);()mm 2182(2)( 1).( )mm 12( 1);m 111()()kiimp 證證明明：12111222( 1)kppp 122( 1)mN 122( )( )kiimp 22212111888( 1)kppp 218( 1

23、).m 定理定理2 2 設(shè)設(shè)m，n是大于是大于1的奇整數(shù)，則的奇整數(shù)，則1122( 1)( )( )mnnmmn 利用以上定理，我們可以很容易地計算利用以上定理，我們可以很容易地計算Jacobi符符號，特別是號，特別是Legendre符號的數(shù)值。但是，必須注意，符號的數(shù)值。但是，必須注意，如同在定義的注如同在定義的注2中指出的，在判斷方程中指出的，在判斷方程(2)的可解的可解性時，性時，Legendre符號和符號和Jacobi的作用是不一樣的。的作用是不一樣的。 方程方程(2)(2)有解。有解。對于一般的正奇數(shù)對于一般的正奇數(shù)m來說，來說， = 1并不能保證并不能保證()am)563(mod2862x例例 判斷同余式是否有解？判斷同余式是否有解？563 563 1143 1 563 1822143 122862143563( 1)( 1)56356356314391( 1)1143143 解：不用考慮解：不用考慮563是否為素數(shù)，直接計算雅可比符號是否為素數(shù)，直接計算雅可比符號:所以同余式無解。所以同余式無解。 當當n是合數(shù)的時候，若（是合數(shù)的時候，若（a/n）=1，則，則a不一定是模不一定是模n的二的二次剩余。定義次剩余。定義 |( , )1,nQaa na是模n的二次剩余 |1