1、電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余第七章第七章平方剩余平方剩余電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余第七章第七章 平方剩余平方剩余7.1平方剩余（平方剩余（熟練熟練）7.2勒讓德符號（勒讓德符號（掌握掌握）7.3雅可比符號（雅可比符號（掌握掌握）電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余7.1 平方平方剩余剩余定義定義7.1.1設設p是奇素數，即大于是奇素數，即大于2的素數，的素數，如果二次同

2、余式如果二次同余式x2 a (mod p)，(a，p) = 1 (1) 有解，則有解，則a稱為模稱為模p的的平方剩余平方剩余，否則否則a成為成為模模p的的平方非剩余平方非剩余 之所以規定之所以規定p是大于是大于2的素數，是因為的素數，是因為p = 2時解二次同余式時解二次同余式(1)非常容易在有些書籍非常容易在有些書籍中，平方剩余和平方非剩余又分別稱為中，平方剩余和平方非剩余又分別稱為二二次剩余次剩余和和二次非剩余二次非剩余電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余例例7.1.1求出求出p = 5，7時的平方剩余和

3、平方非剩余時的平方剩余和平方非剩余解解p = 5時，因為時，因為12 1 (mod 5)，22 4 (mod 5)，32 4 (mod 5)，42 1 (mod 5)，所以所以1，4是模是模5的平方剩余，而的平方剩余，而2，3是模是模5的平方非剩余的平方非剩余p = 7時，因為時，因為12 1 (mod 7)，22 4 (mod 7)，32 2 (mod 7)，42 2 (mod 7)，52 4 (mod 7)，62 1 (mod 7)，所以所以1，2，4是模是模7的平方剩余，而的平方剩余，而3，5，6是模是模7的平方非的平方非剩余剩余電子科技大學電子科技大學 計算機科學與工程學院計算機科學與

4、工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余定理定理7.1.1設設p是奇素數在模是奇素數在模p的簡化剩余系中，有的簡化剩余系中，有 個平方剩余，個平方剩余， 個平方非剩余個平方非剩余證明取模證明取模p的的最小絕對簡化剩余系最小絕對簡化剩余系則模則模p的全部平方剩余為的全部平方剩余為由于由于( a)2 a2 (mod p)12p 12p 1111, (1), 2, 1,1,2,1,.2222pppp222222221111() , (1) ,( 2) ,( 1) ,1 ,2 ,(1) ,() .2222pppp電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院

5、UESTC Press 第七章 平方剩余平方平方剩余剩余于是模于是模p的全部平方剩余為的全部平方剩余為現在證明這個現在證明這個 平方剩余兩兩不同，用反證法平方剩余兩兩不同，用反證法假設假設i2 j2 (mod p)，i j，1 i，j ，則則(i + j)(i j) 0 (mod p)，p (i + j)(i j)，因為因為p是素數，于是是素數，于是p (i + j)或或p (i j)，當當i j，1 i，j 時這顯然是不可能的時這顯然是不可能的，故證得，故證得2222111 ,2 ,(1) ,() .22pp12p12p12p電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院

6、UESTC Press 第七章 平方剩余平方平方剩余剩余所以在模所以在模p的簡化剩余系中，有的簡化剩余系中，有 個平方剩余，個平方剩余，同時有同時有 個平方非剩余個平方非剩余12p1122ppp電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余 以后我們求模以后我們求模p的平方剩余時，就可以只計算下列的平方剩余時，就可以只計算下列數了：數了：12，22， 21() (mod)2pp電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余例例7.1.2求出求出

7、p = 11，17時的平方剩余和平方非剩余時的平方剩余和平方非剩余解解p = 11時：時：12 1 (mod 11)，22 4 (mod 11)，32 9 (mod 11)，42 5 (mod 11)，52 3 (mod 11)，所以所以1，3，4，5，9是模是模11的平方剩余，而的平方剩余，而2，6，7，8，10是模是模11的平方非剩余的平方非剩余p = 17時：時：12 1 (mod 17)，22 4 (mod 17)，32 9 (mod 17)，42 16 (mod 17)，52 8 (mod 17)，62 2 (mod 17)，72 15 (mod 17)，82 13 (mod 17)

