“韩信点兵”问题新解

戴中林

（西华师范大学数学与信息学院，四川南充 637002）

1 引 言

问题1 韩信点兵.有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人 ；求兵数.

问题2 黄宗宪《求一术通解》.今有数不知总，以五累减之无剩，以七百十五累减之剩十，以二百四十七累减之剩一百四十，以三百九十一累减之剩二百四十五，以一百八十七累减之剩一百零九，问总数若干？

上述问题的解法，中国古代数学家称之为“大衍求一术”，即求解同余式组的问题，一般利用孙子定理［1］来解决.但其解法较为繁琐，且不能直接求出最小正整数解.为此本文给出了一种简便的并能直接求出同余式组最小正整数解的递推公式解法.

2 本文的结果

首先给出引理.

依次求得的最小正整数解时，则解

3 “韩信点兵”问题新解

4 两种解法之比较

本文定理解法 孙子定理解法k的个数 n－1个 n个计算k的难易程度计算较为简单m1k1≡a2－a1（mod m2），m1m2k2≡a3－x1（mod m3），……m1m2…mn－1kn－1≡an－xn－2（mod mn），其中xi＝a1＋ ∑计算较为麻烦，尤为mi过多时更甚.m2m3…mnk1≡1（mod m1），m1m3…mnk2≡1（mod m2），……m1m2…mn－1kn≡1（mod mn）.n－1 m1…miki.i＝1解的结构可直接得到最小正整数解x＝xn－1，且解x的结构简单易记.x＝a1＋m1k1＋m1m2k2＋…＋m1m2…mn－1kn－1解x的结构复杂，最后还应适当选取k使得解x大于零，才能将其化为最小正整数解.x＝（a1m2m3…mnk1＋a2m1m3…mnk2＋…＋anm1…mn－1kn）－m1…mnk

［1］闵嗣鹤，严仕健.初等数论［M］.北京：人民教育出版社，1957.

［2］杜德利U.基础数论［M］.上海：科学技术出版社，1980.

［3］陈景润.初等数论Ⅰ［M］.北京：科学出版社，1978.