一次同余方程组的一种解法

一次同余方程组的一种解法一次同余方程组的一种解法一次同余方程组的一种解法第22卷第3期 200t年6月温州师范学院学撤(自然科学版) JOURN;d~OFWENZHOUTEACHERSODLLEGE(NatSci Vo【22No3 Jun200l 一次同余方程组的一种解法王靖庶 (温州帅范学院第一初等教育学院浙江瑞安325200) 摘要提出一个较孙子定理简易得多的一次同条方程组韵解法关键词同泉方程组孙子定理递推累加 0075一(03) 中图分类号O156L文献标识码A文章编号10060375(2001)0...

一次同余方程组的一种解法一次同余方程组的一种解法第22卷第3期 200t年6月温州师范学院学撤(自然科学版) JOURN;d~OFWENZHOUTEACHERSODLLEGE(NatSci Vo【22No3 Jun200l 一次同余方程组的一种解法王靖庶 (温州帅范学院第一初等教育学院浙江瑞安325200) 摘要提出一个较孙子定理简易得多的一次同条方程组韵解法关键词同泉方程组孙子定理递推累加 0075一(03) 中图分类号O156L文献标识码A文章编号10060375(2001)03—介绍同余方程组 fzI(rood lz!(meal 【r"(rood) (这里,~I'/2,…,m两两互素)的解法常采用孙子定理(或称中国剩余定理):若?2,令 M—m m=M.=M_..?=mM,则(L)恰有一整数解. 三MIMIcI+M2M2c2十…+Mn(m.dM) 这里M.,是同余方程M.M1(mod.)的解,i=L,2,…,k 现提出另一种解法: 这里A4,是满足同余方程 MM】口,(reed+1)(3) 的整数解,i=1,2,…,k1, 则(1)的解就是,72a(rood),这里Ms=Im!…m. 本解法的基本思路是:先解(1)中任意两个方程构成的同余方程组,这里不妨就设为 jI(modlr4) lzc2(meal7;q2) 由形如(3)的同余方程解得整数M,因为n:?+MM&.+(一n)=c(mc~t"),满足(4) 中的第二个方程,而:=el+C(roodm)又满足(4)中第一个方程,t,m互素,所以" (modM,)是(4)的解,接着再在(1)中取出一个方程(不妨就取第三个)构成如下同余方程组 =日2(modM2)… ) 【ic3【modm3) 鞯馨品望躬).男.温州帅范学院第一初等教育学院高缎讲师 ) 十 ? 一 l 峨 d m m = 令温螂师范学院(自辅科学版)2001年第22卷依(2),(3)求解,并类似可验证 .=n2+M2M2(roodM3) 是(5)的解,依次求解同余方程组仁(moJM,)(moJr,J…)(6) 最后得到的 I(tBoJM') 就是同余方程组(1)的解实际上,ai即为(1)中前i个方程构成的同余方程组的解,i=l,2,一,,这是一种递推的解法因为只是接连求解形如(6)的只含有两个方程的同余方程组,因此,此法理论简明,其依据就是:若 ,互素,形~11(4)的同余方程组恰有解: ?(tBoJm1m2) 这里是满足同余方程组(4)的一个整数.(6)本质上亦即(4),因为M与m:1互素是显然的每次求解(6)时需解的同余方程(3)相当于孙子定理中的同余方程MMI-----1(roodm)且M 较孙子定理中的数值要小(1)的整个求解过程中,需要解的同余方程还少一个,由此可见,其计算要简约得多还可将本法最后的得解写成类似于孙子定理中最后得解的形式:(这里只是为了比较,实际求解时即为最后的") . 27=l十MlM1+M2M2+…+M'lM 现举"韩信点兵"问题(其文字表述见后)为例说明 fz1(5) J=5(6) T4(m7) 【z;10(rood11) 依孙子定理,列下表进行计算表l M!MM,MJ 46231386 385ll925 330ll320 210l2lcwl 最后得解 I386十1925十1320+2100673I21I1(m0d2310) 用本文提出的方法,也以列表进行计算: 袁2 l 1l ll l99 由(2)式,表中每行的M:,M:相乘,加该行的n即为下行的雹,1.表上作业更为简便 76? (7) 蔫 3蝴王靖庶一改列泉方程蛆的一种解法由表可得n一19g21ll(rood2310)即为(7)的解对于投有同余方程知识的读者,如小学生,用本文解法的思路去解同余问题可如下进行:仍以"韩信点兵"问题为例,有兵一队,若列成五行纵队,则余一人;列成六行纵队,则余五人;列成七行纵队,则余四人; 列成十一行纵队,则余十人,求兵数第一步固五行纵队余一人,该队兵数或为6,或为1l,或为16,……即由1或1逐次累加5得到累加的同时用6试除,求得第一个余数为5的数时,累加停止,得到同时满足前两个条件的最小自然数,这里求得11 第二步为保证前两个条件总能满足,11或l1逐次累加5和6的最小公倍数3O,得到:l1,41,71, …… 累加同时用7试除,求得第一个余数为4时,累加停止,得到同时满足前三个条件的最小自然数这里仍是11,属特例,无须累加第三步为保证前三条件总能满足,11或11逐次累加5,6和7的最小公倍数,累加的同时用11试除,求得第个余数为1O的数即为本题的解这里在第1O次累加试除后得2111 上述累加试除的过程在计算机上是极易实现的. 综上所述,本文提出的解法理论浅显,易懂易学,属于一种递推解法,启动快,计算得值小,易于计算机编程以上乞教于各位前辈同仁希冀此解法能得以推广,特别是在给中小学生讲解同余问题时运用参考文献【]陈景润初等数论fM]北京科学出版社.197812 2]叫景梅数论简明教程[M]银川:中夏^民版社,1998.8 ASolutionofaSystemofLinearCoresidualEquations wANGJing—sh LTheFristE&vnemaryEducationCollege,WenzhouTeachers(}Ie AbstractHereisanewmethodintroducedforsolvingasystemofc(residualequati0nsItonlyn eed『() solveasystemcomposedn{twoequationseachtime,andiseKsentlallyarecursivesoluti0n 口mcessFurthe卜 mOTCthemethodcanbeusedprimarilythroughaccumulatingandtria1dividing. KeywordsG.,residualequationsChine-seremaindertheoremRecursi0nACCUmuIati[】g

                    本文档为【一次同余方程组的一种解法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

一次同余方程组的一种解法

你可能还喜欢