8、，所以所以1，2，4，8，9，13，15，16是模是模17的平方剩余，而的平方剩余，而3，5，6，7，10，11，12，14是模是模17的平方非剩余的平方非剩余電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余定理定理7.1.2（歐拉判別法歐拉判別法）設）設p是奇素數，是奇素數，(a，p) = 1a是模是模p平方剩余的充分必要條件是平方剩余的充分必要條件是a是模是模p平方非剩余的充分必要條件是平方非剩余的充分必要條件是121(mod)pap121(mod)pap 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工

9、程學院UESTC Press 第七章 平方剩余平方平方剩余剩余證明定理第證明定理第1部分證明：部分證明：必要條件證明：必要條件證明：因為因為a是模是模p的平方剩余，則存在的平方剩余，則存在b, 使使 b2 a (mod p)充分條件證明：充分條件證明：由于由于,由定理由定理6.4.4，同余式，同余式112122()1(mod)pppabbp12(1) ()ppxxx電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余有有 個解，可以驗證所有的平方剩余正好就是它的個解，可以驗證所有的平方剩余正好就是它的 個解于是當個解于是當時

10、，時，a是模是模p平方剩余平方剩余1210(mod)pxp 12p121(mod)pap12p 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余定理第定理第2部分證明：部分證明：對于任意對于任意a GF(p)*，有，有ap 1 1 (mod p)，即即 ap 1 1 0 (mod p)，由于由于p是素數，則是素數，則即即11221(mod)1(mod)ppapap 或111221(1)(1)0(mod)pppaaap 1122(1)0(mod)(1)0(mod)ppapap或電子科技大學電子科技大學 計算機科學與工程學院

11、計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余由定理的第由定理的第1部分，部分，a是模是模p平方剩余的充分必要條件平方剩余的充分必要條件是是那么那么a是模是模p平方非剩余的充分必要條件就是平方非剩余的充分必要條件就是定理證畢定理證畢121(mod)pap121(mod)pap 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余例例7.1.31）判斷）判斷3是不是模是不是模17的平方剩余？的平方剩余？解因為解因為32 9 (mod 17)，34 81 4 (mod 17)，所以所以3是模是模17

12、的的平方非剩余平方非剩余17 18442333 31 （mod p）電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余平方平方剩余剩余2）7是不是模是不是模29的平方剩余？的平方剩余？解因為解因為72 = 49 9 (mod 29)，74 ( 9)2 81 6 (mod 29)，78 ( 6)2 36 7 (mod 29)， = 714 =78 74 72 7 ( 6) ( 9) 1 (mod 29)，所以所以7是模是模29的平方剩余的平方剩余29 127電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Pre

13、ss 第七章 平方剩余7.2 勒讓德符號勒讓德符號定義定義7.2.1設設p是奇素數，是奇素數，a是整數是整數勒讓德勒讓德（Legendre）符號）符號定義如下：定義如下：由歐拉判別法我們立即得到下面的定理由歐拉判別法我們立即得到下面的定理定理定理7.2.1勒讓德符號勒讓德符號 具有下列性質：具有下列性質： 1,ap1apapp a.ap 是模 的平方剩余；， 是模 的非平方剩余；0， 能夠被 整除：12(mod)paapp12111)1,( 1).ppp 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余勒讓德符號勒讓德符號2）如果）如果

14、a b (mod p)，則，則3）4）如果）如果(a，p) = 1，則，則5） abppapapp21ap1212.nna aaaaapppp電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余勒讓德符號勒讓德符號性質性質5證明：證明：因為因為 于是于是1122121112221212.(mod)pnnpppnna aaa aapaaaaaapppp1212,1, 2,nna aaaaakp kpppp 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余勒讓德符號勒讓德符號 由于由于p

