“韩信点兵”问题新解

《“韩信点兵”问题新解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第29卷第6期大学数学Vol_29，№．62013年12月COLLEGEMATHEMATICSDec．2O13“韩信点兵"问题新解戴中林(西华师范大学数学与信息学院，四川南充637002)[摘要]对“韩信点兵”问题的解法进行新解，给出了较孙子定理简便的求同余式组最小正整数解的一种递推公式解法．[关键词]孙子定理；同余式组；最小正整数解；递推公式解法[中图分类号]0156．1[文献标识码]C[文章编号]1672—1454(2013)06一O112—041引言问题1韩信点兵．有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；

2、成七行纵队，则末行四人；成十一行纵队，则末行十人；求兵数．问题2黄宗宪《求一术通解》．今有数不知总，以五累减之无剩，以七百十五累减之剩十，以二百四十七累减之剩一百四十，以三百九十一累减之剩二百四十五，以一百八十七累减之剩一百零九，问总数若干?上述问题的解法，中国古代数学家称之为“大衍求一术”，即求解同余式组的问题，一般利用孙子定理来解决．但其解法较为繁琐，且不能直接求出最小正整数解．为此本文给出了一种简便的并能直接求出同余式组最小正整数解的递推公式解法．2本文的结果首先给出引理．引理(同余式解的存在性定理)当且仅当存在一整数k使n—

3、b+km时，a三b(modm)．下面给出本文得到的定理．定理如果≥2，且m，m，⋯，m是n个两两互质的正整数，对于同余式组z兰al(modmz兰a2(modm(1)●●●●●●●●●●●●三a(modm当且仅当k(i一1，2，⋯，一1)是同余式组talk1m：主兰．-。a—l(cm。od+m2)志,cm。d。，(2)【ml⋯m1k三口一(nl+mlkl+mzk2+⋯+m1irn2⋯m2志，r2)(modm)，依次求得的最小正整数解时，则解[收稿日期]2012—05—03第6期戴中林：“韩信点兵”问题新解113z===a1+1忌l+1

4、m2忌2+⋯+1mz⋯，r1愚，r1是同余式组(1)的最小正整数解．证必要性．证明存在矗(i一1，2，⋯，一1)使得z为同余式组(1)的正整数解．应用数学归纳法证明．当i：1时，由同余式组(1)的前两式，设有数点，使得口1+ml壳1三a2(modm2)，即得(2)中第一式忌l三a2一日1(modm2)．1因(m，m。)一1，由引理，可求得正整数忌(0≤忌

5、e～1)成立，并可求得正整数惫，r。(O≤是<)，得解为z=．；Er-2al+1忌1+mlm2愚1+⋯+m1m2⋯2忌2；当i=一1时，由最后一式，有数是满足z，r2+m1m2⋯1愚l三a(modm．)，即得同余式组(2)中最后一式12⋯ml忌，r1三a一z2(modm”)三a一(口1+m1愚1+m1优2愚2+⋯+1mz⋯2忌，广2)(modm)．由引理，可求得正整数忌，r(O≤足，r

6、

7、)，即解z满足同余式组(1)的第二式．．．⋯·；最后注意到同余式组(2)的最后一式成立，有x(modm)三(n1+l忌1+m1m22+⋯+m1m2⋯仇，rl愚，r1)(modm)三r-(a1+ml忌1+⋯+m1⋯，r2愚2)+⋯+ml2⋯，卜1愚1](modm)三(口l+1志1+⋯+ml⋯，r2忌2)+[n一(口l+m1忌1+⋯+1⋯m，广2志，r2)](modm)三日(modm)，即解满足同余式组(1)的最后一式．故解满足同余式组(1)．其次证明这个解z是同余式组(1)的最小正整数解．事实上，由0≤n1

8、2，⋯，)，故有mlm2⋯m一=m1m2⋯mn一(口1+m1志1+lm2忌2+⋯+m12⋯11)≥mlm2⋯m一[(m1—1)+1(2—1)+1m2(3—1)+⋯+l2⋯m，广1(一1)]一1>O，即