"韩信点兵"问题的一种新解法探索

“韩信点兵”问题的一种新解法探索

陈佳1 唐海军 何聪 曾雪彪

（四川文理学院 数学与财经学院 四川 达州 635000）

摘要：通过研究韩信点兵问题得到关于中国剩余问题的一般解法，加深了对数论中一次同余式的认识，有助于中学生解决数学竞赛问题以及学习算法.

关键词：剩余问题；同余；一般解答

1 引言

已知某个正整数分别被一些小于该数的正整数除所得的余数求原数, 这就是我国从古至今流传很广的“余数问题”[1]或中国剩余问题 。它是一类同余问题。这类问题在古代有不少有趣味的名称，“韩信点兵”也是其中之一 [2].“韩信带一千五百名士兵打仗，战死四、五百人，三人站一排，多出二人；五人站一排，多出四人；七人站一排，多出六人；问题，士兵还剩下多少人”.对以上问题，如果设士兵总人数为X，则有以下式子：

X3l12,X5l24,X7l36其中li(i1,2,3)为整数。

2一般形式

由以上问题，可以得到更一般的一次不定方程组问题.事实上，只需要解决满足以下方程组的m

mp1n1s1mpns222

的一般形式：

mpknksk

(1)

其中pi,si(i1,2k)为已知的整数,且0sipi,

m,ni(i1,2k)为未知正整数.

事实上：若pi0时，mpimisi可以转化为m(pi)(ni)si；

令pi'pi有mpi'(ni)si的形式：pi'0.故下面可以只考虑

pi0时的

情形.

收稿日期：

基金项目：教育部2013年国家级大学生创新训练项目《基于光线强弱控制节能灯的数学模型研究》（项目编号[1**********]5）；2013年四川文理学院教育教学改革研究项目《基于课改理念的数学专业选修课程建设与教学研究》（2013JY45）

作者简介：陈佳（1992—），汉族，男，四川营山人，本科生，研究方向：数学与应用数学

唐海军（1982—），汉族，男，四川南充人，讲师，硕士，研究方向：数学教育与应用数学

mp1n1s1

对于（1）式，若能求得满足以下方程组

mp2n2s2(2)

中m的一般形式解，即mp12n12s12再与（1）式中第三个方程结合，

mp12n12s12得

mpns(3)333

就可得到m在（3）式条件下的一般形式mp123n123s123.依次按上述方法做下去,„„,得:

mp12m1n12m1s12m1



mpns(4)mmm

就可以得到m在（4）条件下的一般形式解：mp12mn12ms12m(5) 事实上，由前面的做法，可知(5) 式就是方程组(1)的m的一般形式解.

3.假设

由前面的做法,问题的关键就是如何求解满足以下方程组:

mpt1s

