《初中数学竞赛讲座——数论部分8(同余系的应用)》由会员分享，可在线阅读，更多相关《初中数学竞赛讲座——数论部分8(同余系的应用)（9页珍藏版）》请在金锄头文库上搜索。
1、初中数学兴趣班系列讲座数论部分 唐一良数学工作室第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称为一个完全
2、剩余系，每个数称为相应类的代表元。例如：当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同余。这条性质用数学符号就可表示
3、为：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
4、，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）
5、，即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中的任何一个整数也满足条件。解：
6、取模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（n
7、2m+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
8、，用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（m
9、od3）、因此符合条件的最小的数是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） 不符合
10、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）
11、 符合因此符合条件的数是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、，可以看出余数前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是方程的解，所以这个同余
13、方程的解为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
14、，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个人参加，中场休息后，他们依不同的次序重新围着圆桌坐下，证明：至少有两个人，他们
