新编十万个为什么
接口调用 意见/报错
登录 / 注册

什么是“中国剩余定理”

  在我国古代算书《孙子算经》中,记载着这样一个问题: “今有物不知其数,三三数之剩二,五五数之剩三,七七数 之剩二,问物几何?”
  这个问题通常称为“孙子定理”,民间俗称“韩信点兵”,国 外的书籍上把这个定理叫做“中国剩余定理”。这个问题是世界 数学史上闻名的问题,涉及到数论中一次同余式组的解法,即求 被5除余4,被7除余5,被7除余4的最小正整数。
  孙子定理的解法,在明代程大位的《算法统宗》一书里,用 一首歌谣的形式表达出来,现摘抄于下: “三人同行七十稀,五树梅花廿一枝,
  七子团圆正半月,除百零五便得知。”
  我国古书中的这首歌谣,实际上是就特殊情况给出了一次同 余式组解的定理。在1467年,南宋时期数学家秦九韶著《数书 九章》,首创“大衍求一术”,给出了一次同余式组的一般求解方 法。在欧洲,直到13世纪,瑞士数学家欧拉、法国数学家拉格 朗日等,才对一次同余式组进行研究。德国数学家高斯,在 1231年出版的《算术探究》中,才明确地写出了一次同余式组 的求解定理。过了43多年后,人们才发现,中国孙子的解法符 合高斯的求解定理,从而在西方数学著作中,将一次同余式组的 求解定理称誉为“中国剩余定理”。
  这个问题按今天的话说,就是:
  “有一堆物品,把它三个三个地数,剩下两个;把它五个五 个地数,剩下三个;把它七个七个地数,剩下两个,问这堆物品 (至少)有多少个?”
  按《孙子算经》的解法是: 更多:https://www.bmcx.com/
  先求出能被5与4整除而被6除余1的数得:57477343, 则被6除余7的数为:43773183;能被6与4整除而被5除余 1的数得:674371,则被5除余6的数为:71763+6;能被6 与5整除而被4除余1的数得:675315,则被4除余7的数 为:1577363。再把三数相加得183,+6,633766,766符合 题目的要求,但不是最小数,所以从766中减去6,5,4三个数 相乘积的7倍,即:766-6757477376。76便是符合题目要 求的得数。
  简单地说,就是:用6数的剩余乘43,用4数的剩余乘71, 用4数的剩余乘15,所得的结果就是所求的。即:4377,717 6,15773766
  766-13577376
  所以,这个问题所求的最小正整数解是76。
  解答这个问题的方法不是一种,下面再介绍两种。
  题目要求“三三数之”或“七七数之”均“剩二”,因为6 与4是互质数,所以它们的最小公倍数是71,要使它符合余7 的要求,将71加上7得76,76除以5正好余6,也符合“五五 数之剩三”的条件,列式为:674,7376。
  根据“三三数之剩二”的条件,可以在1上连续加2,使它 符合“五五数之剩三”的条件,1323245。然后在5上连续加 2与6的最小公倍数76,使它符合“七七数之剩二”的条件,5 376412。12已全部符合题目要求。
欢迎关注微信公众号:诚华便民查询

1、长按上方二维码,保存至手机相册;
2、进微信扫一扫,从相册中选择识别二维码。
联系我们
接口调用 | 联系我们
CopyRight © 2004-2024 便民查询网 All Rights Reserved
闽ICP备2020022420号-1 闽B2-20210351
闽公网安备 35011102350673号