《初等数论(闵嗣鹤、严士健)》第三版课件5-3

1 11§5.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 )()();aaaappp1212(4) ()()()();nna aaaaa pppp2 (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 )()()aaaappp1(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，且，且p>2，故得证。

故得证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例如：取例如：取5115[][]11lkinkk p 001124511是的平方剩余;是的平方剩余;11,7.pa  取取5117[][]11lkknkk p 011237711不是的平方剩余.不是的平方剩余.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)(),pp pq  11 22( 1).( )( )pp pq   即即52( )( )1;33   例如：例如：3( )1.5  53( )( )1.3511 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= Q2q1q2qk的形式，其中的形式，其中Q Z，，q1, q2,, qk是互不相同的素数；是互不相同的素数；(3)若有某个若有某个qi= 2，用定理，用定理1推论判定之值；推论判定之值；()iq p (4) 若若qi  2，利用定理，利用定理2将的计算转化为计算将的计算转化为计算()iq p();ip q (5) 重复以上步骤，直至求出每个重复以上步骤，直至求出每个();iq p1(6).( )( )k ii 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= (p1p2pt)2  2，，2.N显然显然设设q是是N的一个奇素因数，则的一个奇素因数，则(p1p2pt)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的奇素因数的奇素因数q18例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。