韩信点兵一一中国剩余定理 我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下 报三次数，第一次按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
韩信点兵――中国剩余定理 我 国 汉 代 有 一 位 大 将 ，名 叫 韩 信 。他 每 次 集 合 部 队 ，都 要 求 部 下 报 三 次 数 ，第 一 次 按 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＋ 1 5×2＝ 233 233－ 105－ 105＝ 23 所 以 这 些 物 品 最 少 有 23 个 。 根 据 上 面 的 算 法 ， 韩 信 点 兵 时 ， 必 须 先 知 道 部 队 的 大 约 人 数 ， 否 则 他 也 是 无 法 准 确 算 出 人 数 的 。 你 知 道 这 是 怎 么 回 事 吗 ？ 这 是 因 为 ， 被 5、 7 整除，而被 3 除 余 1 的 最 小 正 整 数 是 7 0
被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的最小正 整数。 我国古算书中给出的上述四句歌诀，实际上是特殊情况下 给出了一次同余式组解的定理。在1247年，秦九韶著《数书九章》， 首创“大衍求一术”，给出了一次同余式组的一般求解方法。在欧洲 直到18世纪，欧拉、拉格朗日(Lagrange,1736~1813,法国数学 家)等，都曾对一次同余式问题进行过研究；德国数学家高斯，在 1801年出版的《算术探究》中，才明确地写出了一次同余式组的求 解定理。当《孙子算经》中的“物不知数”问题解法于1852年经英 国传教士伟烈亚力(Wylie A1 exander,1815~1887)传到欧洲后， 1874年德国人马提生(Matthiessen,1830~1906)指出孙子的解 法符合高斯的求解定理。从而在西方数学著作中就将一次同余式组 的求解定理称誉为“中国剩余定理
被 3、 7 整除，而被 5 除 余 1 的 最 小 正 整 数 是 2 1； 被 3、 5 整除，而被 7 除 余 1 的 最 小 正 整 数 是 1 5； 所 以 ，这 三 个 数的和 1 5×2＋ 21×3＋ 70×2，必 然 具 有 被 3 除 余 2， 被 5 除 余 3， 被 7 除 余 2 的 性 质 。 以 上 解 法 的 道 理 在 于 ： 被 3、 5 整除，而被 7 除 余 1 的 最 小 正 整 数 是 1 5； 被 3、 7 整除，而被 5 除 余 1 的 最 小 正 整 数 是 2 1； 被 5、 7 整除，而被 3 除 余 1 的 最 小 正 整 数 是 7 0。 因 此 ， 被 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－ 1O5－ 105 ＝ 23。 所 以 23 就是被 3 除 余 2， 被 5 除 余 3， 被 7 除 余 2 的 最 小 正 整数。 我 国 古 算 书 中 给 出 的 上 述 四 句 歌 诀 ，实 际 上 是 特 殊 情 况 下 给 出 了 一 次 同 余 式 组 解 的 定 理 。在 1247 年 ，秦 九 韶 著《 数 书 九 章 》， 首 创“ 大 衍 求 一 术 ”，给 出 了 一 次 同 余 式 组 的 一 般 求 解 方 法 。在 欧 洲 ， 直 到 18 世 纪 ，欧 拉 、拉 格 朗 日（ Lagrange，1736～ 1813，法 国 数 学 家 ） 等 ， 都 曾 对 一 次 同 余 式 问 题 进 行 过 研 究 ； 德 国 数 学 家 高 斯 ， 在 1801 年 出 版 的 《 算 术 探 究 》 中 ， 才 明 确 地 写 出 了 一 次 同 余 式 组 的 求 解 定 理 。当《 孙 子 算 经 》中 的“ 物 不 知 数 ”问 题 解 法 于 1852 年经英 国 传 教 士 伟 烈 亚 力 （ Wylie Alexander， 1815～ 1887） 传 到 欧 洲 后 ， 1874 年 德 国 人 马 提 生 （ Matthiessen， 1830～ 1906） 指 出 孙 子 的 解 法 符 合 高 斯 的 求 解 定 理 。 从 而 在 西 方 数 学 著 作 中 就 将 一 次 同 余 式 组 的 求 解 定 理 称 誉 为 “ 中 国 剩 余 定 理
