数论 01二次同余式与平方剩余

2020/1/30数论第四章二次同余式与平方剩余一二次同余式的概念二二次同余式的应用三模为奇素数的平方剩余与平方非剩余2020/1/30数论一二次同余式的概念二次同余式的一般形式是)mmod(0cbxax2(1)其中a0(modm).因为正整数m有素因数分解式k1k1ppm，所以二次同余式(1)等价于同余式组：)p(mod0cbxax)p(mod0cbxaxk1k2122020/1/30数论一二次同余式的概念我们只需讨论模为素数幂pa的同余式:),pmod(0cbxax2pa(2)将同余式的两端同乘以4a,我们得到)pmod(4acb)b2ax()pmod(04ac4abxx4a2222或令y=2ax+b,我们有)pmod(4acby22，特别地，当p是奇素数时，(p,2a)=1,上述同余式等价于同余式(2)2020/1/30数论一二次同余式的概念定义1设m是正整数，若同余式1)m,a(),mmod(ax2有解，则a叫做模m的平方剩余(二次剩余)；否则，a叫做模m的平方非剩余(或二次非剩余).例11是模4的平方剩余，-1是模4的平方非剩余.例21，2，4是模7的平方剩余，-1，3，5是模7的平方非剩余.2020/1/30数论二二次同余式的应用例3-1，1，2，4，8，9，13，15是模17平方剩余；3，5，6，7，10，11，12，14是模17平方非剩余.因为,116134,9143,4152,116122222222)17(mod1398,15107,2116,8125222222222020/1/30数论2020/1/30数论二二次同余式的应用例4求满足方程)7(mod1:32xxyE的所有点.解：对x=0,1,2,3,4,5,6,分别求出y.x=0,y2=1(mod7),y=1,6(mod7).x=1,y2=3(mod7)，无解，2020/1/30数论二二次同余式的应用x=2,y2=4(mod7),y=2,5(mod7)，x=3,y2=3(mod7),无解，x=4,y2=6(mod7),无解，x=5,y2=5(mod7),无解，x=6,y2=6(mod7),无解，2020/1/30数论二二次同余式的应用例5求满足方程)7(mod2:32xxyE的所有点.解：对x=0,1,2,3,4,5,6,分别求出y.x=0,y2=2(mod7),y=3,4(mod7).x=1,y2=4(mod7),y=2,5(mod7)，2020/1/30数论二二次同余式的应用x=2,y2=5(mod7),无解，x=3,y2=4(mod7),y=2,5(mod7)，x=4,y2=0(mod7),y=0(mod7)，x=5,y2=6(mod7),无解，x=6,y2=0(mod7),y=0(mod7).2020/1/30数论二二次同余式的应用例6求满足方程)7(mod12:32xxyE的所有点.解：对x=0,1,2,3,4,5,6,分别求出y.x=0,y2=1(mod7),y=1,6(mod7).x=1,y2=4(mod7),y=2,5(mod7)2020/1/30数论二二次同余式的应用x=2,y2=6(mod7),无解，x=3,y2=6(mod7),无解，x=4,y2=3(mod7),无解，x=5,y2=3(mod7),无解，x=6,y2=5(mod7),无解，2020/1/30数论二二次同余式的应用例7求满足方程)7(mod1:32xxyE的所有解.解：对x=0,1,2,3,4,5,6,分别求出y.x=0,y2=1(mod7),y=1,6(mod7).x=1,y2=1(mod7),y=1,6(mod7)，2020/1/30数论二二次同余式的应用x=2,y2=0(mod7),y=0(mod7)，x=3,y2=4(mod7),y=2,5(mod7)，x=4,y2=5(mod7),无解，x=5,y2=2(mod7),y=3,4(mod7)，x=6,y2=1(mod7),y=1,6(mod7).2020/1/30数论三模为奇素数的平方剩余与平方非剩余我们讨论模为素数p的二次同余式1),(),(mod2papax(1)定理1（欧拉判别条件）设p是奇素数，(a,p)=1,则(i)a是模p的平方剩余的充分必要条件是2020/1/30数论三模为奇素数的平方剩余与平方非剩余);(mod121pap(2)(ii)a是模p的平方非剩余的充分必要条件是);(mod121pap(3)并且当a是模p的平方剩余时，同余式(1)恰有二解.2020/1/30数论三模为奇素数的平方剩余与平方非剩余证(i)因为p是奇素数，所以有表达式xaxxqaxxaaxxxxppppp)1()()()1())((2122121212其中q(x)是x的整系数多项式.若a是模p的平方剩余，即x2≡a(modp)有二个解x，根据3.4定理5，余式的系数被P整除，即1|21pap，所以(2)式成立.定理5设p是一个素数，n是一个正整数，n≤p.那么同余式f(x)=xn+…+a1x+a0≡0(modp)有n个解的充分必要条件是xp–x被f(x)除所得余式的所有系数都是P的倍数2020/1/30数论三模为奇素数的平方剩余与平方非剩余反过来，若(2)成立，则同样根据3.4定理5，我们有同余式x2≡a(modp)有解，即a是模p平方剩余.(ii)因为p是奇素数，(a,p)=1,根据2.4定理1（欧拉定理），我们有表达式)(mod01)1)(1(12121paaappp2020/1/30数论三模为奇素数的平方剩余与平方非剩余再根据1.4定理2，我们有1|21pap或1|21pap因此，结论(i)告诉我们：a是模p的平方非剩余的充分必要条件是)(mod121pap定理2若p是素数，如果p|ab,则有p|a或p|b2020/1/30数论例1利用定理判断2020/1/30数论例2判断137是否为模227平方剩余.解：根据定理1，我们要计算：)227(mod1371371132/)1227(运用模重复平方计算法，设m=227,b=137,令a=1,将113写成二进制，2020/1/30数论6542221113我们依次计算如下：(1)n0=1,计算)227(mod155,1372100bbbaan(2)n1=0,计算)227(mod190,13721201bbaa(3)n2=0,计算)227(mod7,13722312bbaa2020/1/30数论(4)n3=0,计算)227(mod49,13723423bbaa(5)n4=1,计算)227(mod131,1302454344bbbaan(6)n5=1,计算)227(mod1366,52555455bbbaan(7)n6=1,计算)227(mod2266656nbaa2020/1/30数论因此，137为模227平方非剩余.推论设p是奇素数，(a1,p)=1,(a2,p)=1,则(i)如果a1,a2都是模p的平方剩余，则a1a2是模p的平方剩余.(ii)如果a1,a2都是模p的平方非剩余，则a1a2是模p的平方剩余.(iii)如果a1是模p的平方剩余，a2是模p的平平方非剩余，则a1a2是模p的平方非剩余2020/1/30数论证：因为2122112121)(pppaaaa所以由定理1即得结论.定理2设p是奇素数，则模p的简化剩余系中平方剩余与平方非剩余的个数各为(p-1)/2,且(p-1)/2个平方剩余与序列：222)21(,,2,1p(4)中的一个数同余.且仅与一个数同余.2020/1/30数论证:由定理1，平方剩余的个数等于同余式)(mod121pxp的解数，但1|1121ppxx由3.4定理5，此同余式的解数是21p，故平方剩余的个数是21p，而平方非剩余个数是p-1-21p=21p.定理5设p是一个素数，n是一个正整数，n≤p.那么同余式f(x)=xn+…+a1x+a0≡0(modp)有n个解的充分必要条件是xp–x被f(x)除所得余式的所有系数都是P的倍数2020/1/30数论再证明定理的第二部分：若(4)中有两个数模p同余，即存在)(mod21pkk使得)pmod(kk2221则21212121||)(mod0))((kkpkkppkkkk或因此，但,2/)1(,121pkk故ppkkppkk1||,122121从而，k1=k2,矛盾.2020/1/30数论例1求17和19的平方剩余和平方非剩余2020/1/30数论本节小结二次同余式的概念，二次同余式的运用，欧拉判别条件2020/1/30数论作业习题4.91，4，6，8补充一题：