12.5 初等数论(严蔚敏版) 质数模的二次同余方程 (1)

《12.5 初等数论(严蔚敏版) 质数模的二次同余方程 (1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五节质数模的二次同余方程前面所讲的平方剩余与平方非剩余,欧拉判别条件,Legendre符号,Jacobi符号,归纳起来,只讲了一个中2心问题,就是用来判定二次同余方程xa(modp)2是否有解.如何求解二次同余方程xa(modp),这就是我们所要研究的第二个中心问题,下面我们介绍这个问题.2我们讨论xa(modp),p

2、a,p是奇质数.(1)的具体求法.a当()1时,说明a是p的平方剩余,方程(1)有解,p方程(1)的解是什么形式?1(p1)由欧拉判别法有a21(modp),11(p1)(p1)于是

3、a2aa2a(modp),11(p1)(p1)2从a2a(modp)出发有,a4a(modp),1(p1)42即(a)a(modp).1k2假若k(p1)为整数,则(a)a(modp),4k因此xa(modp),即为所求方程(1)的解.k为整数,可以分为两种情形.1当k是奇数时,则(p1)1(mod2),p3(mod8).41当k是偶数时,则(p1)0(mod2),p7(mod8).4情形1当p3(mod8)或p7(mod8)时,方程(1)有解,1(p1)即为形式xa

4、4(modp)的解.2例1求解同余方程x11(mod43).43111111431解:()(1)22()()1,4311112同余方程x11(mod43)有解,对于p433(mod8),故所求的解为1(431)411x1111(mod43).248而118(mod43),1121(mod43),1111(mod43),1011112(mod43),1121(mod43).故x21(mod43)为所要求方程的解.若k不为整数,上述的方法当然是不能用的,但是,可以

5、按上述原则进行处理.因为p是奇质数,关于模8,只有下面四种情形:p1(mod8),p3(mod8),p5(mod8),p7(mod8).而p3(mod8),p7(mod8)这两种情况已讨论.只需要对p1(mod8),p5(mod8)这两种情形讨论.讨论p5(mod8)的情形.11(p1)因为(p1)是整数,由欧拉判别条件a21(modp),411(p1)(p1)有(a41)(a41)0(modp),11(p1)(p1)所以a410(modp)或a410(modp),1(p

6、1)若前式成立,则a4aa(modp),11(p3)(p3)482aa(modp),这时(a)a(modp),11(p3)这时(p3)是整数,故方程(1)的解是xa8(modp).81(p3)若后式成立,则a4a(modp),2p12由()(1)8可知,2是p的平方非剩余,pp1由欧拉判别条件有221(modp),p11(p3)于是22a4a(modp),11(p1)(p3)故方程(1)的解为:x24a8(modp).情形2当p5(mod8)时:1(p1)若a

7、41(modp),则方程(1)的解是:1(p3)xa8(modp);1(p1)若a41(modp),则方程(1)的解是:11(p1)(p3)x24a8(modp).2例2解同余方程:x23(mod101).101-1231231019解:因为()(-1)22()()1,1012323所以同余方程有解,1这时p1015(mod8),(p1)25,41(p1)42525而a23,所以需要计算23,242352924(mod101),2357630(mod101),1

8、213232700033(mod101),2375649(mod101),252316171(mod101),25再计算2,510232,2102414(mod101),202252146(mod101),219210(mod101),故所求的方程的解为2513x223104915或15(mod101).最后讨论p1(mod8)的情形,这种情形比前三种都要复杂,没有一般结论,在下面我们所要介绍的,只是一个求解的原则.3我们先看一个例子:p415812

9、51,k于是,由此例可以令p2h1,k3,h是奇数,由欧拉判别条件有111(p1)(p1)(p1)a21(a41)(a41)0(modp),11(p1)(p1)a410(modp)或a410(modp),11k1kk2又(p1)(2h11)2h2h,444k2k22h2