现在的位置: 首页 > 综合 > 正文

关于《中国剩余定理》

2013年02月18日 ⁄ 综合 ⁄ 共 389字 ⁄ 字号 评论关闭

   中国古代求解一次同余式组的方法。是数论中一个重要定理。又称中国剩余定理

   我国古代算书《孙子算经》中有“物不知数”问题:“今有物不知其数,三三数之余二 ,五五数之余三 ,七七数之余二,问物几何?”答为“23”。

 

    孙子问题的解法是找出3个关键数 35, 63, 30;

              35——能被5和7整除,被3除余2

              63——能被3和7整除,被5除余3

              30——能被3和5整除,被7除余2

   根据和的整除性可知:35+63+30=128 一定满足 "被3除余2,被5除余3,被7除余2”,但不一定是最小的,要得到满足条件的最小数,

只要减去3,5,7的最小公倍数的若干倍就行了。

           3,5,7 的最小公倍数为105

           128 mod 105 = 23          所以 23 就是满足条件的最小的数。

抱歉!评论已关闭.