初中数学竞赛讲座——数论部分8(同余系的应用).doc

初中数学兴趣班系列讲座数论部分 唐一良数学工作室第8讲 剩余系及其一次同余方程一、基础知识：（1）剩余系对于任意正整数n而言，一个整数除以m所得的余数只能是0,1,2, ,n-1中的某一个。依次可将整数分成n个类（例如n2时，就是奇数或偶数），从每一类中各取一个数所组成的集合就称为模的一个完全剩余系，简称为模的完系。定义1：如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数n，有n个余数：0,1,2,.,n-1），那么就被称为是模n的一个完全剩余系。定义2：剩余系：设模为m,则根据余数可将所有的整数分成m类，分别记成0,1,2,m-1，这m个数0,1,2,m-1称为一个完全剩余系，每个数称为相应类的代表元。例如：当m=10则,0,1,2,3,4,5,6,7,8,9最小非负完全-5,-4,-3,-2,-1,0,1,2,3,4绝对值最小-4,-3,-2,-1,0,1,2,3,4,5绝对值最小（一）根据剩余类的概念，很容易得到以下几条有关剩余类的性质：每一个整数一定包含在而且仅包含在模m的一个剩余类中整数p所属的模m的剩余类中的每一个数都可以写成km+p的形式，这里k是整数用符号p mod m表示p所属的模m的剩余类，这条性质写成数学表达式就是p mod m= p+km（k是整数）整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。这条性质用数学符号就可表示为：p mod m= q mod mpq（mod m）实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。这条性质表明，对于模m的两个剩余类要么相等，要么它们的交集为空集，因此，模m有且仅有m个剩余类，它们是：0modm，1 mod m，2 mod m，（m1）mod m。在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，m1，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。在任意取定的m+1个整数中，必有两个整数对模m同余。（二）根据同余式的性质，我们很容易得到剩余系的其它一些性质：m个整数x1，x2，xm是模m的一组完全剩余系的充要条件是x1，x2，xm中的任意两个数对模m都不同余。如果x1，x2，xm是模m的一组完全剩余系，那么对任意的整数c，x1+c，x2+c，xm+c也是模m的一组完全剩余系。设k1，k2，km是m个整数，如果x1，x2，xm是模m的一组完全剩余系，那么x1+k1m，x2+k2m，xm+k1m也是模m的一组完全剩余系。（2）一次同余方程设m | a，则axb（mod m）叫做模m的一次同余方程。如果x= x0是方程ax b（mod m）的一个解，那么x= km+x0也是这个方程的一个解。这是因为，如果ax0 b（mod m），那么一定有akm+ax0b（mod m），即a(km+x0) b（mod m），这说明如果x=x0是方程axb（mod m）的一个解，那么剩余类x0mod m中的任何一个数也是这个方程的解，这些解都看作是相同的，把剩余类x0mod m称为同余方程axb（mod m）的一个解，记作xx0（mod m）因此，我们在解同余方程的时候，只需在任意取定的模m的一组完全剩余系中求解模m的同余方程，就可获得这个方程的全部解。二、典型例题：例1求证：一定存在整数n，使4n2+27n12能被5整除，并求出这些数。分析：可以选模5的一个完全剩余系逐个验算，只要数a使4a2+27a12能被15整除，那么剩余类a mod 5中的任何一个整数也满足条件。解：取模5的一个完全剩余系0，1，2，3，4直接计算可知，3和4满足条件，所以使4n2+2712能被5整除的所有的整数是n3（mod 5）和n4（mod 5）。例2 求使2n-1为7的倍数的所有正整数n解 因为2381(mod 7)，所以对n按模3进行分类讨论(1) 若n=3k，则2n-1(23)k-18k-11k-10(mod 7)；(2) 若n=3k1，则2n-1=2(23)k-1=28k-121k-11(mod 7)；(3) 若n=3k2，则2n-1=22(23)k-1=48k-141k-13(mod 7)所以，当且仅当3n时，2n-1为7的倍数例3m、p、n为自然数，求证：3 | np（n2m+2）分析：对n按模3进行分类讨论证明：当n0（mod 3）时，np0（mod 3），np（n2m+2）0（mod 3）当n1（mod 3）时，np1（mod 3），n2m12m1（mod 3），np（n2m+2）1（1+2）30（mod 3）当n2（mod 3）时，np2 p（mod 3），n2m（n2）m4m1m1（mod 3）np（n2m+2）2 p（1+2）2 p00（mod 3）所以，对一切自然数n，都有3 | n p（n2m+2）例4.分别求满足下列条件的最小自然数：（1）用3除余1，用5除余1，用7除余1。（2）用3除余2，用5除余1，用7除余1。（3）用3除余1，用5除余2，用7除余2。（4）用3除余2，用7除余4，用11除余1。思路分析：（1）该数减去1以后，是3，5和7的最小公倍数105，所以该数的是105+1=106（2）该数减去1以后是5和7的公倍数。因此我们可以以5和7的公倍数中去寻找答案。下面列举一些同时被5除余1，被7除余1的数，即1，36，71，106，141，176，211，246，从以上数中寻找最小的被3除余2的数。360（mod3），712（mod3），符合条件的最小的数是71。（3）我们首先列举出被5除余2，被7除余2的数，2，37，72，107，142，177，212，247，从以上数中寻找最小的被3除余1的数。2（mod3），37（mod3）、因此符合条件的最小的数是37。（4）我们从被11除余1的数中寻找答案。1，12，23，34，45，56，67，78，89，100，133，144，155，166，177，188，199，210，232，243，1（mod3）； 1（mod7）， 不符合120（mod3）， 125（mod7） 不符合232（mod3）， 232（mod7） 不符合341（mod3）， 346（mod7） 不符合450（mod3）， 453（mod7） 不符合562（mod3）， 560（mod7） 不符合671（mod3）， 674（mod7） 不符合780（mod3）， 781（mod7） 不符合 892（mod3）， 895（mod7） 不符合1001（mod3）， 1002（mod7） 不符合1222（mod3）， 1223（mod7） 不符合1331（mod3）， 1330（mod7） 不符合 1441（mod3）， 1444（mod7） 不符合1552（mod3），1551（mod7） 不符合1661（mod3），1665（mod7） 不符合1770（mod3），1772（mod7） 不符合1882（mod3），1886（mod7） 不符合1991（mod3），1993（mod7） 不符合2100（mod3），2100（mod7） 不符合2212（mod3），2214（mod7） 符合因此符合条件的数是221。例5.现有70个数排成一行，除了两头的两个数以外，每个数的三倍恰好等于它两边两个数的和，这一行最左边的几个数是这样的：0，1，3，8，21，问这一行数最右边的一个数被6除的余数是几？分析：如果将这70个数一一列出，得到第70个数后，再用它去除以6得余数，总是可以的，但计算量太大。即然这70个数中：中间的一个数的3倍是它两边的数的和，那么它们被6除以后的余数是否有类似的规律呢？0，1，3，8，21，55，144，被6除的余数依次是0，1，3，2，3，1，0，结果余数有类似的规律，继续观察，可以得到：0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，可以看出余数前12个数一段，将重复出现。702=510，第六段的第十个数为4，这便是原来数中第70个数被6除的余数。例6解下列同余方程3x2（mod 6） 4x6（mod 10）解：当x0（mod 6）时，3x0（mod 6）当x1（mod 6）时，3x3（mod 6）当x2（mod 6）时，3x60（mod 6）当x3（mod 6）时，3x93（mod 6）当x4（mod 6）时，3x120（mod 6）当x5（mod 6）时，3x153（mod 6）所以方程3x2（mod 6）无解。与小题类似，取模10的最小完全剩余系0，1，2，3，9直接计算可知，x=4和x=9是方程的解，所以这个同余方程的解为x4（mod 10）或x9（mod 10）说明：解模m的一次同余方程，可以取模m的一个完全剩余系直接计算，这个方法也适用于其它的同余方程。模m的一次同余方程axb（mod m）（m a）有解的充要条件是（a，m）| b。例7. 同余方程2x6（mod 8）的解和方程x3（mod 4）的解是否相同，说明理由。解：设x=x0是方程2x6（mod 8）的一个解，那么2x06（mod 8）2x0=8k+6，x0= 4k+3，x03（mod 4）即方程2x6（mod 8）的解必是方程x3（mod 4）的解反之，若x=x0是方程x3（mod 4）的一个解，那么x03（mod 4）x0= 4m+3，2x0=8m+6，故2x06（mod 8）即方程x3（mod 4）的解必是方程2x6（mod 8）的解所以，方程2x6（mod 8）和x3（mod 4）的解相同说明：若正整数d | （a，b，m），则方程axb（mod m）的解与方程的解相同，利用这条性质可以将较大模数的同余方程化为较小模数的同余方程。例8解同余方程38x19（mod 95）分析：此题中的模95的剩余数太多，如果选定一个完全剩余系进行直接计算，运算量相当大，因此我们可以运用上题的方法，将模化小一点。解：（38，19，95）=19，38x19（mod 95）的解与2x1（mod 5）的解完全相同，只需求解方程2x1（mod 5）即可。2x1（mod 5），2x4（mod 5）x2（mod 5），原方程的解为x2+5u（u=0，1，2，3，18）（mod 95）例9 证明：在十进制表示下，任意39个连续正整数中，必有一个数的各位数字之和是11的倍数。例10.设n位为正奇数，证明：数2-1，22-1，23-1，2n-1-1中必有一个数是n的倍数。例11.一次圆桌会议共有2012个人参加，中场休息后，他们依不同的次序重新围着圆桌坐下，证明：至少有两个人，他们之间的人数在休息前后是相等的。三、模拟训练1 证明方程x4+y4+2=5z没有整数解证 对于任一整数x，以5为模，有x0，1，2(mod 5)，x20，1，4(mod 5)，x40，1，1(mod 5)，即对任一整数x，x40，1(mod 5)同样，对于任一整数yy40，1(mod 5)，所以 x4+y4+22，3，4(mod 5)，从而所给方程无整数解说明 同余是处理不定方程的基本方法，但这种方法也非常灵活，关键在于确定所取的模(本例我们取模5)，这往往应根据问题的特点来确定 2解同余方程987x610（mod 1597）解：987x610（mod 1597），987x1597x610（mod 1597）610x610（mod 1597），x1（mod 1597）3请看一首欢庆国庆的诗：“十里长街闹盈盈，庆祝成就万象新，国庆礼花破长空，新桥红灯胜繁星，七七数时余两个，五个一数恰为零，九数之时剩四盏，红灯几盏放光明。”解：设有x盏红灯，那么由得x=7m+2，m=0，1，2，3，代入得，7m+20（mod 5），7m22+5628（mod 5）m4（mod 5），m5n+4，x=7（5n+4）+2=35n+30代入得，35n+304（mod 9），35n2626+4910（mod 9）7n2（mod 9），7n2+6956（mod 9），n8（mod 9）n=9k+8，k=0，1，2，3，所以x=35（9k+8）+30=315k+310，xmin=310，答：有310盏红灯。【延伸阅读】我国南北朝时期有一部著名的算术著作孙子算经，其中有这样一个“物不知数”问题：“今有物不知其数，三三数之剩2；五五数之剩3；七七数之剩2，问物几何？”用现在化较通俗的数学语言可以这样叙述：“求一个数，使它被3除余2；被5除余3；被7除余2。”解：设所求数为x，则由得x=3k+2，k=0，1，2，3代入得，3k+23（mod 5）3k11+56（mod 5），k2（mod 5），即k= 5n+2，n=0，1，2，x=3（5n+2）+2=15n+8，n=0，1，2，3，代入得：15n+82（mod 7），15n66+2115（mod 7）n1（mod 7），故n=7t+1，t=0，1，2，所以，x=15（7t+1）+8=105t+23，t=0，1，2，3，所求数的最小值是23。孙子算经巧妙地解决了“物不知数”问题，但没有上升到一套完整的计算程序和理论高度，没有解决一般的一次同余方程的求解问题，南宋时期的数学家秦九韶在他的数学九章中提出了“大衍求一术”的数学方法，系统地论述了一次同余方程组解法的基本原理和一般程序。“求一”就是求一个数的多少倍除以另一个数，所得的余数是一，为了深刻地理解这一方法，我们再回头研究“物不知数”问题中的几个关键数字71，21、15。70=2571（mod 3）21=371（mod 5）15=351（mod 7）其中，70是5和7的倍数，但被3除余1，21是3和7的倍数，但被5除1；15是3和5的倍数，但被7除余1，任何一个一次同余方程组，只要类似地求出相应的关键数字，就可以得到这个一次同余方程组的解，秦九韶的“大衍求一术”的方法流传到西方，被称为“中国剩余定理”。所以，我得到一般一次同余方程组的解法是：设p，q，r是两面互质的正整数，同余方程组的解是xAa+Bb+Cc（mod pqr）其中 A1（mod p），A0（mod q），A0（mod r）B1（mod q），B0（mod p），B0（mod r）C1（mod r），C0（mod p），C0（modq）下面我们介绍中国剩余定理：【中国剩余定理】设m1，m2，m k是k个两两互质的正整数，对任意整数a1，a2，a k，则同余方程组。有且只有一个解x M1Ma1+M2Ma2+M kMa k（mod m）其中m=m1m2m k，m = mjMj（1jk）以及M jM1（mod mj）1jk这个定理本身比较复杂，证明也比较繁，关于证明过程，这里不作介绍，有兴趣的同学请自行阅读有关初等数论的著作，只对定理本身作一些阐述，以帮助大家理解，我们用中国剩余定理再解“物不知数”问题。M1=57=35，M2=37=21，M3=35=15，352=701（mod 3）211（mod 5），151（mod 7）M1M=70，M2M=21，M3M=15x702+213+152（mod 105）23323（mod 105）所以x的最小值是23。下面举例说明中国剩余定理的运用。例1解同余方程组解：m1=5，m2=7，m3=11M1=711=77，M2=511=55，M3=57=35M1711212（mod 5），由1M1M2M1（