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

1、二、一次同余方程组和孙子定理,一、物不知其数问题及其解法,一次同余方程组 和孙子定理,三、孙子定理的应用,一、物不知其数问题及其解法,大约在公元4世纪，我国南北朝时期有一部著名的算术著作孙子算经，其中就有这样一个物不知其数问题： “今有物， 不知其数， 三三数之剩二， 五五数之剩三， 七七数之剩二， 问物几何？ 答曰：二十三”。,明朝程大位编著的算法统宗里记载了此题的解法，他是用一首歌谣叙述出来的： 三人同行七十稀， 五树梅花廿一枝， 七子团圆正半月， 除百零五便得知。,解答算式是： 702213152233， 233105223.,上面解法的步骤及理由是：,（1） 先在5与7的公倍数中找除以

2、3余1的数，进而找到除以3余2的数。 5，7=35，353=11（余2），（352）3=23（余1），而（702）3=46（余2），140符合条件。,（2）在3与7的公倍数中找除以5余3的数。 3，7=21，215=4（余1），（213）5=12（余3），63就是符合条件的数。,（3） 在3与5的公倍数中找除以7余2的数。 3，5=15，157=2（余1），（152）7=4（余2），30就是符合条件的数。,（4） 将上面得到的分别符合三个条件的三个数相加: 702+213+152=233。,70（或140）是5和7的倍数，而3除余1（或余2）的数。21（或63）是3和7的倍数，而5除余1（或余

3、3）的数。15（或30）是3和5的倍数，而7除余1（或余2）的数。,233是满足除以3余2、除以5余3和除以7余2的数。 又3,5,7=105，233-2105=23也是它的解，而且23105。,23是满足该题的最小解， 它的所有解为 X=105k+23(k=0,1,2, )。,注释： 物不知其数问题及其解答，是我国古代研究一次同余方程组并取得辉煌成果的经典例证。 上面的解法中，总是先求出余1的数，再求出余几的数，这种解法逐渐被总结为简洁实用的求一术。物不知其数又名 秦王暗点兵。,二、一次同余方程组和孙子定理,一次同余方程组,其解为,必定有解，,定理：设,是两两互素的正整数,那,么对于任意整数

4、,，,，,，,。,，这里,证明:,两两互素,所以,若一次同余方程组有解,方程若有解,则解数为1。,下证,由于,。,，则,。因为,两两互素,，这就证明了同余, 所以满足,确实是同余方程组的解。,显然,即,的,必存在。,由,及,就推出,是解。,注释：,(2) 孙子定理要求一次同余方程组的模,(1) 从孙子定理的算法思想来看,整个计算的,难点集中在求,上,需要扩展的欧几里德算法,实现。当然在实际解题中,我们通常采用拼凑法。,两两互素,如果出现了某两个模不互素的情形则 应该将其转化为模互素的情形下的等价的一次 同余方程组,再用孙子定理求解。,三、孙子定理的应用,孙子定理是数论中最重要的基本定理之一,它

5、实质上刻画了剩余系的结构.它的应用是非常广泛的,在数学计算、保密通讯、测距和日常生活中通常会用到。 陈景润初等数论I中有下列趣味问题： 甲、乙两港的距离不超过5000公里， 今有三只轮船于某天零时同时从甲港开往乙港。 假定三只轮船每天24小时都是匀速航行，,若干天后的零时第一只轮船首先到达， 几天后的18时第二只轮船也到达， 再过几天后的8时第三只轮船也到达了。 假若每天第一只轮船走300公里， 第二只轮船走240公里， 第三只轮船走180公里， 问甲、乙两港实际距离是多少公里， 三只轮船各走了多长时间？,乙 港,甲 港,00:00:00,18:00:00,08:00:00,解：设甲、乙两港距离,公里。第二只轮船,18小时走的距离是,公里，第三只轮船,8小时走的距离是,公里。按照题意有,。因为,所以该一次同余方程组不能直接用孙子定理解。,由于,所以原一,次同余方程组与,有相同的解。,此处,由于,所以取,由,所以取,由,所以取,根据孙子定理，我们得,所求率被衍母除后的最小正剩余为3300,答：甲