韩信点兵(同余问题).pdf

.. 二 韩信点兵 例 1 我们先考虑下列的问题：假设兵不满一万，每 5 人一列、 9 人一列、 13 人一列、 17 人一列都剩 3 人，则 兵有多少？ 首先我们先求 5、9、13、17 之最小公倍数 9945 （注：因为 5 、9 、13、17 为两两互质的整数，故其最小公倍 数为这些数的积） ，然后再加 3 ，得 9948 （人）。 例 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. 如果我们把问题改变一下：有一个数，除以 3 余 2，除以 4 余 1，问这个数是几？ 不求被 12 除的余数，而是 求这个数是几？ . 很明显， 这个数最小是 5，满足条件的数是很多的，它们是 5 ＋12×n (n=0 ， 1，2， 3…) ， 事实上，我们首先找出 5 后，注意到 12 是 3 ，4 的最小公倍数，再加上 12 的整数倍，就都是满足条件的数 . 这样就是把 “除以 3 余 2，除以 4 余 1”两个条件合并成 “除以 12 余 5 ”一个条件 . 题目中提出的条件有三个，我们可以先把两个条件合并成一个 . 然后再与第三个条件合并，就可找到答案 . 例 3 秦朝末年，楚汉相争 . 韩信帅 1500 名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉 军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见 远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信急速点兵迎敌。他命令 士兵 3 人一排，结 果多出 2 名；接着命令士兵 5 人一排，结果多出 3 名；他又命令士兵 7 人一排，结果又多出 2 名。 韩信马上向将 士们宣布：我军有 1073 人，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。 一个数除以 3 余 2 ，除以 5 余 3，除以 7 余 2，求符合条件的最小数 . 解： 第 1 步 先列出满足其中一个条件的数（一般从小到大） ，即除以 3 余 2 的数： 2 ， 5 ， 8 ， 11 ， 14 ， 17 ， 20 ， 23 ， 26 ，…， 第 2 步再列出满足其中第二个条件的数， 即除以 5 余 3 的数： 3， 8 ， 13 ， 18 ， 23 ， 28 ，…. 第 3 步归纳前面第 3 步首先出现的公共数是 8. 8 就是满足除以 3 余 2 ，除以 5 余 3 的最小的那个数。 3 与 5 的最小公倍数 是 15. 两个条件合并成一个就是 8 ＋ 15×n (n=0 ， 1，2，…) 。