韩信点兵问题的求解公式

2023-11-01 08:45周锡来
数学之友 2023年13期

周锡来

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

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

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.