初等数论(严蔚敏版) 12.2 勒让德符号

《初等数论(严蔚敏版) 12.2 勒让德符号》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二节Legendre符号•从上节知道,当模比较大的时候,平方剩余与平方非剩余的欧拉判别法很难实际应用.本节将要给出一个比较便于实际计算的判别方法,为此,我们需要引进Legendre符号.定义给定奇素数p,对于整数n,定义Legendre符号0,当p

2、n时(即(n,p)1)n()1,当nQR(p)时(即n是模p的平方剩余).p-1,当nQNR(p)时(即n是模p的平方非剩余)如:1与4是5的二次剩余,2与3是5的二次非剩余,1234于是()1,()-1,()-1,()1.5555定理1设p是奇素数

3、,n是整数,则p-1n(1)()n2(modp);pnn1(2)若nn(modp),则()()(modp);1ppp-11-1(3)()1,()(-1)2;ppaaaaaa12k12k(4)对任意的整数a,1ik,有()()()().ipppp证明:(1)分三种情况说明,n若p

4、n,由Legendre符号的定义知,()0,pp-1又n20(modp),成立.n若n是模p的平方剩余,由Legendre符号的定义知,()1,pp-1又由第一节定理1知,n21(modp),成立.p-1n若n是模p

5、的平方非剩余,易知()1n2(modp),p成立;(2)若nn(modp),1则它们同是模p的二次剩余(或二次非剩余),成立;2(3)对同余式xn(modp),2不论任何奇素数p,总有11(modp),即1总是奇素数p的平方剩余(或在(1)中令n1即可).p-1-1在(1)中令n-1,则()(-1)2,pp-1-1又()(-1)2(modp)两端只能取1或-1pp-1-1(即是说它们不能相差p的整数倍),()(-1)2;pp-1aaa12k2(4)由(1)知,()(aaa)12kpp-1p

6、-1p-1aaa22212k(a)(a)(a)()()()(modp),12kpppaaaaaa12k12k同样,式子()()()()(modp)pppp的左右两边只能取1,0,或1(即是说它们不能相差p的整数倍),aaaaaa12k12k()()()().pppp推论设p是奇素数,则-1QR(p)p1(mod4),-1QNR(p)p3(mod4).p-1-1证明:由性质()(-1)2易知.p定理22p12()(1)8.p•本定理在下节中进行证明.例1判断下列同余方程是否有解.2

7、(1)x3x50(mod7);2(2)5x7x110(mod23).22解:(1)x3x5x10x522(x5)55(mod7),2令yx5,则原方程化为y20(mod7),2即y1(mod7).p-17-1-1-1()(-1)2,()(-1)21,p72故y1(mod7)无解,则原方程也无解.22(2)5x7x115x30x35(mod23),(5,23)1,故原方程等价于22x6x7(x3)160(mod23),2令yx3,则原方程

8、化为y16(mod23).2易知y16(mod23)有解,从而原方程有解.例2设n是整数,2证明:n1的任何奇因数都是4m1的形式.证明:由于奇数都可表示成奇素数之积,而且任意多个形如4m1的整数之积也具有4m1的形式.2我们只需证明:若素数p是n1的因数,则p具有4m1的形式.22若p

9、n1,则n1(modp),即-1QR(p),由以上推论知,p4m1.例3设p是奇素数,(n,p)1,是正整数.2n证明:同余方程xn(modp)有解的充要条件是()1.p2证明:若同余方程xn(

10、modp)有解x,022n则xn(modp),xn(modp),()1.00pn2若()1,则xn(modp)有解x,0pp

11、2x,由第四章第三节定理2知,02由此解可导出xn(modp)的一个解x,2即xn(modp)有解.例4若a1(mod4),2

12、b,并且b没有形如4k3(kZ)的素因数.2332证明:方程yx-a-b没有整数解.证明:用反证法,假设方程有整数解x,y.2若2

13、x,y-1(mod4),则这是不可能的(-1不可能是模4的平方剩余).2332若x3(mod4)

14、,则yx-a-b333-1-02(mod4)这也是不可能的.若x1(mod4),222则xaxa1aa3(mod4),22则必有素数p3(mod4),使得p

15、xaxa,23322于是yx-a-b-b(modp),22b即-b是模p的平方剩余,(-)1.p22p-1b-1