2024年2月14日发(作者：)

第２９卷第６期　２０１３年１２月　大　学　数　学　ＣＯＬＬＥＧＥ　ＭＡＴＨＥＭＡＴＩＣＳ　Ｖｏｌ＿２９，№．６　Ｄｅｃ．２Ｏ１３　“韩信点兵＂问题新解　戴中林　（西华师范大学数学与信息学院，四川南充６３７００２）　［摘要］对“韩信点兵”问题的解法进行新解，给出了较孙子定理简便的求同余式组最小正整数解的一　种递推公式解法．　［关键词］孙子定理；同余式组；最小正整数解；递推公式解法　［中图分类号］０１５６．１　［文献标识码］Ｃ　［文章编号］１６７２—１４５４（２０１３）０６一Ｏ１１２—０４　１　引　言　问题１韩信点兵．有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵　队，则末行四人；成十一行纵队，则末行十人；求兵数．　问题２黄宗宪《求一术通解》．今有数不知总，以五累减之无剩，以七百十五累减之剩十，以二百四　十七累减之剩一百四十，以三百九十一累减之剩二百四十五，以一百八十七累减之剩一百零九，问总数　若干？　上述问题的解法，中国古代数学家称之为“大衍求一术”，即求解同余式组的问题，一般利用孙子定　理　来解决．但其解法较为繁琐，且不能直接求出最小正整数解．为此本文给出了一种简便的并能直接　求出同余式组最小正整数解的递推公式解法．　２本文的结果　首先给出引理．　引理　（同余式解的存在性定理）　当且仅当存在一整数ｋ使ｎ—ｂ＋ｋｍ时，ａ三ｂ（ｍｏｄｍ）．　下面给出本文得到的定理．　定理　如果　≥２，且ｍ　，ｍ　，…，ｍ　是ｎ个两两互质的正整数，对于同余式组　ｚ兰ａｌ（ｍｏｄｍ　ｚ兰ａ２（ｍｏｄｍ　（１）　●●●●●●●●●●●●　三ａ　（ｍｏｄｍ　当且仅当ｋ　（ｉ一１，２，…，　一１）是同余式组　ａｌ　ｔｍｋ１：主兰．　－。ａ—ｌ（ｃｍ。　ｏｄ＋ｍ　２）　，志　ｃｍ。ｄ　。　，　（２）　【ｍｌ…ｍ　１ｋ　三口　一（ｎｌ＋ｍｌｋｌ＋　ｍｚｋ２＋…＋ｍ１ｉｒｎ２…ｍ　２志，ｒ２）（ｍｏｄｍ　），　依次求得的最小正整数解时，则解　［收稿日期］２０１２—０５—０３　

