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

二、一次同余方程组和孙子定理一、‘‘物不知其数’’问题及其解法一次同余方程组和孙子定理三、孙子定理的应用一、‘‘物不知其数’’问题及其解法大约在公元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的数，再求出余几的数，这种解法逐渐被总结为简洁实用的‘‘求一术’’。‘‘物不知其数’’又名‘‘秦王暗点兵’’。二、一次同余方程组和孙子定理kmm,,1kaa,,1)(mod)(mod)(mod2211kkmaxmaxmax,一次同余方程组其解为)(mod11111maMMaMMxkkk1kmmm11(mod)jjjMMm必定有解，定理１：设是两两互素的正整数,那么对于任意整数，jjmMm，(1)jk，。，这里证明:kmm,,1kkmmmmm11],,[kjmccj1),(mod21两两互素,所以1(mod)jjjjjcMMaam21,cc若一次同余方程组有解方程若有解,则解数为1。)(mod21mcckmm,,1kkkaMMaMMc111111),(jjMm)(mod11jjjmMM1jM)(mod11jjjmMM)(|ijMmijc下证由于。，则。因为两两互素,，这就证明了同余,所以满足确实是同余方程组的解。显然,即的必存在。由及就推出是解。注释：(2)孙子定理要求一次同余方程组的模(1)从孙子定理的算法思想来看,整个计算的难点集中在求1jM上,需要扩展的欧几里德算法实现。当然在实际解题中,我们通常采用拼凑法。两两互素,如果出现了某两个模不互素的情形则应该将其转化为模互素的情形下的等价的一次同余方程组,再用孙子定理求解。12,,,kmmm三、孙子定理的应用孙子定理是数论中最重要的基本定理之一,它实质上刻画了剩余系的结构.它的应用是非常广泛的,在数学计算、保密通讯、测距和日常生活中通常会用到。陈景润《初等数论I》中有下列趣味问题：甲、乙两港的距离不超过5000公里，今有三只轮船于某天零时同时从甲港开往乙港。假定三只轮船每天24小时都是匀速航行，若干天后的零时第一只轮船首先到达，几天后的18时第二只轮船也到达，再过几天后的8时第三只轮船也到达了。假若每天第一只轮船走300公里，第二只轮船走240公里，第三只轮船走180公里，问甲、乙两港实际距离是多少公里，三只轮船各走了多长时间？乙港甲港00:00:0018:00:0008:00:00x1824018024解：设甲、乙两港距离公里。第二只轮船18小时走的距离是公里，第三只轮船8小时走的距离是81806024公里。按照题意有0(mod300)180(mod240)60(mod180)xxx。因为(300,240)60,(300,180)60,(240,180)60,所以该一次同余方程组不能直接用孙子定理解。由于22422300235,240235,180235,所以原一次同余方程组与4224(mod2)6(mod3)0(mod5)xxx有相同的解。1212123331441(mod5),191(mod5),4(mod5),MMM4221232,3,5,mmm1234,6,0,aaa此处22424242212335225,25400,23144,2353600.MMMm由于1414112251(mod2),1(mod2),MM所以取111.M由1212122224001(mod3),41(mod3),2(mod3),MMM所以取122.M由所以取134.M根据孙子定理，我们得22514400(2)61444039003300(mod3600).x412m223m235m4221232353600mmmm22135225M42225400M42323144M111M122M134M111225MM122800MM133576MM14a26a30a1111900MMa12224800MMa13330MMa1111112223333900MMaMMaMMa所求率被衍母除后的最小正剩余为3300答：甲、乙两港相距3300公里。第一只轮船走11天，第二只轮船走13天18小时，第三只轮船走18天8小时。由于甲、乙两港距离不超过5000公里，所以实际距离为3300公里。又3300330033300111,13,18.30024041803