摩比爱数学飞跃篇5第5讲初始行程（美妙数学之韩信点兵）
摩比爱数学飞跃篇5第5讲初始行程（美妙数学之韩信点兵）接着再列出除以7余2的数，这些数为：2， 9， 16， 23， 30……就得出同时符合以上两个条件的数：23， 58……满足以上条件的最小自然数是23，而3与5和7的最小公倍数是105。把所有标准融合在一起，就得出一个结论：被105除余23，韩信的兵也就是105×10＋23=1073人。经观察，这两组数列中首先出现的公共数是8，而3与5的最小公倍数是15，两个条件合并成一个，就是8＋15×整数，按照这一标准得出一串数为8， 23， 38……三人同行七十稀，五树梅花开一枝，七子团圆正月半， 除百零五便得知。"刘邦出的这道题，可用现代语言这样表述："一个正整数，被3除时余2，被5除时余3，被7除时余2，如果这数不超过100，求这个数。" 韩信是如何知道自己的队伍有1073个士兵的呢？牛气的韩信熟知余数问题，所以快速统计出自己队伍的人数然后迅速制定作战策略，小伙伴们，你的数论知识现在能不能快速帮
韩信是我国古代杰出的军事家，是西汉的开国功臣，他的一生充满了传奇色彩，从一个众人嫌弃的小混混到称霸一方的大将军，他完成了一次完美的蜕变。同时，他也留下了很多脍炙人口的故事，如"背水一战"、"暗度陈仓"、"十面埋伏"等等。在这其中，"韩信点兵"这个故事包含一个著名的数学问题。
汉高祖刘邦曾问大将韩信："你看我能带多少兵？"韩信斜了刘邦一眼说："你顶多能带十万兵吧！"汉高祖心中有三分不悦，心想：你竟敢小看我！"那你呢？"韩信傲气十足地说："我呀，当然是多多益善啰！"刘邦心中又添了三分不高兴，勉强说："将军如此大才，我很佩服。现在，我有一个小小的问题向将军请教，凭将军的大才，答起来一定不费吹灰之力的。"韩信满不在乎地说："可以可以。"刘邦狡黠地一笑，传令叫来一小队士兵隔墙站队，刘邦发令："每三人站成一排。"队站好后，小队长进来报告："最后一排只有二人。""刘邦又传令："每五人站成一排。"小队长报告："最后一排只有三人。"刘邦再传令："每七人站成一排。"小队长报告："最后一排只有二人。"刘邦转脸问韩信："敢问将军，这队士兵有多少人？"韩信脱口而出："二十三人。
"刘邦大惊，心中的不快已增至十分，心想："此人本事太大，我得想法找个岔子把他杀掉，免生后患。"一面则佯装笑脸夸了几句，并问："你是怎样算的？"韩信说："臣幼得黄石公传授《孙子算经》，这孙子乃鬼谷子的弟子，算经中载有此题之算法，
我们知道宋朝数学家秦九韶在《数书九章》中对这个问题做出了完整系统的解答。明朝数学家程大位在《算法统宗》中将解法编成易于上口的《孙子歌诀》，口诀是：
三人同行七十稀，五树梅花开一枝，七子团圆正月半， 除百零五便得知。"
刘邦出的这道题，可用现代语言这样表述："一个正整数，被3除时余2，被5除时余3，被7除时余2，如果这数不超过100，求这个数。" 韩信是如何知道自己的队伍有1073个士兵的呢？
牛气的韩信熟知余数问题，所以快速统计出自己队伍的人数然后迅速制定作战策略，小伙伴们，你的数论知识现在能不能快速帮你解决些实际问题呢？我们不妨把这个问题数字化，即寻找一个符合条件的最小数，这个数除以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， 58……满足以上条件的最小自然数是23，而3与5和7的最小公倍数是105。把所有标准融合在一起，就得出一个结论：被105除余23，韩信的兵也就是105×10＋23=1073人。
而另一版本的韩信点兵是这样说得：据说秦朝末年的时候，战火四起，楚汉相争。在一次战斗中，韩信率领着1500名将士同楚军将领李锋的军队交战。
战役非常惨烈，双方全都拼死作战，得知死了四五百人，在韩信的带领下，汉军大败楚军，楚军仓惶地逃回了营地，韩信也整理了兵马返回营地。然而当韩信率领剩下的士兵返回营地时，后军来报说楚军追来。这下汉军可炸开了锅，本来就已经身心疲惫的士兵都慌乱不已。
韩信骑马来到坡顶，见追兵不足500人，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着韩信又命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。于是韩信马上说道："我军有1073名兄弟，追兵不过区区500人，我们一定能打败敌人。"听了韩信的话，兵士们士气大振，一鼓作气打败了追来的敌军。
韩信如何快速得知自己士兵的人数呢？这个问题转化成数学问题就是一个数除以3余2，除以5余3，除以7余2，求符合条件的数。下面提供2中解题思路：
1）筛法
1，3，5，7，9，11，13，15，17，19，21，23，25，… （ 用2除余1）
5， 11， 17， 23， … （ 用3除余2）
11， 23，… （ 用4除余3）
再从中挑"用5除余4"的数，… 一直筛选下去，舍得下功夫，就一定可得结果。并且看起来，解，还不是唯一的；可能有无穷多个解。
化繁为简的思想：当问题中有很多类似的条件时，我们先只看其中两三个条件，这就是化繁为简。一个复杂的问题，如果在简化时仍然保留了原来问题的特点和本质，那么简化就"不失一般性"。学会"简化问题"与学会"推广问题"一样，是一种重要的数学能力。
寻找规律的思想：把我们的解题方法总结为筛法是重要的进步，是质的飞跃，找到规律了。
筛法是一般性方法，还可以用来解决其他类似的问题。
2）公倍数法
①化繁为简 ，我们还是先看只有前两个条件的简化题目。
1，3，5，7，9，11，13，15，17，19，21，23，25，… （ 用2除余1）
5，11，17，23，… （ 用3除余2）
上述筛选过程的第一步，得到:1，3，5，7，9，11，13，15，17，19，21，23，25，…其实是列出了"用2除余1"的数组成的数列。这个数列实际上是用带余除法的式子得到的。
所谓"带余除法"，是指整数的如下：对任意 b≠0 被除数a，除数b 必唯一存在商 q和余 数 r ，使a=bq r 0≤r＜b. 回到求"用2除余1的数"的问题。设这样的数为 x ，则 x= 2n 1 。这里x 是被除数，2是除数，n是商，1是余，且 0≤1＜2 。当取 n=0 1 2 3 4 …… 时，用上式求得的x 正好组成上述数列1，3，5，7，9，11，13，15，17，19，21，23，25，…
接着从中筛选出"用3除余2"的数，就是挑出符合下面"带余除法"表达式x=3n 2
的数，这里n可取0，1，2，3，4，… 再继续做下去. 对整个问题寻找规律，： 今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？
②寻找规律，设问题中，需要求的数是x，则x被2，3，4，5，6，7，8，9去除，所得的余数都是比除数少1，于是我们把被除数x再加1，则x 1就可被2，3，4，5，6，7，8，9均整除。也就是说，x 1是2 3 4 5 6 7 8 9的公倍数，从而是其最小公倍数[2 3 4 5 6 7 8 9]的倍数。X 1=2520k k=1 2 3….
怎么解决韩信点兵问题呢？设士兵为x人，则x=3a 2 x=5b 3 x=7c 2 a、b、c为正整数，观察可得x-2=21n n为正整数，当n=1 2 3 … x=23 44 65 … 23被5除余3，所以满足条件的最小人数为23人，x=[3 5 7]k 23=105k 23 因为已经伤亡四五百人，所以1000＜105k 23＜1100 k=10 x=1073.
牛气的韩信熟知余数问题，所以快速统计出自己队伍的人数然后迅速制定作战策略，小伙伴们，你的数论知识现在能不能快速帮你解决些实际问题呢？
1. 一个数在200与400之间，它被3除余2，被7除余3，被8除余5，求该数。
（解：112×2＋120×3＋105×5＋168k，取k＝-5得该数为269。）
2. 一个数除以5余4，除以7余1，除以3余2，这个数不超过100，求这个数？
（解：（3*7）*4 （3*5） （5*7）= 134。这个数小于100，134— 105= 29。）
古代的算法在我国有许多名称，如"韩信点兵"，"鬼谷算"，"隔墙算"，"剪管术"，"神奇妙算"等等，题目与解法都载于我国古代重要的数学著作《孙子算经》中。著作中首次提到了同余方程组问题，以及以上具体问题的解法，一般认为这是三国或晋时的著作，比刘邦生活的年代要晚近五百年，算法口诀诗则载于明朝程大位的《算法统宗》，诗中数字隐含的口诀前面已经解释了。
《孙子算经》中是这样给出这类问题的解法："三三数之剩二，则置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五，一百六以上，以一百五减之，即得。
1247年南宋的数学家秦九韶把《孙子算经》中"物不知其数"一题的方法推广到一般的情况，得到称之为"大衍求一术"的方法，在《数书九章》中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的，被称为"孙子定理"或"中国剩余定理"。
对于我国古代数学名著《孙子算经》中有"物不知数":今有物不知其数，三三数之剩2，五五数之剩3，七七数之剩2，问物几何？如何解析？
首先使用单因子构件凑成法，我们作两个方面的简化：一方面是每次只考虑"一个除式"有余数的情况（即另两个除式都是整除的情况）；另一方面是把余数都简化为最简单的1。这样得到三组方程：
1 x=3a 1 x=5b x=7c
2 y=3a y=5b 1 y=7c
3 z=3a z=5b z=7c 1 (a、b、c为正整数)，
①式意味着，在5和7的公倍数中（35，70，105，…）寻找被3除余1的数；②式意味着，在3和7的公倍数中（21，42，63，…）寻找被5除余1的数；③式意味着，在3和5的公倍数中（15，30，45，…）寻找被7除余1的数。 对①式而言，这个数可以取70，对②式而言，这个数可以取21，对③式而言，这个数可以取15。于是①式两边同减70变为这样：第二式右边仍是5的倍数，第三式右边仍是7的倍数，而第一式右边因为减的70是"用3除余1"的数，正好原来也多一个1，减没了;第一式右边也成为了倍数，是3的倍数。由①得x-70=3( a-23) x-70=5(b-14) x-70=7(c-10)；x-70= [3 5 7 ]k=105k k为正整数，x=105k1 70;由②式两边同减21变得y-21=3 ( a-7 ) y-21=5 ( b-4 ) y-21=7 ( c-3) y=105k2 21; ③式两边同减15变得z=105k3 15;现在重复一下：所得的x是被3除余1，被5和7除余0的数；y是被5除余1，被3和7除余0的数；z是被7除余1，被3和5除余0的数。那么，凑出s=2x 3y 2z， s不就是我们需要求的数吗？
s=140 63 30 105 (2k1 3k2 2k3 )=233 105k;k=-2 -1 0 1 2 3….
这就是《孙子算经》中"物不知其数"一题的解，有无穷多解，最小的正整数解是23（k=-2 时）。
所以，上述方法叫"单因子构件凑成法"解决"由几个平行条件表述的问题"的方法最大优点是可以任意改变余数加以推广：题：有物不知其数，三三数之剩a，五五数之剩b，七七数之剩c，问物几何？ 答：解为s=70a 21b 15c 105k k为整数应该使s为正。
要注意的是，前面的问题中，3，5，7是两两互素的，所以"三三数，五五数，七七数"得余数后可用此公式。但"四四数，六六数，九九数"得余数后就不能用此公式，因为4、6、9并不是两两互素的。
有趣的应用:某单位有100把锁，分别编号为1，2，3，…，100。现在要对钥匙编号，使外单位的人看不懂，而本单位的人一看见锁的号码就知道该用哪一把钥匙。
能采用的方法很多，其中一种就是利用中国剩余定理，把锁的号码被3，5，7去除所得的三个余数来作钥匙的号码（首位余数是0时，也不能省略）。这样每把钥匙都有一个三位数编号。例如23号锁的钥匙编号是232号，52号锁的钥匙编号是123号。8号锁——231 19号锁——145，45号锁——003 ，52号锁——123 因为只有100把锁，不超过105，所以锁的号与钥匙的号是一一对应的。如果希望保密性再强一点儿，则可以把刚才所说的钥匙编号加上一个固定的常数作为新的钥匙编号系统。甚至可以每过一个月更换一次这个常数。这样，仍不破坏锁的号与钥匙的号之间的一一对应，而外人则更难知道了。
余数问题是一个重要的数学问题，是计算机密码学的基石之一。世界著名的数学家欧拉、高斯等人，都曾经研究过这个问题。欧拉重新发现了这个定理（欧拉定理），给出了证明并定义了欧拉函数。对正整数n，欧拉函数φ (n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。例如φ(8)=4，因为1 3 5 7均和8互质。
在数论中，欧拉函数是最重要也是最基础的一个函数，这个函数的很多性质及其证明虽然基础，但也"烧脑"，家里没有要搞奥数的牛娃，就不要折磨脑细胞，咱们背背诗轻松解决好了。
除了用于点兵，欧拉定理更是非对称加密（RSA）算法的核心。欧拉关于数论的大部分工作也是在柏林完成的，他的数论著作在他的《全集》中占了整整四大卷，占全部著作的40%，仅这四卷数论著作就足以使欧拉位列历史上最伟大的数学家之一。
普鲁士的腓特列大帝曾想组成这样一支仪仗队，仪仗队共有36名军官，来自6支部队，每支部队中，上校、中校、少校、上尉、中尉、少尉各一名。他希望这36名军官排成6×6的方阵，方阵的每一行，每一列的6名军官来自不同的部队并且军衔各不相同。
令他恼火的是，这些军官怎么绞尽脑汁也排不成。都说三个臭皮匠，赛过诸葛亮，但是在数学问题上，几千几万个臭皮匠都不顶用。没法，腓特列大帝只能向数学大牛牛欧拉求救。
欧拉先从最简单问题入手，当n=3 (即有3种部队、3种级别)的方阵，他很轻松排出来，然后是n=4，n=5. 都很轻松就解出，得出的方阵叫欧拉方阵（又叫做正交拉丁方阵）。但是当n=6 时，欧拉发现这是一个不可能完成的任务。
1782年，欧拉总结道:"我已经试验研究了很多次，我确信不可能作出两个六阶的，并且对于10、14，…以及奇数2倍的阶数都是不可能的。"欧拉认为:4n 2阶欧拉方阵不存在，这被后人称为"欧拉方阵猜想"。
在没有计算机的年代，欧拉方阵猜想的证明非常困难。一直到了1910年，一对兄弟俩，法国数学家加斯顿•塔里和赫伯特•塔里用了最笨的方法，（不知道他们哪里来的耐心），穷举出了全部六阶拉丁方，从而证实了n=6时欧拉猜想是正确的：n=6 时，仪仗队是一个不可能完成的任务。看到没？ 最笨的方法也可以在数学史上留名啊，真是世上无难事，只怕有心人。（现在用计算机已经知道，除了n=2 6以外，其余的正交拉丁方阵都存在，而且有多种构造的方法。这个否定的结果是人们在180年的努力中未曾想到的。）
欧拉恒等式，欧拉常数，欧拉示性数等
欧拉方阵体现着数学的美：整齐、对称、有规律、简单、自然…，欧拉方阵在工农业生产，统计、组合设计、模拟、数值积分中均具有广泛的应用；另一方面，欧拉方阵在数学的发展中也有着重要的作用.但是，最要紧好玩。欧拉没料到，后人居然把欧拉方阵能玩出花来，成为一种从9-99岁的人都无法抗拒的经典数字游戏。欧拉方阵从瑞士起源，接着在日本推广，后来在英国发扬光大，最终风靡全世界，有了另一个简单好听的名字，数独。其实欧拉方阵就是没有宫的标准数独，而数独其实正是一种特殊的欧拉方阵。
2012 年，三位爱尔兰数学家证明了数独至少需要 17 个初始数字才有唯一解。他们的计算机花了 700 万小时的 CPU 时间才搞定了这道数独题。
可以说中国古代的先贤在这方面取得了丰硕的成果。"韩信点兵"问题只是一个例子，这样的问题有更加普遍和系统化的表示方法。而这个方法是我国为数不多的获得世界公认的古代数学成就之一。