第６期　戴中林：“韩信点兵”问题新解　１１３　ｚ＝＝＝ａ１＋　１忌ｌ＋　１ｍ２忌２＋…＋　１ｍｚ…　，ｒ１愚，ｒ１　是同余式组（１）的最小正整数解．　证必要性．证明存在矗　（ｉ一１，２，…，　一１）使得ｚ为同余式组（１）的正整数解．应用数学归纳　法证明．　当ｉ：１时，由同余式组（１）的前两式，设有数点　，使得　口１＋ｍｌ壳１三ａ２（ｍｏｄｍ２），　即得（２）中第一式　１忌ｌ三ａ２一日１（ｍｏｄｍ２）．　因（ｍ　，ｍ。）一１，由引理，可求得正整数忌　（０≤忌　＜ｍｚ），故得解　＝　ｌ＝ａ１＋　１是１，　即ｉ一１时结论成立；　设ｉ＝　一２时结论成立，即有同余式　ｍ１　２…ｍ，ｒｌ志，ｒ２三口　ｌ一（口１＋ｍ１忌ｌ＋优１ｍ２忌２＋…＋ｍｌ　２…ｍ　３志　３）（ｍｏｄｅ　～１）　成立，并可求得正整数惫，ｒ。（Ｏ≤是　＜　），得解为　ｚ＝．；Ｅｒｒ－２　ａｌ＋　１忌１＋ｍｌｍ２愚１＋…＋ｍ１ｍ２…　２忌　２；　当ｉ＝　一１时，由最后一式，有数是　满足　ｚ，ｒ２＋ｍ１ｍ２…　１愚　ｌ三ａ　（ｍｏｄｍ．），　即得同余式组（２）中最后一式　１　２…ｍ　ｌ忌，ｒ１三ａ　一ｚ　２（ｍｏｄｍ”）　三ａ　一（口１＋ｍ１愚１＋ｍ１优２愚２＋…＋　１ｍｚ…　２忌，广２）（ｍｏｄｍ　）．　由引理，可求得正整数忌，ｒ　（Ｏ≤足，ｒ　＜ｍ　）．故得解　ｚ＝Ｘｒｒ－１：＝＝口１＋ｍ１愚ｌ十仇１ｍ２愚２十…＋ｍｌｍ２…ｍ　１忌，ｒ１，　即当ｉ—　一１时结论成立．故结论对一切ｉ都成立．　又由于０≤忌　＜ｍ　１（ｉ一１，２，…，　～１），故　为（２）的最小正整数解，即当同余式组（２）求得最　小正整数解忌　（　＝１，２，…，　一１）时，同余式组（１）存在正整数解　ｚ—ａｌ＋　１尼１＋　１　２　２＋…＋　ｌ　２…　１尼　１．　充分性．证明这个解　满足同余式组（１）．解ｚ满足同余式组（１）的第一式显然．注意到同余式组　（２）的第一式成立，由于　ｘ（ｍｏｄｍ２）三（口ｌ＋　１尼１＋　１　２　２＋…＋ｍ１ｍ２…ｍ　１愚　１）（ｍｏｄｍ２）　三［（ａｌ＋　ｌ忌１）＋ｍ１ｍ２　２＋…＋ｍｌ　２…仇，ｒ１愚，ｒ１］（ｍｏｄｍ２）　三（ｎ２＋　１　２忌２＋…＋ｍ１ｍ２…　，ｒ１忌　１）（ｍｏｄｍ２）三ａ２（ｍｏｄｍ２），　即解ｚ满足同余式组（１）的第二式．．．…・；最后注意到同余式组（２）的最后一式成立，有　ｘ（ｍｏｄｍ　）三（ｎ１＋　ｌ忌１＋ｍ１ｍ２　２＋…＋ｍ１ｍ２…仇，ｒｌ愚，ｒ１）（ｍｏｄｍ　）　三ｒ－（ａ１＋ｍｌ忌１＋…＋ｍ１…　，ｒ２愚　２）＋…＋ｍｌ　２…　，卜１愚　１］（ｍｏｄｍ　）　三（口ｌ＋　１志１＋…＋ｍｌ…　，ｒ２忌　２）＋［ｎ　一（口ｌ＋ｍ１忌１＋…＋　１…ｍ，广２志，ｒ２）］（ｍｏｄｍ　）　三日　（ｍｏｄｍ　），　即解　满足同余式组（１）的最后一式．故解　满足同余式组（１）．　其次证明这个解ｚ是同余式组（１）的最小正整数解．　事实上，由０≤ｎ１＜ｍ１，０≤忌　１＜ｍｉ，（　一２，…，　），故有　ｍｌｍ２…ｍ　一　＝ｍ１ｍ２…ｍｎ一（口１＋ｍ１志１＋　ｌｍ２忌２＋…＋ｍ１　２…　１　１）　≥ｍｌｍ２…ｍ　一［（ｍ１—１）＋　１（　２—１）＋　１ｍ２（　３—１）＋…＋　ｌ　２…ｍ，广１（　一１）］　一１＞Ｏ，　即　＜ｍ１ｍ２…ｍ　，故解　—ａｌ＋　１忌ｌ＋　１　２忌２＋…＋ｍ１ｍ２…　１愚，ｒ１　是同余式组（１）的最小正整数解．　

