一次同余方程组和孙子定理
二、一次同余方程组和孙子定理 一、物不知其数问题及其解法 一次同余方程组 和孙子定理 三、孙子定理的应用 一、物不知其数问题及其解法 大约在公元4世纪,我国南北朝时期有一部 著名的算术著作孙子算经,其中就有这样一 个物不知其数问题: “今有物, 不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何? 答曰:二十三”。 明朝程大位编著的算法统宗里记载 了此题的解法,他是用一首歌谣叙述出来的: 三人同行七十稀, 五树梅花廿一枝, 七子团圆正半月, 除百零五便得知。 解答算式是: 70×221×315×2233, 233105×223. 上面解法的步骤及理由是: (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。 7070(或(或140140)是)是5 5和和7 7的倍数,而的倍数,而3 3除余除余1 1(或余(或余2 2) 的数。的数。2121(或(或6363)是)是3 3和和7 7的倍数,而的倍数,而5 5除余除余1 1(或余(或余 3 3)的数。)的数。1515(或(或3030)是)是3 3和和5 5的倍数,而的倍数,而7 7除余除余1 1( 或余或余2 2)的数。)的数。 233233是满足除以是满足除以3 3余余2 2、除以、除以5 5余余3 3和除以和除以7 7余余2 2的数的数 。 又又3,5,7=1053,5,7=105,233-2233-2××105=23105=23也是它的解,而也是它的解,而 且且2323105105。 2323是满足该题的最小解,是满足该题的最小解, 它的所有解为它的所有解为 X=105k+23(k=0,1,2, 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 答:甲、乙两港相距3300公里。第一 只轮船走11天,第二只轮船走13天18 小时,第三只轮船走18天8小时。 由于甲、乙两港距离不超过5000公里 ,所以实际距离为3300公里。又