1. 韩信点兵快速解法

物不知数

韩信点兵问题最早出自《孙子算经》。《孙子算经》是中国古代非常重要的数学著作，因数学家 孙子 贡献最大而得名（关于孙子的资料不可考），大约成书于东晋十六国时期，现存最早为北宋刻本，全书分三卷：《卷上》、《卷中》、《卷下》，主要讲述 度量规定 和 算筹运算 以及基于 它们的 数学应为问题，韩信点兵为 《卷下》第二十六题 ”物不知数“，原文如下：

今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问物几何？

答曰：二十三。

术曰：“三、三数之，剩二”，置一百四十；“五、五数之，剩三”，置六十三；“七、七数之，剩二”，置三十。并之，得二百三十三。以二百一十减之，即得。凡三、三数之，剩一，则置七十；五，五数之，剩一，则置二十一；七、七数之，剩一，则置十五。一百六以上，以一百五减之，即得。

题目翻译成现今的数学语言如下：

有一个正整数 x，知 x 除以 3 余 2、除以 5 余数 3、除以 7 余数 2， 求 x 的最小值。

这等价于求解《初等数论》中的 一次同余方程组：

《孙子算经》给出的解法如下：

寻中最小正整数 x₁ ， 满足： x₁ 被 5 和 7 整除 并且 除以 3 余 1，即，5|x₁, 7|x₁ 并且 x₁ mod 3 = 1 ②

x₁ 被 5 和 7 整除，就意味着 被 5×7 = 35 整除，即， 35 | x₁，于是，令 x₁ = 35n（n ≥ 1）：

当 n = 1 时 x₁ = 35，35 mod 3 = 2 不满足 ② 舍弃；

当 n = 2 时 x₁ = 70，70 mod 3 = 1 刚好满足 ②，Bingo~~~。

由于 x₁ ≡ 1 (mod 3)，故 2x₁ ≡ 2 (mod 3)，于是 得到 2x₁ = 140，它满足：除以 3 余 2 并且 被 5 和 7 整除。

同理，

求得满足：可被 3 和 7 整除 并且 除以 5 余 1 的最小正整数 x₂ = 21，从而得到，同样可被 3 和 7 整除 但 除以 5 余 3 的 3x₂ = 63；

求得满足：可被 3 和 5 整除 并且 除以 7 余 1 的最小正整数 x₃ = 15，从而得到，同样可被 3 和 5 整除 但 除以 7 余 2 的 2x₃ = 30；

将上面的 结果 相加 得到： x’ = 2x₁ + 3x₂ + 2x₃ = 140 + 63 + 30 = 233，则 容易验证 x‘ 是 同余方程组 (1) 的一个解 ，但是 x’ 不是 最小整数解 x。很容易可以发现 x' 减去 一个 同时 被 3、5 和 7 整除 并且 不大于 x' 的 整数，结果依然 是 (1) 的解，由于，同时 3、5 和 7 整除，就 意味着 被 3×5×7 = 105 整除，于是得出：

x = x' (mod 105)

进而，有如下算法：

令 x = x'；

如果 x > 105（原文为 106 = x₁ + x₂ + x₃ ） 则 令 x = x - 105，否则 x 为 最终答案；

具体过程如下：

x = x' = 233

[x = 233 > 105]： x = x - 105 = 233 - 105 = 128

[x = 128 > 105]： x = x - 105 = 128 - 105 = 23

[ x = 23 < 105]：OK！

这样就得到了最终答案：x = 23。

将整个求解过程写成算式就是：

x = 2×70 + 3×21 + 2×15 - 2×(3×5×7) = 23

为了方便记忆，发明 珠算 和 卷尺 的明朝数学家 程大位，在其所著的 《算法统宗》 中，将 《孙子算经》的算法编成 "孙子歌诀" 如下：

三人同行七十稀，

五树梅花廿一枝，

七子团圆正半月，

除百零五便得知。

注：正半月就是十五天，除是除去（减去）之意。

韩信点兵