１１４　大　学　数　学　同　第２９卷　解　的　３“韩信点兵”问题新解　问题１的解设兵数为５Ｃ人，依题意得同余式组　ｆ　ｌ　｛ＺＺ同　余　式　组　三　１（ｒｏｏｄ５　三　５（ｒｏｏｄ６　三　４（ｒｏｏｄ７　三　１Ｏ（ｒｏｏｄ　由本文定理即解同余式组　ｆ５　１三４（ｍ。ｄ６），　ｒＪＩｌｌｌｌｌｌｌｌｌｌｌｌｌｌｌ，　、　｝●●Ｉｌ】１】ｌｌｌｌｌｌｌ【　５・６是２三４一（１＋５ｋ１）（ｒｏｏｄ７），　ｌ５・６・７ｋ３三１０～（１＋５志ｌ＋５・６志２）（ｒｏｏｄ１１），　三　三　兰　兰　三　解得是１—２，是　一０，志。一１０，故　ｚ—ａｌ＋　ｌ是１＋ｍ１　２走２＋ｍ１　ｍ２Ⅲ３是３—１＋５・２＋５・６・Ｏ＋５・６・７・１０—２１１１　即兵数为２ｌ１１人．　问题２的解设总数为　，并注意到　２４７—１３・１９，　３９１—１７・２３，　１８７：１１．１７．　７１５—５・１１・１３，　可解与原同余式组　（ｒｏｏｄ５），　０（ｒｏｏｄ７１５）　４０（ｒｏｏｄ２４７　４５（ｒｏｏｄ３９１　０９（ｒｏｏｄ１８７　（３）　三０　ｒｏｏｄ５），　ｚ；１０　（ｒｏｏｄ１１　ｚ三１０　（ｒｏｏｄ１３　三，　ｏｏｄ１７）　ｒｍｏｄｌ９）　（４）　Ｚ三／　ｊ　１５　（ｒｏｏｄ２３　下面用两种方法求解（４）．　解法１　由本文定理可得同余式组　ｆ５ｋ１三１０（ｒｏｏｄ１１），　ｆｌ　５・１ｌｋ２；ｌ０—５ｋｌ（ｒｏｏｄ１３），　５・１１・１３ｋ３三７一（５ｋ１＋５・１ｌｋ２）（ｒｏｏｄ１７），　　ｌ５・１１・ｌ３・１７ｋ４　７一（５ｋ１＋５・１１是２＋５・¨・１３ｋ３）（ｒｏｏｄ１９），　ｌ５・１１・１３・１７・１９ｋ　５三１５一（５ｋ１＋５・１ｌ　２＋５・ｌ１・１３ｋ３＋５・１１・１３・１７ｋ４）（ｍｏｄ２３），　依次解得是ｌ一２，　２—０。是。一１４，忌　一０，尼５—０，故　ｚ＝＝＝ｍ１尼１＋ｍｌｍ２　３尼３＝５・２＋５・１１・１３・１４＝１００２０．　解法２　因ａ　一０，故走　不必计算．由孙子定理可得同余式组　ｆ５・１３・１７・１９・２３ｋ　三１（ｍｏｄｌ１），　Ｉ　５・１１・ｌ７・１９・２３ｋ　３三１（ｒｏｏｄ１３），　５・１ｌ・１３・１９・２３ｋ　三三三１（ｒｏｏｄ１７），　　ｌ５・１１・１３・１７・２３ｋ　三ｌ（ｍｏｄｌ９），　【５・１１・１３・１７・１９ｋ　三１（ｍｏｄ２３），　

