韩信点兵问题的求解公式

周锡来

摘 要： 韩信点兵问题是研究带有余数的除法问题，有一定难度且比较抽象，其解决需要一定的解题技巧.近期笔者将多个带有余数的除法问题统一起来进行思考，并获得了具有两个余数问题的一个求解公式，统一地解决了该问题.公式的推导采用比较简单的方法，只用到基本的代数运算，该公式适用于一切有关的韩信点兵问题.文中给出了韩信点兵问题有解的条件：各除数两两互质.进一步提出韩信点兵问题和不定方程之间是互相可以转换的.它们实际上是同一个问题的两个方面，只是求解的未知数不同而已.

关键词： 韩信点兵问题；带有余数的除法；两数互质

1 “韩信点兵”问题

有队士兵，3人一组余2，5人一组余3，7人一组余4，问这队士兵有多少人？

这是我国古代的一道算术题，据说是刘邦问韩信的.韩信随口给出了答案，所以这个问题就被叫做韩信点兵问题.国际上称作中国剩余定理，可能是因为其研究内容为带有余数的除法问题.

韩信点兵问题的数学语言叙述是：已知一个数被P 1除余r 1，被P 2除余r 2，……被P n除余r n，问这个数是多少？其中P 1，P 2…，P n两两互质.

它的运算形式是：设有一数x，满足

x=P 1n 1+r 1，

x=P 2n 2+r 2，

……

x=P nn n+r n. 需说明（r i＜P i），

问这个数x是多少？

这是整数域上的一类特殊的线性方程组.韩信点兵所讨论的，就是求这类方程组的解，下面所讲的数均指整数.如何求解这类韩信点兵问题，很困难，特别是限于算术的方法，技巧性很强，往往还要因题而异.下面给出一个公式，很简单，适用于任何的韩信点兵问题，主要针对带有两个余数的问题.

2 两个余数问题的求解公式

设有一个数x，被P 1除余r 1，被P 2除余r 2，即

x＝P 1n 1+r 1，   （1）

x=P 2n 2+r 2.   （2） 添加（r i＜P i），

问x是多少？其中P 1，P 2互质.

笔者的解法是统一法，在（1）的基础上把它和（2）统一起来.

假设x已经具备了（1），也就是说已经把“被P 1除余r 1”的数都选出来了，排成了一个数列，通项公式是（1）.下面的任务就是要把（1）中“被P 2除余r 2”的数再取出来，这就需要用P 2去除P 1n 1+r 1，把其中P 2的倍数部分分离出来，再看看余下的部分能不能被P 2除余r 2了，关键是P 2除n 1的结果.

假设n 1除以P 2的商是n，余数为r，即

n 1=P 2n+r，r=0，1，2，…（P 2-1）.

把它代入（1），得

x＝P 1P 2n+（P 1r+r 1）.  （3）

这就要看P 1r+r 1能不能被P 2除余r 2了.由于P 1r+r 1的值是由r=0，1，2…（P 2-1）决定的.所以就要看在这些数中能不能找到一个r 0，使P 1r 0+r 1被P 2除余r 2了.如果这个r 0不存在，就说明问题无解.如果这个r 0存在，则将其代入（3），得

x＝P 1P 2n+（P 1r 0+r 1）.   （4）

这样（4）就既能被P 1除余r 1，也能被P 2除余r 2，把（1）和（2）统一起来了.它就是带有两个余数的韩信点兵问题的求解公式.这样求解韩信点兵问题的关键就是求r 0了.下面会指出，在P 1与P 2互质的条件下，r 0是存在且唯一的.

在（4）中，注意到

0≤P 1r 0+r 1＜P 1（P 2-1）+P 1=P 1P 2.

所以，一个除以P 1余r 1，除以P 2余r 2的数，就是除以P 1P 2余P 1r 0+r 1的数，其本质是带有一个余数的除法问题，该结论为韩信点兵问题的进一步讨论奠定了基礎.

3 推广至多个余数问题的求解

【例】     以本文开头的士兵问题为例，设这队士兵有x个人，则

x=3n 1+2，   （5）

x=5n 2+3，   （6）

x=7n 3+4.   （7）

对于（5）和（6），这里P 1＝3，P 2＝5，r 1=2，r 2=3，在r=0，1，2，…（P 2-1），即在r=0，1，2，3，4中，取r 0=2，得

P 1r 0+r 1=3×2+2=8.

其能被P 2＝5除余3，所以满足（5）和（6）的x就是

x＝P 1P 2N+（P 1r 0+r 1）=3×5N+8.   （8）

对于（7）和（8），这里P 1＝7，P 2＝3×5，r 1=4，r 2=8，在r＝0，1，2…，即r=0，1，2，…，14，P 2-1＝0，1，2，…，14中取r 0=7，

P 1r 0+r 1=7×7+4=53.

其能被P 2＝15除余r 2=8，所以满足（7）和（8）的x就是

x=P 1P 2N+（P 1r 0+r 1）=7×（3×5）N+（7×7+4）=105N+53.

这就是这队士兵人数的通解，通常是指53人.

韩信点兵问题的计算公式（4），可以用不定方程来求解，而且也很简单.

从（1）和（2）中消去x并移项得

P 2n  2-P 1n  1=r 1-r 2.   （8）

它是一个关于n 1和n 2的不定方程.由于P 1，P 2互质，方程（8）有解，且根据《不定方程的一个通解公式》里的方法，在r=0，1，2，…，（P 2-1）里存在r 0，能使P 1r 0+（r 1-r 2）被P 2整除，或者说P 1r 0+r 1能被P 2除余r 2，从而得到n 1的解是

n 1=P 2t+r 0.

代入（1）就得到（4）.

这里也为（8）式中r 0的存在性做了补充说明.

不定方程也是可以用韩信点兵问题来求解的.例如可以把方程（8）化为（1）和（2）.

这样不定方程和韩信点兵问题就是同一个问题了，统一在方程组（1）之下.只是所求的未知数不同而已.这也指出，方程组（1）总是可以求解的.

由此，本文对中国古代的一道“韩信点兵”问题进行了详细分析，在此基础上进一步考虑了把多个带有余数的除法问题统一起来，给出了具有两个余数问题的一个求解公式，统一地解决了这个问题.该公式适用于一切有关韩信点兵的数学问题.

诚恳地希望得到同行老师们的点评和意见.

参考文献：

［1］ 李春峰.探索化归思想在高中数学解题中的应用［J］.数学之友，2022，36（6）：53 55.

［2］ 凌翔，崔颖.基于GeoGebra的数学概念的教学探究——以“椭圆定义的多种形式”为例［J］.数学之友，2022，36（6）：68 71.

［3］ 张志刚.曲径通幽处：一道高考模拟题的背景揭示与破解［J］.数学之友，2022，36（6）：80 84.