《数论算》教案 4章(二次同余方程与平方剩余).doc

《数论算》教案 4章(二次同余方程与平方剩余).doc

ID:56877207

大小:2.16 MB

页数:49页

时间:2020-07-18

《数论算》教案 4章(二次同余方程与平方剩余).doc_第1页
《数论算》教案 4章(二次同余方程与平方剩余).doc_第2页
《数论算》教案 4章(二次同余方程与平方剩余).doc_第3页
《数论算》教案 4章(二次同余方程与平方剩余).doc_第4页
《数论算》教案 4章(二次同余方程与平方剩余).doc_第5页
资源描述:

《《数论算》教案 4章(二次同余方程与平方剩余).doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第4章二次同余方程与平方剩余内容1.二次同余方程,平方剩余2.模为奇素数的平方剩余3.勒让德符号、雅可比符号4.二次同余方程的求解要点二次同余方程有解的判断与求解4.1一般二次同余方程(一)二次同余方程+bx+c≡0(modm),(a0(modm))(1)(二)化简设m=,则方程(1)等价于同余方程问题归结为讨论同余方程+bx+c≡0(mod),(pa)(2)(三)化为标准形式p≠2,方程(2)两边同乘以4a,4+4abx+4ac≡0(mod)≡-4ac(mod)变量代换,y=2ax+b(3)有≡-4ac(mod)(4)当p为奇素数时,方程(4)与(2)等价。即l两者同时有解或无解;有解时,

2、对(4)的每个解,通过式(3)(x的一次同余方程,且(p,2a)=1,所以解数为1)给出(2)的一个解,由(4)的不同的解给出(2)的不同的解;反之亦然。l两者解数相同。结论:只须讨论以下同余方程≡a(mod)(5)【例】化简方程7x2+5x-2≡0(mod9)为标准形式。(解)方程两边同乘以4a=4×7=28,得196x2+140x-56≡0(mod9)配方(14x+5)2-25-56≡0(mod9)移项(14x+5)2≡81(mod9)变量代换y=14x+5得y2≡0(mod9)(解之得y=0,±3,从而原方程的解为x≡(y-5)≡(y-5)≡2(y-5)≡2y-10≡2y-1≡-7,-

3、1,5≡-4,-1,2(mod9))(一)二次剩余【定义4.1.1】设m是正整数,a是整数,ma。若同余方程≡a(modm)(6)有解,则称a是模m的平方剩余(或二次剩余);若无解,则称a是模m的平方非剩余(或二次非剩余)。问题:(1)设正整数a是模p的平方剩余,若记方程(6)中的解为x≡(modm),那么此处的平方根(modm)与通常的代数方程=a的解有何区别?(2)如何判断方程(6)有解?(3)如何求方程(6)的解?(二)例【例1】1是模4平方剩余,-1是模4平方非剩余。【例2】1、2、4是模7平方剩余,3、5、6是模7平方非剩余。【例3】直接计算12,22,…,142得模15的平方剩余

4、(实际上只要计算(12,22,…,72)1,4,9,10,6平方非剩余:2,3,5,7,8,11,12,13,14【例4】求满足方程E:≡+x+1(mod7)的所有点。(解)对x=0,1,2,3,4,5,6分别解出y:=0,≡1(mod7),y≡1,6(mod7)=1,≡3(mod7),无解=2,≡4(mod7),y≡2,5(mod7)=3,≡3(mod7),无解=4,≡6(mod7),无解=5,≡5(mod7),无解=6,≡6(mod7),无解所以,满足方程的点为(0,1),(0,6),(2,2),(2,5)。说明:方程E:≡+x+1的图形称为椭圆曲线。4.1模为奇素数的平方剩余与平方非剩

5、余模为素数的二次方程≡a(modp),(a,p)=1(1)因为=,故方程(1)要么无解,要么有两个解。(一)平方剩余的判断条件【定理4.2.1】(欧拉判别条件)设p是奇素数,(a,p)=1,则(i)a是模p的平方剩余的充要条件是≡1(modp)(2)(ii)a是模p的平方非剩余的充要条件是≡-1(modp)(3)并且当a是模p的平方剩余时,同余方程(1)恰有两个解。(证)先证pa时,式(2)或(3)有且仅有一个成立。由费马定理≡1(modp)-1≡0(modp)≡0(modp)(4)即=但=1或2且素数p>2。所以,p能整除,但p不能同时整除和(否则,p能整除它们的最大公因子1或2)所以,由

6、式(4)立即推出式(2)或式(3)有且仅有一式成立。(i)必要性。若a是模p的二次剩余,则必有使得≡a(modp),因而有≡(modp)。即(modp)。由于pa,所以p,因此由欧拉定理知≡1(modp)。即(2)式成立。充分性。已知≡1(modp),这时必有pa。故一次同余方程≡a(modp),(1≤b≤p-1)(5)有唯一解,对既约剩余系-(p-1)/2,…,-1,1,…,(p-1)/2(6)由式(6)给出的模p的既约剩余系中的每个j,当b=j时,必有唯一的属于既约剩余系(6),使得式(5)成立。若a不是模p的二次剩余,则必有。这样,既约剩余系(6)中的p-1个数就可按j、xj作为一对,

7、两两分完。(b1≠b2,则相应的解x1≠x2,且除了±1之外,每个数的逆不是它本身)因此有由威尔逊定理知与式(2)矛盾。所以必有某一,使,由此及式(5)知,a是模p的二次剩余。(ii)由已经证明的这两部分结论,立即推出第(ii)条成立。其次,若0(modp)是方程(1)的解,则-也是其解,且必有-(modp)。故当(a,p)=1时,方程(1)要么无解,要么同时有两个解。(说明:本定理只是一个理论结果,当p>>

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。