中国剩余定理的改进.doc

  1. 1、本文档共3页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
中国剩余定理的改进

孙子定理的一点改进 摘要:对孙子定理稍加改进,略去了定理的最后一步.从而减少了计算的工作量,特别是未知量多时,使位数大大降低. 关键词:同余方程 算法 完全剩余系 关于解联立同余方程组的问题,我国古代取得了辉煌的成果,这就是著名的中国剩余定理,又称孙子定理 1, 在孙子算经里曾提出并解决了下列的问题 "今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?" 其解法为"三三数之剩二,置一百四十,五五数之剩三,置六十三,七七数之剩二,置三十,并得之得二百三十三,以二百十减之即得"答案是"有物二十三" 把这个问题的提法和解法用现在的说法来表达,它可以写成这样: 解同余方程组: 这个具体问题得答案是 一般来说,若一数用3除余a,用5除余b, 用7除余c,则此数是 关于这个问题的一般解法,在明朝程大位的《算法归宗》里有一首歌,就是"三人同行七十稀,五朵梅花二十一,七子团圆整半月,除百零五便得知"究竟70,21,15是怎样得来得呢?这将从下列定理中看出: 定理:若是两两互质的正整数,令 则) 这n个同余式只有一个公共解. 这就是著名的中国剩余定理,又称孙子定理[1][2][3],中国历代数学家曾经给这个定理内的各种数规定了一定的名称,笔者认为清朝黄宗宪的"大衍求一术"的规定最为全面,他是这样规定的: 定母: 衍母: 衍数: 乘数: 用数: 剩数; 各总: 所求率: 所求总:所求率被M除后的最小正余数. 2, 笔者在研究洛阳民间流传的拣桃问题中[4],遇到了需要求十四个同余式组成的同余方程组。   这个问题的是一个十六位的数字,就更大了,这就迫使笔者考虑这一问题,孙子定理能否改进. 3, 笔者改进的算法如下: 令:使 再令使 依次类推,若已经求出则令使其 这里的,这算法是递推的 证明:用数学归纳法 当t=1时又故 又所以是一个完全剩余系,从而即 故    假设 以本文开头的题目为例,用我们改进的算法来解: 令: 令 即    上面提到的实际问题用此法解得      再举一个例题:二数余一,五数余二,七数余三,九数余五,问本数? 解: 参考文献: [1]华罗庚 《数论导引》  第一版,北京  科学出版社 1957 32--34 [2]闵嗣鹤 《初等数论》  第二版  北京  人民教育出版社 1982 61--63 [3]陈景润 《初等数论》  第一版 北京  科学出版社 1978 83--85 [4]符文通 马国祥 从拣桃问题谈起 《全国第五届MPMH会议文集》 西南交通大学出版社1994 334—339 洛阳大学学报(自然科学版) 1995年第二期 … - 52 -

文档评论(0)

wuailuo + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档