偶看新闻刘国梁打人视频:孙子定理——中国剩余定理
来源：百度文库 编辑：偶看新闻 时间：2024/04/28 07:50:13
我国古代数学名著《孙子算经》载有一道数学问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”这里的几何指多少的意思。翻译成数学语言就是：求正整数N，使N除以3余2，除以5余3，除以7余2。
如何求符合上述条件的正整数N呢？《孙子算经》给出了一个非常有效的巧妙解法。术曰：“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之，得二百三十三。以二百一十减之，即得。凡三、三数之剩一，则置七十；五、五数之剩一，则置二十一；七、七数之剩一，则置十五。一百六以上，一百五减之，即得。”
过了一千多年，到了十六世纪，数学家程大位在他所著的《算法统宗》里把这个问题的解法用歌诀形式表述出来。三人同行七十稀， 五树梅花廿一枝，七子团圆正月半，除百零五便得之。
歌诀的前三句给出了三组数，后一句给出了一个数：
3 70
5 21
7 15
105
三组数的共同特征是：
70除以3余1，除以5、7余0； 21除以5余1，除以3、7余0； 15除以7余1，除以3、5余0。
首先程大位把不同的余数问题统一化为标准的余数问题。然后，他把复杂难解的问题化解为三个易解的问题。70、21、15分别是满足第一、二、三行条件的最小解。
2×70满足原题第一个余数条件，且被5、7整除。
3×21满足原题第二个余数条件，且被3、7整除。
2×15满足原题第三个余数条件，且被3、5整除。
统统相加得和：N=2×70+3×21+2×15=233。
N必然满足原题所有三个余数条件。但N不一定是最小的。歌诀最后一句“除百零五便得知”，这里“除”的意思是“减”，意即从233中减去3、5、7的最小公倍数105的倍数便得到23。这个23就是问题的最小解。这最后一句也可以理解为N除以105的余数就是问题的最小解。
韩信点兵 秦朝末年，楚汉相争。有一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是，韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更认为韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步逼近，楚军乱作一团。交战不久，楚军大败而逃。',1)">
如何求符合上述条件的正整数N呢？《孙子算经》给出了一个非常有效的巧妙解法。术曰：“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之，得二百三十三。以二百一十减之，即得。凡三、三数之剩一，则置七十；五、五数之剩一，则置二十一；七、七数之剩一，则置十五。一百六以上，一百五减之，即得。”
过了一千多年，到了十六世纪，数学家程大位在他所著的《算法统宗》里把这个问题的解法用歌诀形式表述出来。三人同行七十稀， 五树梅花廿一枝，七子团圆正月半，除百零五便得之。
歌诀的前三句给出了三组数，后一句给出了一个数：
3 70
5 21
7 15
105
三组数的共同特征是：
70除以3余1，除以5、7余0； 21除以5余1，除以3、7余0； 15除以7余1，除以3、5余0。
首先程大位把不同的余数问题统一化为标准的余数问题。然后，他把复杂难解的问题化解为三个易解的问题。70、21、15分别是满足第一、二、三行条件的最小解。
2×70满足原题第一个余数条件，且被5、7整除。
3×21满足原题第二个余数条件，且被3、7整除。
2×15满足原题第三个余数条件，且被3、5整除。
统统相加得和：N=2×70+3×21+2×15=233。
N必然满足原题所有三个余数条件。但N不一定是最小的。歌诀最后一句“除百零五便得知”，这里“除”的意思是“减”，意即从233中减去3、5、7的最小公倍数105的倍数便得到23。这个23就是问题的最小解。这最后一句也可以理解为N除以105的余数就是问题的最小解。
韩信点兵 秦朝末年，楚汉相争。有一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是，韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更认为韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步逼近，楚军乱作一团。交战不久，楚军大败而逃。',1)">