第６期　戴中林：“韩信点兵”问题新解　１１５　可解得ｋ２—８，ｋ　３—８，　一１０，ｋ　５—１８，忌６—１２，　一（ａ１ｍ２ｍ３…ｍ　ｋ１＋ａ２ｍ１ｍ３…　ｋ　２＋…＋ａ　ｍ１ｍ２…ｍ　一１ｋ　）一ｍｌｍ２…ｍ　ｋ　＝＝＝（１０・５・１３・１７・１９・２３・８＋１０・５・１１・１７・１９・２３・８　＋７．５．１１・１３・１９・２３・１０＋７・５・¨・１３・１７・２３・１８　＋１５・５・１１・１３・１７・１９・１２）一５・１１・１３・１７・１９・２３ｋ　一１６９９８５５４０—５３１１７３５・３２—１００２０，　（是的取值应使ｚ大于零，这里应取ｋ一３２）．　总数为１００２０．　４两种解法之比较　本文定理解法　孙子定理解法　ｋ的个数　一１个　个　计算ｋ的　计算较为简单　计算较为麻烦，尤为ｍ　过多时更甚．　难易程度　优ｌｋｌ　２一“１（ｍｏｄ　ｍ２），　２ｍ３…ｍ　ｋｌ　１（ｍｏｄ　ｍ１），　ｌ　２ｋ２ｉｎ３一ｚ１（ｍｏｄ　ｍ３），　ｍ１ｍ３…ｍ　ｋ　２；ｌ（ｍｏｄ　ｍ２），　７　ｌｍ２…　一ｌｋ　一１　口　一ｚ　一２（ｍｏｄ　ｍ　），　ｍｌｍ２…ｍ　一１ｋ　；１（ｒｏｏｄ　ｍ　）．　ｎ　１　其中ｚ，一ｎ　＋∑ｍ　…ｍ　ｋ　．　ｉ一１　可直接得到最小正整数解ｚ—ｚ　一　，且解－ｚ的结　解　的结构复杂，最后还应适当选取ｋ使得　构简单易记．　解ｚ大于零，才能将其化为最小正整数解．　解的结构　ｚ—ａ１＋ｍ１　１＋　１ｍ２ｋ２＋…＋ｍｌｍ２…ｍ　一１ｋ　一１　ｚ＝（　１ｍ２ｍ３…ｍ　ｋ１＋ａ　２ｍ１ｍ３…ｍ　ｋ　２＋…　＋ａ　ｍ】…ｍ　一ｌｋ　）一ｍ１…ｍ　ｋ　［参　考　文　献］　Ｆ１］闵嗣鹤，严仕健．初等数论［Ｍ］．北京：人民教育出版社，１９５７．　［２］杜德利Ｕ．基础数论［Ｍ］．上海：科学技术出版社，１９８０．　［３］陈景润．初等数论Ｉ［Ｍ］．北京：科学出版社，１９７８．　Ａ　Ｎｅｗ　Ｓｏｌｕｔｉｏｎ　ｏｆ‘Ｈａｎｘｉｎ　ｏｆ　Ｓｏｌｄｉｅｒｓ’　Ｄａｉ　Ｚｈｏｎｇ—ｌｉｎ　（Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ，Ｃｈｉｎａ　Ｗｅｓｔ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｉｃｈｕａｎ，Ｎａｎｃｈｏｎｇ　６３７００２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｆｏｒ　ｐｒｏｂｌｅｍ［ＨＡＮ　Ｘｉｎ　ｏｆ　Ｓｏｌｄｉｅｒｓ］ｎｅｗ　ｏｆ　ｔｈｅ　ｓｏｌｕｔｉｏｎ，ｇｉｖｅｓ　ａ　ｍｏｒｅ　ｓｉｍｐｌｅ　ｔｈｅｏｒｅｍｓ，ｓｅｅｋｉｎｇ　ｃｏｎｇｒｕｅｎｃｅ　ｇｒｏｕｐ　ｔｈｅ　ｓｍａｌｌｅｓｔ　ｐｏｓｉｔｉｖｅ　ｉｎｔｅｇｅｒ　ｓｏｌｕｔｉｏｎｓ　ａ　ｒｅｃｕｒｓｉｖｅ　ｆｏｒｍｕｌａ　ｓｏｌｕｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：Ｃｈｉｎｓｅ　ｒｅｍａｉｎｄｅｒ　ｔｈｅｏｒｅｍ；ｃｏｎｇｒｕｅｎｃｅ　ｇｒｏｕｐ；ｔｈｅ　ｓｍａｌｌｅｓｔ　ｐｏｓｉｔｉｖｅ　ｉｎｔｅｇｅｒ　ｓｏｌｕｔｉｏｎ：ｒｅｃｕｒｓｉｖｅ　ｆｏｒｍｕｌａ　ｍｅｔｈｏｄ