1、第五章第五章 二次同余式与平方剩余二次同余式与平方剩余apEulerLegendreGaussLegendreEulerGaussapJacobi一个整数 何时是素数模 的完全平方数？伟大的数学家、和对这一问题和相关问题都进行了深入的研究，极大地推动了现代数论的发展。在这一章，我们从一般二次同余方程解的问题引入二次剩余的概念和符号，其次给出一个由和发现的一个确定整数是否为模 的二次剩余的判别准则，接着给出著名的二次反转定律，引入符号。第一节第一节 一般二次同余式一般二次同余式第二节第二节 单质数的平方剩余与平方非剩余单质数的平方剩余与平方非剩余2(mod)yaxbp容易看出，通过变量替换2(
2、, )1,0(mod)(*)pp aaxbxcp设 是单质数，且二次同余式的一般形式为222( , )1( ,4 )1(*)4 ()0(mod)(2)4(mod)p apaa axbxcpaxbbacp由知，所以式和同余式的解相同，上式可写成224(mod)ybacp上 述 同 余 式 与是 等 价 的 ， 也 就 是 说 ， 两 者 同 时 有 解 或 无 解2(mod)(1)xap由以上分析得出，我们只要讨论形如的同余式即可。0(mod)(,)1p axpp a当时，(1)仅有一解所以，以后恒假定2(mod)xapp此时同余式要么无解，要么有偶数个关于模 的不同余的解。2(mod),( ,
3、)1(1)(1)xapa papap定义：若同余式有解，则 叫做模 的平方剩余，若无解，则 叫做模 的平方非剩余2(mod)xap为了确定同余式的解的存在性问题，我们引入平方剩余的概念：这样，我们就有二次（平方）剩余理论要解决的两个问题：( )iiapp给定一个整数 ，确定它是哪些质数模 的平方剩余，又是哪些质数模 的平方非剩余。( ) ipapap给定一个质数 ，确定哪些整数 是模 的平方剩余，哪些整数 是模 的平方非剩余；121( ,)11(mod)2pa papap定理（欧拉判别条件）若，则 是模 的平方剩余的充要条件是（ ）121(mod)3papapap 而 是模 的平方非剩余的充要
4、条件是（ ）若 是模 的平方剩余，(1)式恰有两解。11122( )()(1)ppppixxx xaax证： 先证平方剩余的充要条件：因为122( )(1)pxaxq xax）211220(mod)1,1(mod)ppxapp aap而恰有两个解的充要条件是即1112222()(1)pppxaxax11122( )1(mod)(1)(1)0(mod)pppiiapaap再证平方非剩余的充要条件：因为由欧拉定理得，所以112210(mod)10(mod)ppapap 所以或1212112210(mod)10(mod)11,2pppppapapp ap ap由 为单质数，与有且只有一个成立，否则且
5、从而（矛盾）121210(mod)10(mod)ppapap 而为平方剩余的充要条件，则为平方非剩余的充要条件。2222112211 ,2 ,2pppp定理模 的简化剩余系中平方剩余与非剩余的个数各为，而且个平方剩余分别与序列中之一数同余，且仅与一数同余25(mod11)x 例1、判断同余式是否有解11 15422555 55 31(mod11) 解：同余式有解，且有两个解221(mod4)1!1(mod)2pppp 例 、设 是奇素数，则121)!( 1)(1)!pWillsonpp 解：由定理得：-1 （1211( 1)1 2(1)22pppp 1211( 1)1 2(1)22ppppp
6、112211( 1)1 2( 1)2 122pppp 2211()!()!(mod)22ppp 第三节第三节 勒让德符号勒让德符号()()aLegendreapppa定义 勒让德符号读作 对 的勒让德符号 是一个对于给定的单质数 定义在一切整数 上的函数，它的值规定如下：1,1,0,apaappp a 是模 的平方剩余模 的平方非剩余勒让德符号的几个性质勒让德符号的几个性质12(mod)paapp121111(mod)=1pppp，即112211( 1)(mod )=( 1)ppppp ，即112 ,41,121121,43,12pkpkppkpkp 进一步有，当即时，当即时12111121(
7、mod)(mod)(mod)ppaaapappaaaapppp当时，由于，所以11 21221 21 212()(mod )pnnnnnaaaaaaaaapppppaaaaaapppp，2ababbappppp 特 别 地112,(2,)1aZaaa 注意：对，设111,222,(2, )1apaapppapp 112,(2,)1aZaapp 故对，其勒让德符号的值可转化为计算及21118121(1 )(,)1, (, 2 )1(1 )12pkpa kppapaappp定 理；若， 则其 中2212 ,81,2812 +1,83,28pkpmpkpm推论：当即时是平方剩余当即时是平方非剩余21
8、0(mod 2)8110(mod 4)22ppp证 ： 当时 ， 有1+1+221+10(mod4)0(mod4)22ppppp又因为，因此两数必为一奇一偶，于是或11(mod8)1(mod8)ppp 即或所以只有当时，2是它们的平方剩余；211(mod2)83+30(mod4)22ppp当时，有33(mod8)3(mod8)ppp 同上讨论，我们有即或所以只有当时，2是它们的平方非剩余2例 求出以为平方剩余与平方非剩余的质数的一般表达式212ppp解由1111( )2211ppIpp 当或1(mod4)1(mod8)pp即1(mod4)1(mod8)pp或3(mod4)3(mod8)pp或3
9、(mod 4)3(mod8)pp 或而无解，的解为81832pnpnp因此，当或时，是 的平方剩余1111()22112ppIIppp 当或时，是 的平方非剩余1(mod8)p ，3(mod8)p 的解为3(mod4)1(mod8)pp即3(mod4)1(mod8)pp 或1(mod4)3(mod8)pp或1(mod4)3(mod8)pp 或而无解，1(mod8)p 的解为，3(mod8)p 的解为，81832pnpnp因此，当或时，是 的平方非剩余01201121212kkkkaq qqqqappppp 设，则12apqpqppp这样，计算的问题就归结于计算下面的三种值：，（ ， 均为奇素数
10、），前两者已讨论，后面讨论第三种值的计算。1122( , )1( 1)pqpqqpp qpq 定理2（二次反转定律）若 ， 是单质数，则2286(mod563)x 例判断同余式是否有解5637083解：质数28621431113563563563563563 ，1356341,56313131156321,5631111 2861,563 同余式无解22317xy例证 明 方 程无 解217(mod 23)x证：对于同余式17 1 23 1221723623( 1)23171717171 ( 1)1 2217(mod23)2317xx同余式无解，故原不定方程无解3p例 求以 为平方剩余与平方非
11、剩余的质数 的一般表达式1233( 1)pppp 解：首先， 为素数，由二次反转定律得11221133( 1)1( 1)1pppp 当或时，3=1,3pp则 为 的平方剩余3 13 1221(mod3)1(mod3)110(mod2)0(mod2)22pppp 此时或1(mod3)1(mod3)1(mod4)3(mod4)pppp 即或1(mod12)1(mod12)pp 解得或=121121pkpk即或3 13 1221(mod3)1(mod3)111(mod2)0(mod2)22pppp 此时或11221133( 1)1( 1)1pppp 当或时，3= 1,3pp则 为 的平方非剩余7(mod12)5(mod12)pp解得或=1213pkp故当时，为模 的平方剩余=1253pkp当时，为模 的平方非剩余
