第五章 (11) 一勒让德符号、Jacobi符号

《第五章 (11) 一勒让德符号、Jacobi符号》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章(2)勒让德符号、雅可比符号1复习设p是奇质数.设pa

2、,二次同余式的2一般形式是axbxc0(mod).p(1)由于pa

3、4,所以(1)和同余式24aax(bxc)0(mod)p的解相同,上式可22写成(2axb)b4ac(mod).p(2)容易看出,通过变数替换y2axb(mod),p22同余方程与同余方程yb4ac(mod)p是等价的.2由以上讨论知，我们只有讨论形如2xa(mod)p(5)的同余式2当pa时,xa(mod)p仅有一解xp0(mod)，所以以后恒假定pa.3平方剩余和平方

4、非剩余定义12,设.质数papa是整数,

5、如果2同余式xap(mod)ap有解,则称是模的平方()二次剩余;若无解,则称ap是模的平方()二次非剩余.4例如,当pa31(mod3)时,是模3的平方剩余，a1(mod3)是模3的平方非剩余.当pa51,1(mod5)时,是模5的平方剩余，ap2,2(mod5)7是模5的平方非剩余.当时,a1,2,3(mod7)是模7的平方剩余，a1,2,3(mod7)是模7的平方非剩余.5定理1在模p的一个简化剩余系中,恰有(ppp1)/2个1)/2模的平方剩余;(个

6、模pa的p平方非剩余.此外,若是模的2平方剩余,则同余式xap(mod)的解数为2.6例1求p11,17,19,29的平方剩余与平方非剩余.j123452dj(mod11)14253模11的平方剩余是:1，-2,3,4,5;平方非剩余是:-1,2,-3,-4,-5j123456782dj(mod17)14818224模17的平方剩余是:1，2,4,8;平方非剩余是:3,5,6,7.7定理2()欧拉判别条件设质数p2.,pa

7、那么,a是模p的(p1)/2平方剩余的充要条件是ap1(mod);(9)a

8、p是模的平方非剩余的充要条件是(p1)/2ap1(mod).(10)推论3-1是模p的平方剩余的充要条件是pp1(mod4);当1(mod4)时,p12(()!)1(mod)p.(13)28证存在性对任一apa,,

9、式(9)或(10)有且仅有(p1)一式成立.由费马-欧拉定理知ap1(mod),因而(pp1)/2(1)/2有(a1)(a1)0(mod)p(11).由于质数p2(pp1)/2(1)/2及(aa1,1)2,所以推出结论.必要性:,若a是模p的平方剩余则必有x使得的充要021p(p

10、1)/2条件是xa(mod),p因而有xa(mod).p由于00p1pa

11、

12、,所以px,因此由费马-欧拉定理知x1(mod).p00由此推出式(9)成立.9充分性：设式(9)成立,这时必有pa

13、.考虑一次同余式bxa(mod)p(12).由定理及pa

14、知,对于式(6)给出的模p的简化剩余系中的每个j,当bj时,必有惟一属于简化剩余系(6),使得上式成立.若a不是模p的平方剩余,则必有jx,j这样简化剩余系(6)中的p1,个数就可按jx作为一对,两两j(p1)/2分完.因此有(p1)!a(mod).p由wils

15、on定理知(p1)/2a1(mod)p.但这和(9)矛盾.所以必有某一j,使jx,00j0由此及(12)证得结论.10推论4设素数p2,papa

16、

17、,.那么,12(i)若aa,p均aa为模的平方剩余,则也是1212模p的平方剩余;(ii)若aa,p均aa为模的平方非剩余,则是1212模p的平方剩余;(iii)若a是模pa的平方p非剩余,是模的平方12非剩余,则aa是模p的平方非剩余.1211例2利用定理2来判断:(i)3是不是模17的平方剩余;(ii)7是不是模29的平方剩余.例3判断下列同余方程的解数：2(i)x1(m

18、od61);2(ii)x16(mod51);2(iii)x2(mod209);2(iv)x63(mod187).12§3Legendre符号,Gauss二次互反律a定义勒让德(Legendre)符号()(读作ap对的勒让德符号)p是一个对于给定的单质数定义在一切整数a上的函数,它的值规定如下：1,当ap是模的平方剩余；a()1,当ap是模的平方非剩余；p0,当pa.13定理Legendre符号有以下性质：apa(i)()();ppa(p1)/2(ii)()ap(mod);pacac(iii)()()();

19、ppp2a(iv)当pa

20、时，()1;p11(p1)/2(v)()1,()(1);pp14这样,确定ap是否是模的二次剩余就变为去计算aLegendre符号()的值.定理的性质可