15、是奇素數，是奇素數，p 2，而勒讓德符號只能取值，而勒讓德符號只能取值0， 1，所以上式中，所以上式中k只可能等于只可能等于0，所以我們有，所以我們有1212.nna aaaaapppp電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余定理定理該結論可以作為勒讓德符號的該結論可以作為勒讓德符號的第第6項性質項性質2182( 1)pp 定理定理7.2.2（二次互反律）如果（二次互反律）如果p，q都是奇素數，都是奇素數，(p，q) = 1，則，則1122( 1)pqqppq 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院U

16、ESTC Press 第七章 平方剩余二次互反律二次互反律勒讓德符號性質勒讓德符號性質7：證明：分別把證明：分別把p 1 (mod 8)，p 3 (mod 8)，代入代入 式中便得式中便得11mod8213mod8ppp ，如果（），如果（）2182( 1)pp 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余二次互反律二次互反律例例7.2.1判別判別286是否是模是否是模563的平方剩余的平方剩余解解563是奇素數，又是奇素數，又286 = 2 11 13，于是，于是而而 ，（因為，（因為563 3 (mod8)）（因為（因為563

17、4 (mod13)）2862111356356356356321563 563 1 13 122135634( 1)15631313 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余二次互反律二次互反律（因為（因為563 2 (mod11)）則則故故286是模是模563的平方非剩余的平方非剩余563 1 11 122115632( 1)15631111 2861563 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余二次互反律二次互反律例例7.2.2判斷判斷x2 = 137 (m

18、od 227)是否有解是否有解解解227是奇素數，又是奇素數，又137 90 2 32 5 (mod227)，則，則而而21371235227227227227227 ,2123111227227227 () 227 1 5 122522721122755電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余二次互反律二次互反律故故原同余式無解原同余式無解1371227 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余7.3 雅可比符號雅可比符號定義定義7.3.1設設m是大于是大于1的

19、奇數，的奇數，m = p1p2pr是是m的素數分解，的素數分解，a是整數雅可比符號定義如下：是整數雅可比符號定義如下：其中其中 是勒讓德符號是勒讓德符號當當m是一個奇素數時，雅可比符號和勒讓德符號是一個奇素數時，雅可比符號和勒讓德符號是一致的雅可比符號有著和勒讓德符號相似的是一致的雅可比符號有著和勒讓德符號相似的下列性質：下列性質： 12raaaamppp iap電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余雅可比符號雅可比符號1）2）如果）如果a b (mod m)，則，則3）如果）如果(a，m) = 1，則，則4）5）6）7） 1

20、1mabmm 21amamamm1212nna aaaaammmm1211()mm21821()mm 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余證明性質證明性質6證明：證明：現在只需證明現在只需證明而而故得證故得證112121111( 1)riiprmppp 111(mod 2)22riipm 121122rp ppm 12111(12)(12)(12)12222rppp 11(mod 2)2riip ，故性質6證得電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余性質性質7

21、證明：證明：現在只需證明現在只需證明而而故性質故性質7證得證得2118122222( 1)riiprmppp 22111(mod 2)88riipm 2222121188rp ppm 22212111(18)(18)(18)18888rppp 211(mod 2)8riip 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余雅可比符號雅可比符號定理定理7.3.1如果如果m，n都是大于都是大于1的奇數，則的奇數，則證明證明如果如果(m，n) 1，得到，得到定理成立現在假設定理成立現在假設(m，n)=1設設n = q1q2qs是是n的素數分解

22、，則的素數分解，則1122( 1)mnnmmn 0nmmn111rrsjiijiiqnnmpp 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余11112211( 1)rsjiijqprsiijjpq 112211( 1)jiqprsiijjpq rsjii=1 j=1q -1p -122m= (-1)n111(mod 2)22riipm 111rrsjiijiiqnnmpp 電子科技大學電子科技大學 計算機科學與工程學院計算機科學與工程學院UESTC Press 第七章 平方剩余雅可比符號雅可比符號我們有我們有故故1111111111(mod 2)222222rsrsjjiiijijqqppmn 1122( 1)mnnmmn 電子科技