中国剩余定理
定理得内容：
若某数x分别被d1、d2、…、dn除得的余数为r1、r2、…、rn，则x可表示为下式：x=R1r1+R2r2+…+Rnrn+RD
其中R1是d2、d3、…、dn的公倍数；而且被d1除，余数为1；…、Rn是d1、d2、…、dn-1的公倍数；而且被dn除，余数为1；D是d1、d2、…、dn的最小公倍数；R是任意整数，可根据实际需要决定，且d1、d2、…、dn必须互质，以保证每个Ri（I=1，2，…，n）都能求得。 一、剩余问题
在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题。二、两个定理
定理1：几个数相加，如果只有一个加数，不能被数a整除，而其他加数均能被数a整除，那么它们的和，就不能被数a整除。
如：10能被5整除，15能被5整除，但7不能被5整除，所以（10+15+7）不能被5整除。
定理2：二数不能整除，若被除数扩大（或缩小）了几倍，而除数不变，则其余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。 如：22÷7＝3……1
（22×4）÷7＝12……1×4（＝4）
（要余2即 22×2÷7＝6……2）
（22×9）÷7＝28……1×9-7（＝2）
（想余5则22×5÷7＝15……5）
三、读解《中国剩余定理》
中国数学史书上记载：在两千多年前的我国古代算书《孙子算经》中，有这样一个问题及其解法：
今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？
答曰：23
术曰：“三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十。并之，得二百三十三，以二百一十减之即得。”
“术”即解法。书中还介绍了上述问题中余数为一的一般解法：凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一则置十五；一百六以上，以一百零五减之即得。
在明朝程大位著《算术统宗》一书中，把上述问题的基本解法，用诗句概括为：
三人同行七十稀，五树梅花廿一枝，
七子团圆正半月，除百令五便得知。
解法1：依定理译成算式解为：
70×2＋21×3＋15×2＝233
233－105×2＝23
这就是享誉中外的《中国剩余定理》。对此古代剩余问题，时至今日另有解法。
解法2：用各除数的“基础数”法解。
基础数的条件：
（1）此数必须符合除数自身的余数条件；
（2）此数必须是其他所有各除数的公倍数。
（一）求各除数的最小公倍数
［3，5，7］＝105
（二）求各除数的基础数
（1）［3］ 105÷3＝35
［35］÷3＝11……2
（2）［5］ 105 ÷ 5＝21
21÷5＝4……1（当于3）
∵1×3＝3 21×3＝［63］
（3）［7] 105 ÷ 7＝15
15 ÷ 7＝2……1（当于2）
∵1×2＝2
∴15×2＝［30］
（三）求各基础数的和
35+63+30＝128
（四）求基准数（最小的，只有一个）
128-105=23
（五）求适合条件的数X
X＝23+105K（K是整数）
（注：此法易行，且具有一般性）
解法3：用枚举筛选法解
按除数3，7同余2，依次逐一枚举；随后用除以5余3，进行筛选，便可获解。
摘录条件
3......2
（基准数） ÷5……3 同余 2
7......2
（一）求3和7的最小公倍数
［3，7] ＝21
（二）进行枚举筛选
（1）21＋2=23 23÷5＝4……3
一般地有：X=基准数+各除数的最小公倍数×K（K是整数）
四、剩余问题的解法与应用
例：韩信点兵，有兵一队，若列成五行纵队，则末行一人；若列成六行纵队，则末行五人；若列成七行纵队，则末行四人；若列成十一行纵队，则末行十人，求兵数至少有多少人？
用基础数法解：
5......l
基准数（2111）÷6……5
7......4
11......10
（一）求各除数的最小公倍数
［5， 6， 7， 11]＝2310
（二）求各除数的基础数
（l）［5] 2310÷5＝462
462÷5＝92……2
∵2×3－5＝1
∴462×3＝［1386］
（2）［6] 2310÷6＝385
385÷6＝64……1
∵ 1×5＝5
∴385×5＝［1925］
（3）［7］ 2310÷7＝330
330÷7＝47……1
∵1×4＝4
∴330×4＝［1320］
（4）［11] 2310÷11＝210
210÷11＝19……1
∵1×10＝10
∴210×10＝［2100］
（三）求各基础数的和
1386＋1925＋1320＋2100＝6731
（四）求最小的基准数
6731－2310×2＝2111（人）
（五）求最适合条件的数X
X=2111＋2310K（K为整数）
答：这队兵至少有2111人。
注：各除数应两两互质，可确保命题的真实性。
五、推导《3、5、8剩余定理）及启用
题目：一个数除以3余2；除以5余3；除以8则余1。此数最小是多少？
摘录条件 3……2
（基准数）（113）÷5……3
8......1
A、推导定理：只要能确定3、5、8各除数的余数均为1的基础数，便可推导出定理，随后再乘以各对应的余数，即可依此定理解题。
（一）［3、5、8]＝120
（二）求各除数的余数均为1的基础数
（1）［3]120÷3＝40
［40］÷3＝13……1
（2）［5］120÷5＝24 24÷5＝4……4
∵4×4－5×3＝l
∴24×4＝［96]
（3）［8]120÷8＝15 15÷8＝1……7
∵7×7－8×6＝1
∴15×7＝［105]
由此得出《3、5、8剩余定理》诗曰：
三人同行40多，五树梅花96朵，
八仙过海105招，除百二十便解惑。
（三）分别乘以各对应的余数再求和而获解
40×2＋96×3＋105×l＝473
（四）求最小的基准数
473－120×3＝113
B、启用定理，再解两题
（一） 3……1
（79）÷5……4
8......7
解：40×1＋96×4＋105×7＝1159
1159－120×9＝79
（二） 3……2
（11）÷5……1
8......3
解：40×2＋96×1＋105×3＝491
491－120×4＝11
C、补充《3、4、5剩余定理》
三人同行40里，四季花开45枝，
五朵金花36浪，除去六十便得知。
3......2
（53）÷4……1
5......3
解：40×2＋45×1＋36×3＝233
233－60×3＝53
由此可知，“剩余问题”的“解法定理”，都是可以推得的，都是非常灵验的。
通过对“剩余问题”的研讨，使我们进一步认识了其“解法定理”，提高了解题能力，证明其解题方法可行、实用、有趣和灵活多样。《3、5、8剩余定理》、《3、4、5剩余定理》……《a、b、c剩余定理》等“解法定理”的推导成功，证明对“剩余问题”完全可以运用“定理解题”。解 2 ：读解《中国剩余定理》
中国数学史书上记载：在两千多年前的我国古代算书《孙子算经》中，有这样一个问题及其解法：
今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？
答曰：23
《孙子算经》中给出这类问题的解法：“三三数之剩二，则置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五，一百六以上，以一百五减之，即得。”用现代语言说明这个解法就是：
首先找出能被5与7整除而被3除余1的数70，被3与7整除而被5除余1的数21，被3与5整除而被7除余1的数15。
所求数被3除余2，则取数70×2＝140，140是被5与7整除而被3除余2的数。
所求数被5除余3，则取数21×3＝63，63是被3与7整除而被5除余3的数。
所求数被7除余2，则取数15×2=30，30是被3与5整除而被7除余2的数。
又，140＋63＋30=233，由于63与30都能被3整除，故233与140这两数被3除的余数相同，都是余2，同理233与63这两数被5除的余数相同，都是3，233与30被7除的余数相同，都是2。所以233是满足题目要求的一个数。
而3、5、7的最小公倍数是105，故233加减105的整数倍后被3、5、7除的余数不会变，从而所得的数都能满足题目的要求。由于所求仅是一小队士兵的人数，这意味着人数不超过100，所以用233减去105的2倍得23即是所求。
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