(6)(其中:p.q.s.l为已知整数,且p,q>0;0≤S

mqt2l

形式解.对于满足(6)式的m是否有解呢？如果有解又应该满足什么条件呢? 下面研究该问题: 假设(6)有解,则mpt1sqt2l，则pt1sqt2l.

(pq)t1slqt1qt2(pq)t1slq(t2t1).从而得到q(pq)t1(sl).

令:(pq)t1(sl)q.r,rZ,则有t1

qr(sl)

Z(7)

pqdqr(sl)

d(pq)

若(p,q)dpdp,qdq.t1由于:dd(pq)，d(sl).

故得出以下定理:

定理3.1 方程组(6）中m有解的充分必要条件为(p,q)sl. 证明: 必要性:已经在前面证明,这里不再累述.下证充分性:

、t若:(p,q)sl，则t12Z，使得pt1qt2sl，pt1sqt2l,

sqtpt12l,即:p(t1)sq(t2)l.

;t2t只要取t1t12,则有mpt1sqt2l.(证毕)

下面求解方程组(6): 令r

(pq)(pq)

K(sl)，KZ，

(p,q)(p,q)

pqpqq(pq)K

q(sl)(sl)q(sl)(sl)

(p,q)(p,q)qK(p,q) 由(7)式得到t1

pq(p,q)pq

pqpq(sl)p(sl)

pqK(p,q)所以ms(p,q)pq

pqKpqpq(sl)p(sl)s(p,q)pqpqpq

pqpqp(K1)(sl)s(p,q)pqpqpl(q1)qs(p1)K,KZ.(p,q)pq故得出以下定理:

定理3.2 若满足方程组(6)的为:m4.应用

x3l12

对于引言中的第一个问题: ，由定理3.2上述方程组的解为:

x5l42

m有解,则解的形式

pqpl(q1)qs(p1)

k,kZ (p,q)pq

x

3534(51)52(31) k15k1615k14,kZ(3,5)35

x15k14再将其与第三个条件联合，于是有，再次应用定理3.2上述方程组的

x7l63

解为:

157156(71)714(151)

xm105m106105m104,mZ

(15,7)157

即:1000105m1041100 又由于1500人已经战死四五百人，1000x1100，

8.5x9.48又mZ,m9，故x10591041049.这与韩信所说出的数完全吻合.

这种解法也可以应用于其它类似的问题，如《孙子算经》中的物不知数问题[3]

. 这类问题和解法, 一般也称它为孙子定理, 外国人称其为“ 中国剩余定理”。剩余是数论中的重要概念，剩余类与剩余系及其性质是一种解决数论问题的重要工具[4]．中国剩余问题不但是中国古代数学中的著名问题，也是现在中学数学竞赛中一个重要内容。对其解法的一般性研究，不但加深对数论中一次同余方程组的认识，也便于中学生利用研究中提出的定理来解决一些竞赛数学上的问题.

参考文献： [1]彭月英.求解“韩信点兵”问题的算法研究[J].广西师范学院学报，1997，14(2):43-48.

[2]张兴华.由“韩信点兵

[3]李文林.数学史概论[M].北京：高等教育出版社，2005：89-90

[4]邹 明.剩余类与剩余系在竞赛中的应用[J].中等数学,2011(10):6-10.

A exploration on the solving”Han Xin Calculate the Sum Total of Soldiers”Question

Chen Jia Tang Hai-jun , He Cong , Zen Xue-biao

(College of Maths and Finance-Economics, Sichuan University of Arts and Science,

Dazhou 635000, China)

A new method to explore the problem about

“Han xin point soldier”

Chen Jia Tang Haijun He Cong Zeng Xuebiao

(Sichuan liberal arts college Institute of mathematics and finance Sichuan

Dazhou 635000)

Summary:Through the research about problem of “Han xin point soldier”we can get the general solution about the China’s surplus problems,and it deepens the cognition about a congruence type in Number Theory.It also helps high school students to slove the problems about math competition and learning algorithm. Antistop: surplus problems;congruence; general solution

“韩信点兵”问题的一种新解法探索

陈佳1 唐海军 何聪 曾雪彪

（四川文理学院 数学与财经学院 四川 达州 635000）

摘要：通过研究韩信点兵问题得到关于中国剩余问题的一般解法，加深了对数论中一次同余式的认识，有助于中学生解决数学竞赛问题以及学习算法.

关键词：剩余问题；同余；一般解答

1 引言

已知某个正整数分别被一些小于该数的正整数除所得的余数求原数, 这就是我国从古至今流传很广的“余数问题”[1]或中国剩余问题 。它是一类同余问题。这类问题在古代有不少有趣味的名称，“韩信点兵”也是其中之一 [2].“韩信带一千五百名士兵打仗，战死四、五百人，三人站一排，多出二人；五人站一排，多出四人；七人站一排，多出六人；问题，士兵还剩下多少人”.对以上问题，如果设士兵总人数为X，则有以下式子：

X3l12,X5l24,X7l36其中li(i1,2,3)为整数。

2一般形式

由以上问题，可以得到更一般的一次不定方程组问题.事实上，只需要解决满足以下方程组的m

mp1n1s1mpns222

的一般形式：

mpknksk

(1)

其中pi,si(i1,2k)为已知的整数,且0sipi,

m,ni(i1,2k)为未知正整数.

事实上：若pi0时，mpimisi可以转化为m(pi)(ni)si；

令pi'pi有mpi'(ni)si的形式：pi'0.故下面可以只考虑

pi0时的

情形.

收稿日期：

基金项目：教育部2013年国家级大学生创新训练项目《基于光线强弱控制节能灯的数学模型研究》（项目编号[1**********]5）；2013年四川文理学院教育教学改革研究项目《基于课改理念的数学专业选修课程建设与教学研究》（2013JY45）

作者简介：陈佳（1992—），汉族，男，四川营山人，本科生，研究方向：数学与应用数学

唐海军（1982—），汉族，男，四川南充人，讲师，硕士，研究方向：数学教育与应用数学

mp1n1s1

对于（1）式，若能求得满足以下方程组

mp2n2s2(2)

中m的一般形式解，即mp12n12s12再与（1）式中第三个方程结合，

mp12n12s12得

mpns(3)333

就可得到m在（3）式条件下的一般形式mp123n123s123.依次按上述方法做下去,„„,得:

mp12m1n12m1s12m1



mpns(4)mmm

就可以得到m在（4）条件下的一般形式解：mp12mn12ms12m(5) 事实上，由前面的做法，可知(5) 式就是方程组(1)的m的一般形式解.

3.假设

由前面的做法,问题的关键就是如何求解满足以下方程组:

mpt1s

(6)(其中:p.q.s.l为已知整数,且p,q>0;0≤S

mqt2l

形式解.对于满足(6)式的m是否有解呢？如果有解又应该满足什么条件呢? 下面研究该问题: 假设(6)有解,则mpt1sqt2l，则pt1sqt2l.

(pq)t1slqt1qt2(pq)t1slq(t2t1).从而得到q(pq)t1(sl).

令:(pq)t1(sl)q.r,rZ,则有t1

qr(sl)

Z(7)

pqdqr(sl)

d(pq)

若(p,q)dpdp,qdq.t1由于:dd(pq)，d(sl).

故得出以下定理:

定理3.1 方程组(6）中m有解的充分必要条件为(p,q)sl. 证明: 必要性:已经在前面证明,这里不再累述.下证充分性:

、t若:(p,q)sl，则t12Z，使得pt1qt2sl，pt1sqt2l,

sqtpt12l,即:p(t1)sq(t2)l.

;t2t只要取t1t12,则有mpt1sqt2l.(证毕)

下面求解方程组(6): 令r

(pq)(pq)

K(sl)，KZ，

(p,q)(p,q)

pqpqq(pq)K

q(sl)(sl)q(sl)(sl)

(p,q)(p,q)qK(p,q) 由(7)式得到t1

pq(p,q)pq

pqpq(sl)p(sl)

pqK(p,q)所以ms(p,q)pq

pqKpqpq(sl)p(sl)s(p,q)pqpqpq

pqpqp(K1)(sl)s(p,q)pqpqpl(q1)qs(p1)K,KZ.(p,q)pq故得出以下定理:

定理3.2 若满足方程组(6)的为:m4.应用

x3l12

对于引言中的第一个问题: ，由定理3.2上述方程组的解为:

x5l42

m有解,则解的形式

pqpl(q1)qs(p1)

k,kZ (p,q)pq

x

3534(51)52(31) k15k1615k14,kZ(3,5)35

x15k14再将其与第三个条件联合，于是有，再次应用定理3.2上述方程组的

x7l63

解为:

157156(71)714(151)

xm105m106105m104,mZ

(15,7)157

即:1000105m1041100 又由于1500人已经战死四五百人，1000x1100，

8.5x9.48又mZ,m9，故x10591041049.这与韩信所说出的数完全吻合.

这种解法也可以应用于其它类似的问题，如《孙子算经》中的物不知数问题[3]

. 这类问题和解法, 一般也称它为孙子定理, 外国人称其为“ 中国剩余定理”。剩余是数论中的重要概念，剩余类与剩余系及其性质是一种解决数论问题的重要工具[4]．中国剩余问题不但是中国古代数学中的著名问题，也是现在中学数学竞赛中一个重要内容。对其解法的一般性研究，不但加深对数论中一次同余方程组的认识，也便于中学生利用研究中提出的定理来解决一些竞赛数学上的问题.

参考文献： [1]彭月英.求解“韩信点兵”问题的算法研究[J].广西师范学院学报，1997，14(2):43-48.

[2]张兴华.由“韩信点兵

[3]李文林.数学史概论[M].北京：高等教育出版社，2005：89-90

[4]邹 明.剩余类与剩余系在竞赛中的应用[J].中等数学,2011(10):6-10.

A exploration on the solving”Han Xin Calculate the Sum Total of Soldiers”Question

Chen Jia Tang Hai-jun , He Cong , Zen Xue-biao

(College of Maths and Finance-Economics, Sichuan University of Arts and Science,

Dazhou 635000, China)

A new method to explore the problem about

“Han xin point soldier”

Chen Jia Tang Haijun He Cong Zeng Xuebiao

(Sichuan liberal arts college Institute of mathematics and finance Sichuan

Dazhou 635000)

Summary:Through the research about problem of “Han xin point soldier”we can get the general solution about the China’s surplus problems,and it deepens the cognition about a congruence type in Number Theory.It also helps high school students to slove the problems about math competition and learning algorithm. Antistop: surplus problems;congruence; general solution