韩信点兵 泛指 ”物不知数“ 此类 一次同余方程组 求解问题。南宋著名数学家 秦九韶 对 《孙子算经》中的算法 进行了深入研究，将其扩展为『大衍总数术』，彻底解决了 韩信点兵问题，这就是 《初等数论》中的 中国剩余定理（也称 孙子定理）：

设 m₁, m₂, ..., m_n 是 两两互素 的 正整数，那么对于任意整数 a₁, a₂, ..., a_n 组成的 一次同余方程组：

在同余意义下，必有唯一解：

其中：

验证：易知，

再结合 (3'')，由 (3') 可以推出：

这就说明 (3') 的确 是 (3) 的解。

注：这里只是给出了定理的验证，并没有严格证明 同余意义下的唯一性。证明 中国剩余定理，有多种方法大家有兴趣可以参考《初等数论》。

秦九韶 分别称 M、Mᵢ 、 Mᵢ⁻¹ 为 衍母、衍数、乘率，这里的关键是求 乘率 Mᵢ⁻¹ ，方法如下：

令， r 是 Mᵢ 除以 mᵢ 的余数，即，

于是：

进而：

然后，让 mᵢ 和 r 辗转相除，得到：

到 r_k = 1 终止。如果 向下进行一步就是：

前面再加上 (4) ，整个过程 就是 欧几里得辗转相除法，因此 r_k 为 Mᵢ 和 mᵢ 的 最大公约数，而 m₁, m₂, ..., m_n 是 两两互素，于是有： r_k = (Mᵢ, mᵢ) = 1 ，这样就证明了 最后 总可以 终止于 1 的正确性。

接着，定义两个数列：

有：

即，

假设，

则：

这样归纳的证明了 (7) 成立。

当 k 为偶数时 有：

于是：

比较 (5) 得到：

当 k 为奇数时，则 k + 1 是偶数，这就要算到 (6) ，对 (6) 稍作变形：

于是，令，

并重新令：

则有：

这样我们就将 辗转相除 又延长了一步 到 k + 1，这时 k + 1 是偶数，则同理上面 情况 可得到：

因为此算法最后总会终止于 1，所以 被 秦九韶 称为『大衍求一术』，前缀 “大衍” 来自于《易经 · 系辞》：“大衍之数五十，... ...”。

当然，中国剩余定理 要求 m₁, m₂, ..., m_n 必须两两 互素，对于那些 不满足这个条件的 一次同余方程组 可以转换为 和 其 同解 的 满足这个条件的 一次同余方程组。下面举例说明：

有一筐鸭蛋，1个1个数，正好数完；2个2个数，还剩1个；3个3个数，正好数完；4个4个数，还剩1个；5个5个数，还剩1个；6个6个数，还剩3个；7个7个数，正好数完；8个8个数，还剩1个；9个9个数，正好数完。请问：框里最少有多少个鸭蛋？

按照题目所述，列同余方程组如下：

显然 1, 2, 3, 4, 5, 6, 7, 8, 9 并不两两互素，因此需要简化：

一个数字必然被 1 整除，因此 ① 没有意义，删除； 一个数字被 9 整除，必然会被 3 整除，因此 保留 ⑨ 删除 ③；一个数字 被 8 除余 1，则可以表示为 8x + 1，进而有 2(4x) + 1，4(2x) + 1，于是 x 一定 可以被 2 和 4 整除，因此 保留 ⑧ 删除 ② 和 ④；目前已经保证了 被 2 除 余 1，可表示为 2x + 1，也保持了 被 3 整除，于是有 3(2x + 1) = 6x + 1，这说明 目前已经保持了 被 6 除 余 3，因此 ⑥ 可以被删除；最后剩下 ⑤ 和 ⑦ 保留。得到：

则 (8') 和 (8) 等价。由于 5,7,9,8 两两互素，符合 中国剩余定理 要求，于是解：

◆M = m₁ m₂ m₃ m₄ = 5 × 7 × 8 × 9 = 2520

◆M₁ = 7 × 8 × 9 = 504

M₁ = q m₁ + r, 504 = 100 × 5 + 4 , c₀ = 1;

m₁ = q₁ r + r₁, 5 = 1 × 4 + 1, c₁ = q₁ = 1; (r₁ = 1，下标 1 是奇数，需要再算一步 )

r = q₂ r₁ + r₂, 4 = 3 × 1 + 1, c₂ = q₂c₁ + c₀ = 3 × 1 + 1 = 4；(得到结果)

M₁⁻¹ = 4， M₁⁻¹ M₁a₁ = 4 × 504 × 1 = 2016；

◆ 由于 a₂ = 0 所以 M₂⁻¹ M₂a₂ = 0；

◆M₃ =5 × 7 × 9 = 315

M₃ = q m₃ + r, 315 = 39 × 8 + 3 , c₀ = 1;

m₃ = q₁ r + r₁, 8 = 2 × 3 + 2, c₁ = q₁ = 2;

r = q₂ r₁ + r₂, 3 = 1 × 2 + 1, c₂ = q₂c₁ + c₀ = 1 × 2 + 1 = 3；(r₂ = 1，下标 2 是偶数，得到结果)

M₂⁻¹ = 3， M₂⁻¹ M₂a₂ = 3 × 315 × 1 = 945；

◆由于 a₄ = 0 所以 M₄⁻¹ M₄a₄ = 0；

得到：

x = M₁⁻¹ M₁a₁ + M₂⁻¹ M₂a₂ + M₄⁻¹ M₄a₄ = 2016 + 0 + 945 + 0 = 2961

x > M, x = x - M = 2961 - 2520 = 441

最终答案：框里最少有 441 个鸭蛋。

最后，需要说明的是：

数学大神欧拉和高斯 对于 一般一次同余式进行了详细研究，独立的得到了 中国剩余定理，后来证实 与 秦九韶『大衍求一术』相同，于是才命名该定理为：中国剩余定理。

中国剩余定理，在《抽象代数》中还有另外的形式，不过这就扯远了，就此打住。

（由于本人数学水平有限，出错在所难免，欢迎各位老师批评指正！）

2. 韩信点兵快速解法大全

相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。

输入3个非负整数a,b,c ，表示每种队形排尾的人数（a<3,b<5,c<7），输出总人数的最小值（或报告无解）。已知总人数不小于10，不超过100 。

3. 韩信点兵问题最适合用的方法

韩信点兵的数学解法

　　我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下报三次数，第一次按1～3报数，第二次按1～5报数，第三次按1～7报数，每次报数后都要求最后一个人报告他报的数是几，这样韩信就知道一共到了多少人。他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。

　　这种问题在《孙子算经》中也有记载：“今有物不知其数：三三数之余二，五五数之余三，七七数之余二，问物几何?” 它的意思就是，有一些物品，如果3个3个的数，最后剩2个；如果5个5个的数，最后剩3个；如果7个7个的数，最后剩2个；求这些物品一共有多少？人们通常把这个问题叫作“孙子问题”， 西方数学家把它称为“中国剩余定理”。现在，这个问题已成为世界数学史上著名的问题。

　　到了明代，数学家程大位把这个问题的算法编成了四句歌诀：

　　三人同行七十稀，五树梅花廿一枝；

　　七子团圆正半月，除百零五便得知。

　　用现在的话来说就是：一个数用3除，除得的余数乘70；用5除，除得的余数乘21；用7除，除得的余数乘15。最后把这些乘积加起来再减去105的倍数，就知道这个数是多少。

　　《孙子算经》中这个问题的算法是：

　　70×2＋21×3＋15×2＝233

　　233－105－105＝23

　　所以这些物品最少有23个。

　　根据上面的算法，韩信点兵时，必须先知道部队的大约人数，否则他也是无法准确算出人数的。你知道这是怎么回事吗？

　　这是因为，

　　被5、7整除，而被3除余1的最小正整数是70；

　　被3、7整除，而被5除余1的最小正整数是21；

　　被3、5整除，而被7除余1的最小正整数是15。

　　所以，这三个数的和是15×2＋21×3＋70×2，必然具有被3除余2，被5除余3，被7除余2的性质。

　　以上解法的道理在于：

　　被3、5整除，而被7除余1的最小正整数是15；

　　被3、7整除，而被5除余1的最小正整数是21；

　　被5、7整除，而被3除余1的最小正整数是70。

　　因此，被3、5整除，而被7除余2的最小正整数是 15×2＝30；

　　被3、7整除，而被5除余3的最小正整数是 21×3＝63；

　　被5、7整除，而被3除余2的最小正整数是 70×2＝140。

　　于是和数15×2＋21×3＋70×2，必具有被3除余2，被5除余3，被7除余2的性质。但所得结果233（30＋63＋140＝233）不一定是满足上述性质的最小正整数，故从它中减去3、5、7的最小公倍数105的若干倍，直至差小于105为止，即 233－105－105＝23。所以23就是被3除余2，被5除余3，被7除余2的最小正整数。

4. 韩信点兵快速解法视频

中国剩余定理

民间传说着一则故事——“韩信点兵”。

秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。

首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然后再加3，得9948（人）。

在一千多年前的《孙子算经》中，有这样一道算术题：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数.

这样的问题，也有人称为“韩信点兵”.它形成了一类问题，也就是初等数论中解同余式.这类问题的有解条件和解的方法被称为“中国剩余定理”，这是由中国人首先提出的.

① 有一个数，除以3余2，除以4余1，问这个数除以12余几？

除以3余2的数有：

2， 5， 8， 11，14， 17， 20， 23….

它们除以12的余数是：

2，5，8，11，2，5，8，11，….

除以4余1的数有：

1， 5， 9， 13， 17， 21， 25， 29，….

它们除以12的余数是：

1， 5， 9， 1， 5， 9，….

一个数除以12的余数是唯一的.上面两行余数中，只有5是共同的，因此这个数除以12的余数是5.

如果我们把①的问题改变一下，不求被12除的余数，而是求这个数.很明显，满足条件的数是很多的，它是 5＋12×整数，

整数可以取0，1，2，…，无穷无尽.事实上，我们首先找出5后，注意到12是3与4的最小公倍数，再加上12的整数倍，就都是满足条件的数.这样就是把“除以3余2，除以4余1”两个条件合并成“除以12余5”一个条件.《孙子算经》提出的问题有三个条件，我们可以先把两个条件合并成一个.然后再与第三个条件合并，就可找到答案.

②一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数.

先列出除以3余2的数：

2， 5， 8， 11， 14， 17， 20， 23， 26，…，

再列出除以5余3的数：

3， 8， 13， 18， 23， 28，….

这两列数中，首先出现的公共数是8.3与5的最小公倍数是15.两个条件合并成一个就是8＋15×整数，列出这一串数是8， 23， 38，…，再列出除以7余2的数 2， 9， 16， 23， 30，…，

就得出符合题目条件的最小数是23.

事实上，我们已把题目中三个条件合并成一个：被105除余23.

那么韩信点的兵在1000-1500之间，应该是105×10+23=1073人

中国有一本数学古书「孙子算经」也有类似的问题：「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」

答曰：「二十三」

术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」

孙子算经的作者及确实著作年代均不可考，不过根据考证，著作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（Chinese Remainder Theorem）在近代抽象代数学中占有一席非常重要的地位。

韩信被贬淮阴侯时高祖找他聊天 高祖说：韩信你说寡人我能带多少兵。 韩信说：10万绝对不能超过10万。高祖又说：你呢。韩信说：韩信点兵 多多益善. 高祖说：那你不是比我还厉害吗，那你为什么会被寡人抓到呢。韩信说：皇上您是将之将 我是兵之将 当然不如陛下您

5. 韩信点兵5种解法

假设人数不超过10000人。首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然后再加3，得9948（人）这个数就满足要求。