第五章 (10) 一般二次同余式、平方剩余

《第五章 (10) 一般二次同余式、平方剩余》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章二次同余式与平方剩余本章的目的就是讨论二次同余式.首先把问题归结到讨论形式如：x2≡a(modm)的同余式，从而引入平方剩余与平方非剩余的概念.再利用勒让德符号及雅克比符号讨论m是单质数的情形.2§1一般二次同余式设p是奇质数.设pa

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

3、4,所以(1)和同余式24aax(bxc)0(modp)的解相同,上式可22写成(2axb)b4ac(mod).p(2)容易看出,通过变数替换ya2xb(mod)(3)p,22同余方程与同余方程y

4、b4ac(mod)(4)p是等价的.3由以上讨论知，我们只有讨论形如2xa(mod)p(5)的同余式2当pa时,xa(mod)p仅有一解xp0(mod)，所以以后恒假定pa.4§2平方剩余和平方非剩余定义12,设.质数papa是整数,

5、如果2同余式xap(mod)ap有解,则称是模的平方()二次剩余;若无解,则称ap是模的平方()二次非剩余.5例如,当pa31(mod3)时,是模3的平方剩余，a1(mod3)是模3的平方非剩余.当pa51,1(mod5)时,是模5的平方剩余，ap2,2(mod5)

6、7是模5的平方非剩余.当时,a1,2,3(mod7)是模7的平方剩余，a1,2,3(mod7)是模7的平方非剩余.6定理1在模p的一个简化剩余系中,恰有(ppp1)/2个1)/2模的平方剩余;(个模pa的p平方非剩余.此外,若是模的2平方剩余,则同余式xap(mod)的解数为2.7pp11证只要取模p的绝对最小简化剩余系,-+1,,-1,22pp111,,-1,(6)来讨论.ap是模的平方剩余当且仅当22p12p1222p12p12ap(),(1),,(1),1,,(1)或()(mod)

7、222222由于(-jj)(modp),所以a是模p的平方剩余当且仅当2p12p12ap1,,(1)或()(mod)(7).当1ij(p1)/2时,2222ij(mod)p(8).所以式(7)给出了模p的全部平方剩余,共有(p1)/2个.由于模p的简化剩余系有p1个数,所以另外的(pp1)/2个必为模的平方非剩余,这就证明前一半结论.当a是模p的平方剩余时,由式(7)及(8)知,必有惟一的i,使xip(mod)是(5)的解,进而就推出在简化剩余系(6)中有且仅有xi(mod)p是(5)的解,即(5)

8、的解数为2.8例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.9定理2()欧拉判别条件设质数p2.,pa

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

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

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

12、由于00p1pa

13、

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

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

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

17、1(mod)x.但,这和(9)矛盾.所以必有某一,使00j0由此及(12)证得结论.12推论4设素数p2,papa

18、

19、,.那么,12(i)若aa,p均aa为模的平方剩余,则也是1212模p的平方剩余;(ii)若aa,p均aa为