资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
初中数学兴趣班系列讲座数论部分 唐一良数学工作室第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个人参加,中场休息后,他们依不同的次序重新围着圆桌坐下,证明:至少有两个人,他们
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号