韓信點兵問題的求解公式

周錫來

摘 要： 韓信點兵問題是研究帶有余數(shù)的除法問題，有一定難度且比較抽象，其解決需要一定的解題技巧.近期筆者將多個帶有余數(shù)的除法問題統(tǒng)一起來進行思考，并獲得了具有兩個余數(shù)問題的一個求解公式，統(tǒng)一地解決了該問題.公式的推導(dǎo)采用比較簡單的方法，只用到基本的代數(shù)運算，該公式適用于一切有關(guān)的韓信點兵問題.文中給出了韓信點兵問題有解的條件：各除數(shù)兩兩互質(zhì).進一步提出韓信點兵問題和不定方程之間是互相可以轉(zhuǎn)換的.它們實際上是同一個問題的兩個方面，只是求解的未知數(shù)不同而已.

關(guān)鍵詞： 韓信點兵問題；帶有余數(shù)的除法；兩數(shù)互質(zhì)

1 “韓信點兵”問題

有隊士兵，3人一組余2，5人一組余3，7人一組余4，問這隊士兵有多少人？

這是我國古代的一道算術(shù)題，據(jù)說是劉邦問韓信的.韓信隨口給出了答案，所以這個問題就被叫做韓信點兵問題.國際上稱作中國剩余定理，可能是因為其研究內(nèi)容為帶有余數(shù)的除法問題.

韓信點兵問題的數(shù)學(xué)語言敘述是：已知一個數(shù)被P 1除余r 1，被P 2除余r 2，……被P n除余r n，問這個數(shù)是多少？其中P 1，P 2…，P n兩兩互質(zhì).

它的運算形式是：設(shè)有一數(shù)x，滿足

x=P 1n 1+r 1，

x=P 2n 2+r 2，

……

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

問這個數(shù)x是多少？

這是整數(shù)域上的一類特殊的線性方程組.韓信點兵所討論的，就是求這類方程組的解，下面所講的數(shù)均指整數(shù).如何求解這類韓信點兵問題，很困難，特別是限于算術(shù)的方法，技巧性很強，往往還要因題而異.下面給出一個公式，很簡單，適用于任何的韓信點兵問題，主要針對帶有兩個余數(shù)的問題.

2 兩個余數(shù)問題的求解公式

設(shè)有一個數(shù)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互質(zhì).

筆者的解法是統(tǒng)一法，在（1）的基礎(chǔ)上把它和（2）統(tǒng)一起來.

假設(shè)x已經(jīng)具備了（1），也就是說已經(jīng)把“被P 1除余r 1”的數(shù)都選出來了，排成了一個數(shù)列，通項公式是（1）.下面的任務(wù)就是要把（1）中“被P 2除余r 2”的數(shù)再取出來，這就需要用P 2去除P 1n 1+r 1，把其中P 2的倍數(shù)部分分離出來，再看看余下的部分能不能被P 2除余r 2了，關(guān)鍵是P 2除n 1的結(jié)果.

假設(shè)n 1除以P 2的商是n，余數(shù)為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）決定的.所以就要看在這些數(shù)中能不能找到一個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）統(tǒng)一起來了.它就是帶有兩個余數(shù)的韓信點兵問題的求解公式.這樣求解韓信點兵問題的關(guān)鍵就是求r 0了.下面會指出，在P 1與P 2互質(zhì)的條件下，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的數(shù)，就是除以P 1P 2余P 1r 0+r 1的數(shù)，其本質(zhì)是帶有一個余數(shù)的除法問題，該結(jié)論為韓信點兵問題的進一步討論奠定了基礎(chǔ).

3 推廣至多個余數(shù)問題的求解

【例】 ????以本文開頭的士兵問題為例，設(shè)這隊士兵有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.

這就是這隊士兵人數(shù)的通解，通常是指53人.

韓信點兵問題的計算公式（4），可以用不定方程來求解，而且也很簡單.

從（1）和（2）中消去x并移項得

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

它是一個關(guān)于n 1和n 2的不定方程.由于P 1，P 2互質(zhì)，方程（8）有解，且根據(jù)《不定方程的一個通解公式》里的方法，在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）.

這樣不定方程和韓信點兵問題就是同一個問題了，統(tǒng)一在方程組（1）之下.只是所求的未知數(shù)不同而已.這也指出，方程組（1）總是可以求解的.

由此，本文對中國古代的一道“韓信點兵”問題進行了詳細分析，在此基礎(chǔ)上進一步考慮了把多個帶有余數(shù)的除法問題統(tǒng)一起來，給出了具有兩個余數(shù)問題的一個求解公式，統(tǒng)一地解決了這個問題.該公式適用于一切有關(guān)韓信點兵的數(shù)學(xué)問題.

誠懇地希望得到同行老師們的點評和意見.

參考文獻：

［1］ 李春峰.探索化歸思想在高中數(shù)學(xué)解題中的應(yīng)用［J］.數(shù)學(xué)之友，2022，36（6）：53 55.

［2］ 凌翔，崔穎.基于GeoGebra的數(shù)學(xué)概念的教學(xué)探究——以“橢圓定義的多種形式”為例［J］.數(shù)學(xué)之友，2022，36（6）：68 71.

［3］ 張志剛.曲徑通幽處：一道高考模擬題的背景揭示與破解［J］.數(shù)學(xué)之友，2022，36（6）：80 84.