《数论算法》教案章 .pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《《数论算法》教案章 .pdf》由会员分享,可在线阅读,更多相关《《数论算法》教案章 .pdf(49页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第 5章二次同余方程与平方剩余内容1. 二次同余方程,平方剩余2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点二次同余方程有解的判断与求解5.1 一般二次同余方程( 一 )二 次 同 余 方 程2ax bxc0(mod m) , (a0(mod m) ) (1)( 二 )化 简设 mkkppp2121,则方程( 1)等价于同余方程组)()()(kkpcbxaxpcbxaxpcbxaxmod0mod0mod022212212ax bxc0(mod p) ,(pa)(2)( 三 )化 为 标 准 形 式p2,方程( 2)两边同乘以 4a,422xa4abx4ac0
2、(mod p)22bax2b 4ac(mod p)变量代换,y2axb(3)有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 49 页 - - - - - - - - - 2y 2b 4ac(mod p )(4)当 p 为奇素数时,方程( 4)与(2)等价。即两 者 同 时有 解 或 无解 ; 有 解 时 , 对 (4) 的 每 个解pyymod0,通过式(3) (x 的一次同余方程, 且(p, 2a ) 1 , 所 以 解 数 为1 ) 给 出 ( 2 ) 的 一 个
3、解pxxmod0,由( 4)的不同的解给出(2)的不同的解;反之亦然。两者解数相同。结论:只须讨论方程2xa(mod p)(5)【例 5.1.1】 化简方程 7x25x20 (mod 9) 为标准形式。(解)方程两边同乘以4a4728,得196x2140 x560(mod 9)配方(14x5) 225560(mod 9)移项(14x5) 281(mod 9)变量代换 y14x5 得y20(mod 9)(解之得 y0, 3,从而原方程的解为x114 (y5)15(y5) 2(y5)2y102y1 7, 1, 54, 1, 2(mod 9) )( 四 )平 方 剩 余【定义 5.1.1】设 m 是
4、正整数, a 是整数,ma。若同余方程2x a(mod m)(6)有解,则称 a 是模 m 的平方剩余 (或二次剩余 ) ;若无解,则称 a 是模 m 的平方非剩余 (或二次非剩余 ) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 49 页 - - - - - - - - - 【例】1 是模 4 平方剩余, 1 是模 4 平方非剩余。【例】1、2、4 是模 7 平方剩余, 3、5、6 是模 7 平方非剩余。问题:(1)设正整数 a 是模 p 的平方剩余, 若记方程(6
5、)中的解为 xa(mod m) , 那么此处的平方根a(mod m)与通常的代数方程2xa 的解a有何区别?(2)如何判断方程( 6)有解?(3)如何求方程( 6)的解?( 五 )例【例 5.1.2】求以 15 为模的所有平方剩余和平方非剩余。(解)直接计算12,22,142得模 15 的平方剩余( 实际只需计算 12,22, 72)1,4,9,10,6 平方非剩余: 2,3,5,7,8,11,12,13,14 【例 5.1.3】求满足方程 E:2y3xx1(mod 7)的所有整点(即坐标为整数的点) 。(解)对x0,1,2,3,4,5,6 分别解出 y:x0,2y 1(mod 7) ,y1,
6、6(mod 7)x1,2y 3(mod 7) ,无解x2,2y 4(mod 7) ,y2,5(mod 7)x3,2y 3(mod 7) ,无解x4,2y 6(mod 7) ,无解x5,2y 5(mod 7) ,无解x6,2y 6(mod 7) ,无解所以,满足方程的点为(0, 1) , (0, 6) , (2, 2) , (2, 5) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 49 页 - - - - - - - - - 附:方程 E:2y3xx1 的图形称为 椭
7、圆曲线 。5.2 模为奇素数的平方剩余与平方非剩余方程2xa(mod p), (a,p)1 (1)结论: 方程(1) 要么无解,要么有两个解(因为2x2x) 。(p时,方程恰好1 个解)5. 2. 1 平方剩余的判断条件【定理 5.2.1】 (欧拉判别条件 )设 p 是奇素数, (a,p)1,则(i)a 是模 p 的平方剩余的充要条件是21pa1(mod p)(2)(ii)a 是模 p 的平方非剩余的充要条件是21pa1(mod p)(3)并且当 a 是模 p 的平方剩余时,同余方程(1)恰有两个解。(证)先证 pa 时,式(2)或(3)有且仅有一个成立。由费马定理1pa1(mod p)221
8、pa10(mod p)112121ppaa0(mod p)(4)即11pap112121ppaa但1,12121ppaa1 或 2 且 p2。p 能整除112121ppaa,但 p 不能同时整除121pa和121pa(否则, p 能整除它们的最大公因子 1 或 2)由式( 4)知式( 2)或( 3)有且仅有一式成立。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 49 页 - - - - - - - - - (i)必要性: a 是模 p 的二次剩余有0 x使得20 xa(
9、mod p) ,21p20 x21pa(mod p) 。即2110ppax(mod p) 。由于 pap0 x,由欧拉定理10px1(mod p) 。充分性:21pa1(mod p)pa。故一次同余方程bxa(mod p), (1bp1) (5)有唯一解,对既约剩余系21,1,1,21ppA(6)设 bj 时方程( 5)的解jxx(Axj) 。若 a 不是模 p 的二次剩余jxjA 中各数可按 j、xj配对,两两分完。(b1b2,则相应的解 x1x2,且除了 1 之外,每个数的逆不是它本身 )pappmod)!1(21即papmod121(威尔逊定理)与式( 2)矛盾必有某个0j,使00jxj
10、a 是模 p 的二次剩余。(ii)显然( 由(i)的证明即知 )其次,若0 x0(mod p)是方程( 1)的解,则0 x也是其解,且必有0 x0 x(mod p) 。故当(a, p)1 时,方程(1)要么无解,要么同时有两个解。(说明:本定理只是一个理论结果,当p1 时,它并不是一个实用的判断方法 )名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 49 页 - - - - - - - - - 小结:对于任何整数a,方程( 1)的解数可能为paxT;20, 1, 2 【例
11、 5.2.1】设 p19,验证定理 5.2.1 的证明过程。(解)由费马定理18a1(mod 19) ,a1, 2, , 18 方程2x 1(mod 19)只有两个解,即x1(mod 19) 。9a1(mod 19)(视2918aa1(mod 19) ,即9ax) 针对必要性:【例】a17 是模 19 的二次剩余,即存在0 x6 使得26 17(mod 19) 。有21pa9171861(mod 19)【2】2x 2(mod 19)无解,即 a2 是模 19 的二次非剩余。则92119221(mod 19) 针对充分性:【例】a6,21pa96 1(mod 19) ,验证 6 是二次剩余。解方
12、程bx6(mod 19), (1b18) b 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 x 6 3 2 11 5 1 18 14 8 13 其中5? 56(mod 19)所以 6 是二次剩余。又选 a8,21pa98 1(mod 19) ,验证:解方程bx8(mod 19), 1b18 b 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共
13、 49 页 - - - - - - - - - x 8 4 9 2 13 14 12 1 3 16 18 7 5 6 17 10 15 11 1?2?18 (1? 8)(2? 4)(3? 9)(5? 13)(6? 14)(7? 12)(10?16)(11?18)(15?17) 98 1(mod 19)【例 2】判断 137是否为模 227 的平方剩余。(解)首先, 227是素数。其次,计算21227137 1(mod 227)所以, 137 是模 227 的平方非剩余。【推论】设 p 是奇素数, (a1, p)1,(a2, p)1,则(i)若 a1,a2都是模 p 的平方剩余,则a1a2是模
14、p 的平方剩余;(ii)若 a1,a2都是模 p 的平方非剩余,则a1a2是模 p的平方剩余;(iii ) 若 a1是模 p 的平方剩余,a2是模 p 的平方非剩余,则 a1a2是模 p 的平方非剩余。(证)因2121paa212211ppaa5. 2. 2 平方剩余的个数【定理 5.2.2】设 p 是奇素数,则模 p 的既约剩余系中平方剩余与平方非剩余的个数各为(p1)2,且(p1)2 个平方剩余恰与序列12,22,221p中的一个数同余。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
15、 第 7 页,共 49 页 - - - - - - - - - (证)由定理 5.2.1,模 p 的平方剩余个数等于方程21px1(mod p)的解数。但1121ppxx由定理 4.4.5 知,方程的解数为21p,即平方剩余的个数是21p,且平方非剩余的个数是(p1)21p21p。其次,可以证明当1k121p,1k221p,且 k1k2时,有21k22kmod p。故结论成立。(定理 4.4.5:设 p 为素数, n 为正整数, np。则同余方程xf0111axaxaxnnn0 mod p 有 n 个解xxp被xf除所得余式的所有系数都是p 的倍数 )5.3 勒让德符号目的:快速判断整数a 是
16、否为素数 p 的平方剩余。( 一 )勒 让 德 符 号【定义 5.3.1】设 p 是素数,定义 勒让德(Legendre)符号为:L(a, p) pa。当的二次非剩余;是模当的二次剩余;是模当appapa,0, 1,1【推论】整数 a 是素数 p 的平方剩余的充要条件是pa1。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 49 页 - - - - - - - - - (证)由定义 5.3.1。意义:判断平方剩余转化为计算勒让德符号的值。【例 5.3.1】计算勒让德符号1
17、7a的值。其中 a0, 1, 2, , 16。(解)直接计算:1716171517131791781741721711 17141712171117101771761751731 (注:本例仍是利用平方剩余而得到勒让德符号值)问题:反过来,如何快速计算勒让德符号的值,以判断平方剩余。( 二 )( 勒 让 德 符 号 的 ) 性 质【性质 1】 (欧拉判别法则 )设 p 是奇素数,则对任意整数a,有pa21pa(mod p)(证)由定理 5.2.1 即知。【性质 2】p11 (证)显然(因为方程 x2 1 (mod p)始终有解 x 1 (mod p) ,或者由性质 1 立得) 。名师资料总结
18、- - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 49 页 - - - - - - - - - 【性质 3】p1211p。(证)由性质 1 即得。【例 2】1711,1911 【推论】p14mod3,14mod1,1pp(证)p1(mod 4)p4k1p1211pk211 p3(mod 4)p4k3p1211p121k1 另一种描述 :设素数 p2,则 1 是模 p 的二次剩余的充分必要条件是 p1(mod 4) 。【性质 4】ppapa(证)因 x2ap(mod p)x2a(mod p
19、)【推论】若 ab(mod p) ,则papb名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 49 页 - - - - - - - - - 【性质 5】pabpbpa(证)因pab21pab2121ppbapbpa【推论 1】pakkpa【推论 2】当 pa 时,pa21 讨论:确定a 是否是模p 的平方剩余就变为如何计算Legendre 符号pa的值。上述性质可以用来计算pa,并由算术基本定理,设a 的分解式为akkppp2121t1kkppp2121, (t0, 1
20、)则pakpqpqpqpkt21211(t0,1)故只要能计算出p1,p2,pq就可以计算出任意的pa,其中2q是小于 p 的素数。已经解决的计算:p1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页,共 49 页 - - - - - - - - - 剩余的问题:p2,pq的计算。解决这些问题的基础是下面的二次互反律(Gauss定理) 。【性质 6】p28121p【例 3】17281172141621811,19281192121842011,故 2 是模 17 的平方剩余,
21、但不是模19 的平方剩余。【推论】p 为奇素数,则p28mod318mod1,1pp(证)因为当 p8k1 时812p811pp8828kkk(8k2)偶数当 p8k3 时812p82848kk(2k1)(4k1)奇数【例 4】 由于 3171 (mod 8) , 593 (mod 8) , 故3121,9521,即 2 是模 31 的平方剩余,但不是模59名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 49 页 - - - - - - - - - 的平方剩余。【性质
22、7】 (二次互反律,高斯定理 )pq 且均为奇素数,则pqqpqp21211另一表示形式 :pqqp21211qp说明1:符号pq和qp分别刻画了二次同余方程2xq(mod p)和2xp(mod q)是否有解,即 q 是否是模 p 的二次剩余和 p 是否是模 q 的二次剩余,其中正好是模与剩余互换了位置,而性质7 恰好刻画了两者之间的关系,故称为二次互反律 。说明2:由欧拉提出, 高斯首先证明。 已有一百五十多个不同的证明。由二次互反律引伸出来的工作,导致了代数数论的发展和类域论的形成。【推论】 (i)设奇素数 p、q 中至少有一个模4 为 1,则方程2xq(mod p)有解方程2xp(mod
23、 q)有解(ii) 若 pq3(mod 4) ,则方程2xq(mod p)有解方程2xp(mod q)无解(证) (i)设 p1(mod 4) ,即 p4k1,则名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页,共 49 页 - - - - - - - - - pqqppp21211qppk21241qp(ii)此时, p4s3,q4t3,则pqqppp21211qpts2242241qp【例 5】判断 3 是否是模 17 的平方剩余。(解)17331712132117321
24、 所以, 3 是模 17 的平方非剩余。(不但如此, 17 也是 3 的平方非剩余,即 2 是 3 的平方非剩余 )【例 6】判断同余方程2x 137(mod 227)是否有解。(解)已知 137与 227 均为奇素数,所以2271371372271213721227137901375322137513721375513712152113752 1 所以,方程无解。另法:2271372279022712275322227522725227121521227名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
25、- - - - 第 14 页,共 49 页 - - - - - - - - - 521 【例 7】判断同余方程2x1(mod 365)是否有解,若有解,求解数。(解)由于 365573,所以2x 1(mod 365)73mod15mod122xx517311 所以方程有解,且解数为4。【例 8】判断同余方程2x2(mod 3599)是否有解,若有解,求解数。(解)由于 35995961,所以2x2(mod 3599)61mod259mod222xx因为 593 (mod 8) , 即5921, 故方程2x2 (mod 59)无解,从而原方程无解。【例 9】证明形如 4k1 的素数有无穷多。(证
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数论算法 数论算法教案章 2022 数论 算法 教案
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内