(11)初等数论ppt第五章-一勒让德符号、Jacobi符号

第五章(2)勒让德符号、雅可比符号1222222,0(mod).(1)4,4)0(mod))4(mod).(2)(mod),4(mod).ppaaxbxcppaaaxbxcpaxbbacpyaxbpybacp设是奇质数.设二次同余式的一般形式是由于所以(1)和同余式(的解相同,上式可写成(2容易看出,通过变数替换2同余方程与同余方程是等价的||复习222(mod)(mod)0(mod(5)).xappaxapxppa由以上讨论知，我们只有讨论形如的同余式当时,仅有一解，所以以后恒假定3212,.(mod)()()papaxapapap定义设质数是整数,如果同余式有解,则称是模的;若无解,则称是模平方二次剩余平方二的次.非剩余|平方剩余和平方非剩余431(mod3)1(mod3)51,1(mod5)2,2(mod5)71,2,3(mod7)1,2,3(mod7)paapaapaa例如,当时,是模3的平方剩余，是模3的平方非剩余.当时,是模5的平方剩余，是模5的平方非剩余.当时,是模7的平方剩余，是模7的平方非剩余.5211)/21)/2(mod)2.pppppapxap定理在模的一个简化剩余系中,恰有(个模的平方剩余;(个模的平方非剩余.此外,若是模的平方剩余,则同余式的解数为62211,17,19,2912345(mod11)14253-12345678(mod17)148182243pjdjjdj例1求的平方剩余与平方非剩余.模11的平方剩余是:1，2,3,4,5;平方非剩余是:-1,2,-3,-4,-5模17的平方剩余是:1，2,4,8;平方非剩余是:,5,6,7.7(1)/2(1)/2()2.1(mod4);1(mod4)12ppppaapapapappppp定理2欧拉判别条件设质数,那么,是模的平方剩余的充要条件是1(mod);(9)是模的平方非剩余的充要条件是1(mod).(10)推论3-1是模的平方剩余的充要条件是当时,((|2.(13)p)!)1(mod)8(1)(1)/2(1)/2(1)/2(1)/202100,,-1)(1)021,1(11)2,:,)ppppppapaapaappaaapxxapxa证存在性对任一式(9)或(10)有且仅有一式成立.由费马欧拉定理知1(mod),因而有((mod).由于质数及(所以推出结论.必要性若是模的平方剩余则必有使得的充要条件是(mod),因而有|(1)/2100,,-1ppppapxxp(mod).由于所以因此由费马欧拉定理知(mod).由此推出式(9)成立.||9(1)/2(.,1,(1)!wil)s(o12njjppabxappapjbjapjxpjxpapa充分性：设式(9)成立,这时必有考虑一次同余式(mod).由定理及知,对于式(6)给出的模的简化剩余系中的每个当时,必有惟一属于简化剩余系(6),使得上式成立.若不是模的平方剩余,则必有,这样简化剩余系(6)中的个数就可按作为一对,两两分完.因此有(mod).由定理知||01)/2001.,pjpjjx(mod)但这和(9)矛盾.所以必有某一,使由此及(12)证得结论.10121212121212122,.,,ppapaaapaapaapaapapapaap推论4设素数,那么,(i)若均为模的平方剩余,则也是模的平方剩余;(ii)若均为模的平方非剩余,则是模的平方剩余;(iii)若是模的平方非剩余,是模的平方非剩余,则是模的平方非剩余.||11222221(mod61);16(mod51);2(mod209);63(mod187).xxxx例2利用定理来判断:(i)3是不是模17的平方剩余;(ii)7是不是模29的平方剩余.例3判断下列同余方程的解数：(i)(ii)(iii)(iv)12(Legendre)()(),1,()1,0,.aappaapaapppa定义勒让德符号读作对的勒让德符号是一个对于给定的单质数定义在一切整数上的函数它的值规定如下：当是模的平方剩余；当是模的平方非剩余；当§3Legendre符号,Gauss二次互反律13(1)/22(1)/2Legendre(i)()();(ii)()(mod);(iii)()()();(iv)()1;11(v)()1,()(1);ppapappaappacacpppapappp定理符号有以下性质：当时，|14Legendre()12(),(),(),(),().2apapapppqaqppp这样,确定是否是模的二次剩余就变为去计算符号的值.定理的性质可以用来计算并由算数基本定理知,只要能计算出：就可以计算出任意的这里是小于的素数.1521=1(1)/8[]12()(1)7,(,)1,2|,1()=(-1)8),21,1(mod8)21,3(mod8)pkpakpnapapapppppp定理2（）若则（其中.推论()=(-1)16(1)/2(1)/23,(,)1,()(1)().3,,1()();43()().pqpqpqqppqpqqppqqpkpq定理设均为单质数,则定理表明:两个奇数只要有一个数（mod4),就必有当且仅当它们都是形式的数时,才有(Gauss二次互反律)1722Legendre()()(mod)(mod)3Legendreqppqxqpxpqqppq由符号知,和分别刻画了同余方程和是否有解,即是否是模的二次剩余和是否是模的二次剩余，这里正好是模和剩余互换了位置.定理就是刻画了这两者之间的关系,所以称为二次互反律.二次互反律是初等数论中最重要的定理之一.它不仅可用来计算符号,而且它有重要理论价值.1819202860(mod11021)x例求解同余方程21Blum.RSA二次剩余一个有趣且有用的应用就是由布卢姆()发明的电子抛币此方法充分利用了寻找素数所需时间和分解是两个素数乘积的整数所需时间的长度差,这也是密码的基础.电子抛币22221,3(mod4).,(mod)(mod),,,,20(mod),,pqpqnpqnxxanaanxanxynxnyxyxqxynqxn假设鲍勃和爱丽斯正在进行电子通信.爱丽斯选取两个不同的大素数和它们满足爱丽斯将整数发给鲍勃.鲍勃随机选取一个小于正整数并将满足的整数发给爱丽斯,其中0.爱丽斯求出的四个解,即然后将这四个解中的一个发送给鲍勃.注意到我们有和,.,.,.ynpynynxnxnnnn于是,若鲍勃或时候,则他能用欧几里得算法迅速求出的一个素因子.另一方面,若鲍勃收到或则他无法在合理的时间内分解于是若鲍勃能分解则他就赢得了抛币的胜利,否则爱丽斯胜利由上面的分析知,鲍勃收到能使他快速分解的的解的概率,与他收到不能帮助分解的解的概率相同.2311111111,1,1LegendreJacobisssssjsjjPPpppjsaaaaPppppajsppaP定义设奇数,()是素数.定义这里()是模的符号.我们把称为是符号.§5Jacobi符号2412221Jacobi1(i)()1;,1()0;,1()1;(ii)()();(iii)()()();(iv)()()();(v),)()()1.aaPPPaaPPaaPPPacacPPPaaaPPPaaPaPP定理符号有以下性质：当()时，当()时,取值当（=1时,25111212121212121(mod)(1),,111(mod).211(1)(1)(1)(1).1(mod)1(mod),111(1)(1)11(mod).jssjamjsaaaaaammmmsaaaaaaaamamaaaaammmmaammm引理2设我们有证显然只要证的情形.我们有由知所以261(1)/2(1)/81(1)/2(1)/2111()(1);(1)2()(1).(2)111()()()(1).22,(1),111(mod2).2222()sPPsppjjssPPPppmapjsPppPppP定理3我们有证设是奇素数.由定义,定理1(v)知在引理中取就得到由以上两式即得式(1).由定义和定理2得§2221(1)/8(1)/8122222122()()(1).1(mod8).22,(1)111(mod8).888sppjsjjjsppppmapjsPpp由于是奇数,所以在引理中取就得到由以上两式即得式(2).27(1)/2(1)/211(1)/2(1)/211111(111,1,(,)1.(1).()()()(1){()}{(1)jijPQsrjissrsrpqjijjijijjisrpjjiiPQPQQPPQPppQqqpqpQQqPppqpq定理4设奇数奇数我们有()()=证设,,,均是奇素数.由定义,定理1()11(1)/2(1)/21)/2(1)/21111(1)/2(1)/2(1)/2(1)/2(1)/2(1)/21}(1).1113)(mod2).222(1)(1)(1).rjiiisjjisrspqqjijrsQPpQQPjPQQqqQPPPPQQQ()类似于式(可得由以上两式得()()()()28222222109,45385222211145353510910910910910938557115711441022157115711例求雅克比符号解:==2111129.105Legendre105acobi3171053172317105105acobiLegendreacobiLegendreacobidP以上性质表明:为了计算符号,我们并不需要求素数因数分解式例如，不是奇素数,我们要计算符号()时,可以先把它看作J符号来计算,由定理4得()=()=()=1.因此,引入J符号后,对计算符号十分方便.但J符号和符号本质差别是：J符号()=1,绝不表22(mod),222)))1,2(mod9)933xdPx示二次同余方程一定有解.例(((但同余方程无解.3022221(mod).(mod)1.(mod)(mod)1.,1,jtmjjPPaxaPPaxaPPpPxaPxapaaapPp当是素数时,雅克比符号与勒让德符号一致.但是合数时,雅克比符号的取值并不能确定同余方程是否有解我们知道,若同余方程有解,则事实上,注意到若是的素因子且有解,则有解,从而因此其11222.2222,15,111.2(mod15)15352(mod3)2(mod5).mttmPPppaPxxx中有素幂分解设则有但无解,这是因为和均无解3121431563122286(mod563)286214356356356356314391143143x例判断同余