中国剩余定理的应用Zhong guo sheng yu ding li de ying yong

源于中国古代名题 “物不知数”(参见“物不知数”条)。中国剩余定理又叫孙子定理，由于此定理在现代数字中占有重要地位， 被国际数学界称为中国剩余定理。从数论的角度，这一定理可陈述如下：
设n₁、n₂, …n_k 为k个两两互素的自然数，m₁、m₂、…，m_k为任意k个整数，则存在自然数m，满足：m≡mi (mod ni), i=1, 2…，k。“物不知数： 物不知其数，三三数之余2，五五数之余3，七七数之余二。”不仅提出了问题而且通过歌诀“三人同行七十稀、五树梅花廿一枝， 七子团圆正半月、除百零五便得知。”给出了解法。
一般地， 求m的方法如下：
令 N₁＝，那么N1与_ni互素(因为n₁、…nk两两互素)，所以存在a_i，使a_iN_i≡1(modnl)。置m=m1a1N1+m2a2N₂+…+m_ka_kN_k则m即为所求。
例1:在522后面添上三位数字，要求所得的六位数能被7、8、9整除， 添上的三个数字是什么？
解：所有余数(m₁)都是0，可以看作中国剩余定理的特殊情况，求解只须考虑口诀的最末 一句“除百零五便得知”即可。7、8、9的公倍数为504，所得六位数介于522 000与523 000之间，522 000除以504商为1 035因此，所得六位数为504×1 036=522 144与504×1 037=522 648，即添上的三个数字可以是1、4、4或6、4、8。
例2:有一个整数，除以3余数是2，除以5余数是3, 问这个数除以15余数是几？
解： 由辗转相除可知 2×3=6≡1(mod5),2×5=10≡1(mod3)，再由中国剩余定理3×6+2×10=38，满足要求，38≡8(mod15)，这个数除以15余数是8。
例3:在一个圆圈上有几十个孔(不到100个)，如图，小明像玩跳棋那样，从A孔出发沿着逆时针方向，每隔几个孔跳一步，希望一圈后能跳回到A孔，他先试着每隔2孔跳一步，结果只能跳到B孔，他又试着每隔4孔跳一步，也只能跳到B孔，最后他每隔6孔跳一步，正好跳回到A孔，你知道这个圆圈上共有多少个孔吗？
解： 把这道题翻译成数学语言如下：有一个数，被3除余1，被5除也余1，被7除尽，并且这个数小于100，问这个数是几？由中国剩余定理的解法口诀，所求的数是1×70+1×21=91, 故圆圈上有91个孔。