初等数论(严蔚敏版) 12.3 二次互反律

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

1、第三节二次互反律引理p-1设(n,p)1,对于整数k(1k),2以r表示nk对模p的最小非负剩余,kpnm设r,r,,r中大于的有m个,则()(-1).12k2pp证明:在r,r,,r中,假设大于的是a,a,,a,12p-112m22p小于的是b,b,,b,12t2p-1p-1p-1p-1则mt,(nk)(n1)(n2)(n)n2()!.2p-1221k2mt又(nk)aibj(modp),p-1i1j11k2ppap,0pa,ii22则对于1im,1jt

2、,有bpa,jip-1(这说明pa与b恰好是1与之间的全部整数.)ij2p-1否则有整数k,k,1k,k,有ank,bnk,1212i1j220abn(kk)(modp),则p

3、n(kk),ij1212p-1(n,p)1,p

4、kk与1k,k矛盾,12122p-1mt2p-1mmp-1n()!(1)(p-ai)bj(1)()!(modp).2i1j12p-1p-1p

5、()!,由上式知(两边同除以()!),22p-1p-1则n2(1)m(modp),又(n)n2,(

6、n)(1)m(modp),ppnm易知两边分别是1或-1,()(1).p定理1下面的结论成立:2p12(1)()(1)8;pp12nin[]p(2)若n是奇数,(n,p)1,则()(-1)i1.p证明:使用引理中的符号r,a,b,m与t,kijnkp1nkp[]r,1k.kp2p122p1p1(nk)n(12)n.28k1p1p1p1p122nk22nkmt又(nk)p[]rkp[]aibippk1k1k1k1i1j1p12nk

7、mtmp[](pai)bi2aimppk1i1j1i1p1p12nk2mp[]i2aimppk1i1i1p122mnkp1p[]2aimp,p8k1i1p1222mp1nkp1np[]2aimp,8p8k1i1p122mp1nk(n1)p[]2aimp.8pk1i1p-1p若n2,1k,0k,22k12knk0,01,[]0.p2ppp122mp1nk由(n1)p[]

8、2aimp得,8pk1i12p1m(mod2),82p1从而m2k,kZ,822p1p122k()(1)m(1)8(1)8.pp122mp1nk若2

9、n,则由(n1)p[]2aimp得,8pk1i1p1p12nk2nk0p[]mp(mod2),即[]m(mod2),ppk1k1p12nin[]mp()(1)(-1)i1.p推论21当p1(mod8)时设p是素数,则().p-1当p3(mod8)时定理2(二次互反律)p-

10、1q1qp设p与q是不相同的两个素数,则()(-1)22().pq注意•(1)由勒让德符号定义知,(q/p)和(p/q)分别刻画了q是否是模p的平方剩余和p是否是模q的平方剩余,这里正好是模和剩余互换了位置,定理2就是刻画了这两者之间的关系,所以称为二次互反律,或称为二次反转定律.•(2)二次互反律是初等数论中最重要的基本定理之一,它不仅可用来计算勒让德符号,而且它也有重要的理论价值.•(3)需要注意的是,不管是计算勒让德符号,还是判断同余方程的有无解问题,都必须要求勒让德符号下方的数为质数.判定素数模的二次同余方程的可解性

11、,一般地,若p是素数,n计算Legendre符号()可按以下步骤进行:p(1)求出nn(modp),1np;002(2)将n写成nqqqq的形式,0012k其中qZ,q,q,,q是互不相同的素数;12k2p12(3)若某个q2,用()(1)8计算;ipqpi(4)若q2,则用二次互反律将()转化为计算();ipqiqi(5)重复以上步骤,直至求出每个();pknqi(6)计算()().ppi12例1已知563是素数,判定方程x429(mod563)是否有解.4293111331113解:()(

12、)()()()56356356356356331563111156311315631563563563(1)22()(1)22()(1)22()31113224()()()(1)(1)11,方程有解.311