1 115.3 勒让德符号5.3 勒让德符号利用欧拉判别条件虽然可以判定利用欧拉判别条件虽然可以判定 x2 a (mod p)的解的存在性，但对较大的质数模，实际运用很困难。通过引入勒让德符号，本节给出了较方便的判别方法。的解的存在性，但对较大的质数模，实际运用很困难。通过引入勒让德符号，本节给出了较方便的判别方法。2一、Legendre符号一、Legendre符号定义 给定奇素数定义 给定奇素数p，对于整数，对于整数a，定义，定义Legendre符号为符号为011( )p a aappap ，；， 是 的平方剩余；， 是 的平方非剩余.如, 1与4是模5的平方剩余，2与3是模5的平方非剩余， ，；， 是 的平方剩余；， 是 的平方非剩余.如, 1与4是模5的平方剩余，2与3是模5的平方非剩余，所以有所以有 123451111 0.55555( )( )( )( )( ) ， ，3二、基本性质二、基本性质1 2(1) ()(mod );paapp 1 211(2) ()1,()( 1);ppp 1 1(3)(mod )()();aaaappp1212(4) ()()()();nna aaaaa pppp2 (5) ()(),.abapbpp ?41 2(1) ()(mod )paapp 011( )p a aappap ，；， 是 的平方剩余；， 是 的平方非剩余.，；， 是 的平方剩余；， 是 的平方非剩余.| ,pa若显然成立；若显然成立；1 21;p apa 若 是 的平方剩余，则若 是 的平方剩余，则1 21.p apa 若 是 的平方非剩余，则若 是 的平方非剩余，则1 211(2) ()1,()( 1)ppp (1)的特例. (1)的特例.:(2)1;(3)41,pm 注式说明 永远是平方剩余式说明当时1,43(41), 1.pmm是平方剩余 当或时是平方非剩余2 251 1(3)(mod )()()aaaappp1(mod )aap 11.paapaa同时整除 ， ；或者 同时不整除 ，同时整除 ， ；或者 同时不整除 ，1 21(mod ).p apap 若 为 的平方剩余，则有若 为 的平方剩余，则有11(mod )aapaapq 11 22 1()pp aapq 所以，所以，1 2p a 1(mod ).p 1ap即 也为 的平方剩余.即 也为 的平方剩余.61212(4) ()()()()nna aaaaa pppp 12()()()(mod )naaapppp 1 122 12()()p n na aaa aap 证：证：111 222 12pppnaaa 1212()()()()nna aaaaa pppp又和的取值只有又和的取值只有0，1，且，且p2，故得证。，故得证。72 (5) ()(),abapbpp ()(mod )app 22 ()()()abab ppp 证明：证明：?1 22()()pabp 1()pabp 8定理1定理1下面的结论成立：下面的结论成立：21 82(1)( 1)pp ； ；1 1(2)( , )1,( 1).2lknk papaa plp 若 为奇数，则，其中 若 为奇数，则，其中11(mod8)2 13(mod8).p pp ， 当，即， 当注：定理1给出了判断平方剩余的另一方法。 ， 当，即， 当注：定理1给出了判断平方剩余的另一方法。271 82( 1)1277 例如：由是 的平方剩余；例如：由是 的平方剩余；2111 82( 1)121111 由不是的平方剩余.由不是的平方剩余.3 391 1(2)( , )1,( 1).2lknk papaa plp 若 为奇数，则，其中若 为奇数，则，其中11,5.pa例如：取例如：取511511lkinkk p 001124511是的平方剩余;是的平方剩余;11,7.pa 取取511711lkknkk p 011237711不是的平方剩余.不是的平方剩余.101(1)由定理 的式立刻得出81,2,83,2pmpm 当时是平方剩余 当时推论是平方非剩余.1例 判断下列同余方程是否有解.2(1)350(mod7);xx 2(2)57110(mod23).xx 22:(1)35105xxxx 解22(5)55(mod7),x 25,20(mod7),yxy 令则原方程化为1121(mod7).y 即 -17-1 22-1-1()(-1),()(-1)1,7pp 21(mod7),.y 故无解 则原方程也无解22(2)571153035(mod23),xxxx (5,23)1, 故原方程等价于2267(3)160(mod23),xxx 23,16(mod23).yxy 令则原方程化为216(mod23),.y 易知有解 从而原方程有解122,n例 设 是整数2:141.nm 证明的任何奇因数都是的形式:,证明 由于奇数都可表示成奇素数之积 而且任意多个4141.mm 形如的整数之积也具有的形式 我们只需2:1,41.pnpm 证明 若素数 是的因数 则 具有的形式22|1,1(mod ),-1,p nnpp 若则即是 的平方剩余,41.pm 由以上推论知4 413定理2(二次反转定律) 设定理2(二次反转定律) 设p与与q是不同的两个奇素数是不同的两个奇素数,则则11 22()( 1)(),pqqp pq 11 22( 1).( )( )pqqp pq 即即52( )( )1;33 例如：例如：3( )1.5 53( )( )1.3511 22( 1)pq 1 2( 1)1. 114()( )1;77 再如：再如：7()1.11 117()()1.711 11 22( 1)pq 5 3( 1)1. 14注意：利用第二节和本节中的定理，可以判定素数注意：利用第二节和本节中的定理，可以判定素数模的二次同余方程的可解性。模的二次同余方程的可解性。例1 已知例1 已知563是素数，方程是素数，方程x2 429 (mod 563)是否有解。是否有解。4293 11 13 563563() () 解：解：31113 563563563()()() 3 1 563 111 1 563 113 1 563 1 222222563563563( 1)( 1)( 1)31113()()() 224 31113( )( )( ) ( 1)( 1)1 。方程有解。方程有解。15一般地，若一般地，若p是素数，计算可按以下步骤进行：是素数，计算可按以下步骤进行：()n p (1) 求出求出n0 n(mod p)，1 n0 p；(2) 将将n0写成写成n0= Q2q1q2qk的形式，其中的形式，其中Q Z，q1, q2, qk是互不相同的素数；是互不相同的素数；(3)若有某个若有某个qi= 2，用定理，用定理1推论判定之值；推论判定之值；()iq p (4) 若若qi 2，利用定理，利用定理2将的计算转化为计算将的计算转化为计算()iq p();ip q (5) 重复以上步骤，直至求出每个重复以上步骤，直至求出每个();iq p1(6).( )( )k iiqq pp 计算计算16例2 判断方程例2 判断方程x2 137 (mod 227)是否有解。是否有解。13790()()227227 解：解：2235()227 125()()()227227227 227 1 21()( 1)227 1; 2273(mod8), 因为因为2()1227 所以；所以；227 1 5 1 225227()()( 1)2275 2( )5 1 ；137()1227 从而，从而，.原方程无解原方程无解5 517例例3证明：形如证明：形如8k 7（k Z）的素数有无穷多个。解 用反证法，假设只有有限个素数）的素数有无穷多个。解 用反证法，假设只有有限个素数p1, p2, , pt.记记N= (p1p2pt)2 2，2.N显然显然设设q是是N的一个奇素因数，则的一个奇素因数，则(p1p2pt)2 2 (mod q)，因此，由定理，因此，由定理1有有q 1或或7(mod 8)。若。若N的所有奇素因数都具有的所有奇素因数都具有8k 1的形式，则的形式，则N也是也是8k 1的形式，但是，由于任何奇数的平方对模的形式，但是，由于任何奇数的平方对模8与与1同余，所以应有同余，所以应有N 1 2 1 (mod 8)。这个矛盾说明，。这个矛盾说明，N至少有一个形如至少有一个形如8k 7的奇素因数的奇素因数q。18例4 求以11为其二次剩余的所有奇素数例4 求以11为其二次剩余的所有奇素数p. .1 211()()( 1),11pp p 解：解：()11p 直接计算得直接计算得1,1, 2,3,4,5(mod11);1,1,2, 3, 4, 5(mod11).pp 1 21,1(mod4);( 1)1,1(mod4).ppp 12(mod4);(mod11).papa 解同余式组解同余式组121112(mod44).paa 得得 11()11, 5, 7, 9, 19(mod44).pp 从而有从而有19练习：21.1 mod365,.x 判断是否有解 若有求出解数 42.11 mod8 ,xp 证明:的奇素数进而推出有无1 mod8 .p 穷多个素数 3.:1 mod4 .p 证明 有无穷多个素数 424.:11 mod12 .nnp证明的素因数201:3655 73, 解方程等价于 221