一、剩余问题
在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题。
二、两个定理
定理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剩余定理》等“解法定理”的推导成功，证明对“剩余问题”完全可以运用“定理解题”。
中国剩余定理
数学研究所 李文林 袁向东
在我国古代劳动人民中，长期流传着“隔墙算”、“剪管术”、“秦王暗点兵”等数学游戏。有一首“孙子歌”①，甚至远渡重洋，输入日本：
“三人同行七十稀，五树梅花廿一枝，
七子团圆正半月，除百零五便得知。”
这些饶有趣味的数学游戏，以各种不同形式，介绍世界闻名的“孙子问题”的解法，通俗地反映了中国古代数学一项卓越的成就。
“孙子问题”在现代数论中是一个一次同余问题，它最早出现在我国公元四世纪的数学著作《孙子算经》中。《孙子算经》卷下“物不知数”题说：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？显然，这相当于求不定方程组
N=3x+2，N=5y+3，N=7x+2
的正整数解N，或用现代数论符号表示，等价于解下列的一次同余组：
N 2(mod3) 3(mod5) 2(mod7)②
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论