一次同余方程组和孙子定理.ppt

二 一次同余方程组和孙子定理 一 物不知其数 问题及其解法 一次同余方程组和孙子定理 三 孙子定理的应用 一 物不知其数 问题及其解法 大约在公元4世纪 我国南北朝时期有一部著名的算术著作 孙子算经 其中就有这样一个 物不知其数 问题 今有物 不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 答曰 二十三 明朝程大位编著的 算法统宗 里记载了此题的解法 他是用一首歌谣叙述出来的 三人同行七十稀 五树梅花廿一枝 七子团圆正半月 除百零五便得知 解答算式是 70 2 21 3 15 2 233 233 105 2 23 上面解法的步骤及理由是 1 先在5与7的公倍数中找除以3余1的数 进而找到除以3余2的数 5 7 35 35 3 11 余2 35 2 3 23 余1 而 70 2 3 46 余2 140符合条件 2 在3与7的公倍数中找除以5余3的数 3 7 21 21 5 4 余1 21 3 5 12 余3 63就是符合条件的数 3 在3与5的公倍数中找除以7余2的数 3 5 15 15 7 2 余1 15 2 7 4 余2 30就是符合条件的数 4 将上面得到的分别符合三个条件的三个数相加 70 2 21 3 15 2 233 70 或140 是5和7的倍数 而3除余1 或余2 的数 21 或63 是3和7的倍数 而5除余1 或余3 的数 15 或30 是3和5的倍数 而7除余1 或余2 的数 233是满足除以3余2 除以5余3和除以7余2的数 又 3 5 7 105 233 2 105 23也是它的解 而且23 105 23是满足该题的最小解 它的所有解为X 105k 23 k 0 1 2 注释 物不知其数 问题及其解答 是我国古代研究一次同余方程组并取得辉煌成果的经典例证 上面的解法中 总是先求出余1的数 再求出余几的数 这种解法逐渐被总结为简洁实用的 求一术 物不知其数 又名 秦王暗点兵 二 一次同余方程组和孙子定理 一次同余方程组 其解为 必定有解 定理 设 是两两互素的正整数 那 么对于任意整数 这里 证明 两两互素 所以 若一次同余方程组有解 方程若有解 则解数为1 下证 由于 则 因为 两两互素 这就证明了同余 所以满足 确实是同余方程组的解 显然 即 的 必存在 由 及 就推出 是解 注释 2 孙子定理要求一次同余方程组的模 1 从孙子定理的算法思想来看 整个计算的 难点集中在求 上 需要扩展的欧几里德算法 实现 当然在实际解题中 我们通常采用拼凑法 两两互素 如果出现了某两个模不互素的情形则应该将其转化为模互素的情形下的等价的一次同余方程组 再用孙子定理求解 三 孙子定理的应用 孙子定理是数论中最重要的基本定理之一 它实质上刻画了剩余系的结构 它的应用是非常广泛的 在数学计算 保密通讯 测距和日常生活中通常会用到 陈景润 初等数论I 中有下列趣味问题 甲 乙两港的距离不超过5000公里 今有三只轮船于某天零时同时从甲港开往乙港 假定三只轮船每天24小时都是匀速航行 若干天后的零时第一只轮船首先到达 几天后的18时第二只轮船也到达 再过几天后的8时第三只轮船也到达了 假若每天第一只轮船走300公里 第二只轮船走240公里 第三只轮船走180公里 问甲 乙两港实际距离是多少公里 三只轮船各走了多长时间 乙港 甲港 00 00 00 18 00 00 08 00 00 解 设甲 乙两港距离 公里 第二只轮船 18小时走的距离是 公里 第三只轮船 8小时走的距离是 公里 按照题意有 因为 所以该一次同余方程组不能直接用孙子定理解 由于 所以原一 次同余方程组与 有相同的解 此处 由于 所以取 由 所以取 由 所以取 根据孙子定理 我们得 所求率被衍母除后的最小正剩余为3300 答 甲