初等数论(严蔚敏版) 12.1 素数模的二次剩余

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

1、第五章二次同余式与平方剩余第一节素数模的二次剩余在这一章里,我们将比较深入地研究二次同余方程.首先,我们讨论一种最简单的二次同余方程,其一般形式2为xa(modp),p为素数.2当p2时,xa(modp)总有解,且其解数为1.其中当a0(mod2)时,解为x0(mod2);当a1(mod2)时,解为x1(mod2).下面我们只研究模为奇质数的情形,2此时,若a0(modp),方程xa(modp)有解,且解数为1,即x0(modp),在此无需研究,故我们只需要讨论形如2xa(modp),(a,p)1的同余方程.2记素数p

2、,axbxc0(modp),(1)如果(a,p)p,则方程(1)成为一次同余方程,只需考虑p2,且(a,p)1的情形.(4a,p)1,方程(1)等价于224ax4abx4ac0(modp),22(2axb)b4ac(modp),2研究方程(1)归纳对方程xa(modp)的研究.定义给定整数p,对于任意的整数a,(a,p)1.2若方程xa(modp)有解,则称a是模p的二次剩余,记作aQR(p).否则称a是模p的二次非剩余,记作aQNR(p).•在本节中,总假定p是奇素数.定理1若(a,p)1,则p

3、-1(1)a是模p的二次剩余的充要条件是a21(modp);(欧拉判别条件)2(2)若a是模p的二次剩余,则方程xa(modp)有两个解;p-1(3)a是模p的二次非剩余的充要条件是a21(modp).证明:(1),(2)由第四章第四节定理6:若p是素数,n

4、p1,p

5、a,p-1nn则xa(modp)有解的充要条件是a1(modp).若有解,则解数为n.易得;p-1(3)若(a,p)1,则由Euler定理,a1(modp),p1p1(a21)(a21)0(modp),p1p是素数,则a210(modp)

6、p1或a210(modp)中必有一个成立,p1又由(1)知,a21(modp).定理2模p的简化剩余系中,p-1二次剩余与非二次剩余的个数都是,2而且,模p的每个二次剩余与且仅与数列22p-121,2,,()中的一个数同余.2p-1证明:由定理1知,平方剩余个数等于同余式x21(modp)的解数.p-1p-1又x2-1xpx,即xp-x(x2-1)f(x),由第四章第四节定理5:nn-1设np,则同余方程f(x)xaxaxa0(modp)n-110有n个解的充要条件是存在整系数多项式q(x)和r(x),且

7、r(x)的次数n,pxxf(x)q(x)pr(x).p-1知,平方剩余的个数是,2又模p恰有p-1个与p互素的剩余类,则模p的平方剩余与非平方剩余总数等于p-1,p-1p-1p1-.2222p-12显然,1,2,,()中的数都是平方剩余,222p-12只需证明数列1,2,,()中2任何两个数对模p不同余,p-1对任意k,s,1sk,222若ks(modp),p

8、ks或p

9、k-s,1k-sksp,p

10、ks或p

11、k-s这都是不可能.注意21.该定理给出了判断方程xa(modp)是否有解的一种方法,2

12、2p-12即判断a是否与1,2,,()中之一数关于模同余p,如果2是,则方程有解,否则方程无解.2.欧拉定理并不是一个实用的判别法,因为对具体的素数p,22p-12当它不太大时,我们通常可以通过计算1,2,,()来2直接确定哪些a是平方剩余,哪些a是平方非剩余,这要比验p1证a21或(1)(modp)要简单;当p较大时,这两种方法都不实用.3.因此,欧拉判别法多用于理论上.2例1(1)把三项二次同余方程4x11x30(mod13)化为二项二次同余方程.2(2)把三项二次同余方程x3x50(mod79)化为二项二次同余方程

13、.2(3)把三项二次同余方程5x7x110(mod23)化为二项二次同余方程.(1)解:(4,13)1,2把同余方程axbxc0(modp)两边乘以4a,2即把同余方程4x11x30(mod13)两边乘以16,2164x1611x1630(mod13),2(8x11)169(mod13),2y0(mod13),其中y8x11.22(2)解:x3x5x82x522(x41)415(mod79),令yx41,则原方程化为2y17(mod79).22(3)解:5x7x11

14、5x30x35(mod23),(5,23)1,故原方程等价于22x6x7(x3)160(mod23),2令yx3,则原方程化为y16(mo