1、小学奥数竞赛专题之同余问题窗体顶端小学奥数竞赛专题之同余问题专题介绍:同余问题生活中我会经常遇到与余数有关的问题,比如:某年级有将近400名学生。有一次演出节目排队时出现:如果每8人站成一列则多余1人;如果改为每9人站成一列则仍多余1人;结果发现现成每10人结成一列,结果还是多余1人;聪名的你知道该年级共有学生多少名吗?假设有一名学生不参加演出,则结果一定是不管每列站8人或9人或10人都将刚好站齐。因此此时学生人数应是8、9、10公倍数,而8、9、10的最小公倍数是360,因此可知该年级共有361人。研究与余数有关的问题,能帮助我们解决很多较为复杂的问题。分析1、两个整数a和b,除以一个大于1
2、的自然数m所得余数相同,就称a和b对于模m同余或称a和b在模m下同余,即ab(modm)2、同余的重要性质及举例。1aa(modm)(a为任意自然)2若ab(modm),则ba(modm)3若ab(modm),bc(modm)则ac(modm)4若ab(modm),则acbc(modm)5若ab(modm),cd(modm),则ac=bd(modm)6若ab(modm)则anbm(modm)其中性质3常被称为同余的可传递性,性质4、5常被称为同余的可乘性,性质6常被称为同余的可开方性注意:一般地同余没有可除性,但是:如果:ac=bc(modm)且(c,m)=1则ab(modm)3、整数分类:1
3、用2来将整数分类,分为两类:1,3,5,7,9,(奇数)0,2,4,6,8,(偶数)2用3来将整数分类,分为三类:0,3,6,9,12,(被3除余数是0)1,4,7,10,13,(被3除余数是1)2,5,8,11,14,(被3除余数是2)3在模6的情况下,可将整数分成六类,分别是:0(mod6):0,6,12,18,24,1(mod6):1,7,13,19,25,2(mod6):2,8,14,20,26,3(mod6):3,9,15,21,27,4(mod6):4,10,16,22,29,5(mod6):5,11,17,23,29,经典例题例1:求4373091993被7除的余数。思路分析:如
4、果将4373091993算出以后,再除以7,从而引得到,即4373091993=269120769,此数被7除的余数为1。但是能否寻找更为简变的办法呢?4733(mod7)3091(mod7)由同余的可乘性知:43730931(mod7)3(mod7)又因为19935(mod7)所以:437309199335(mod7)15(mod7)1(mod7)即:4373091993被7除余1。例2:70个数排成一行,除了两头的两个数以外,每个数的三倍恰好等于它两边两个数的和,这一行最左边的几个数是这样的:0,1,3,8,21,问这一行数最右边的一个数被6除的余数是几?思路分析:如果将这70个数一一列出
5、,得到第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除的余数。思路分析:我们被直接用除法算式,结果如何。例4、分别求满足下列条件的最小自然数:(1)用3除余1,用5除余1,用7除余1。(2
6、)用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,2
7、47,从以上数中寻找最小的被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(mo
8、d3),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)符
9、合因此符合条件的数是221。例5判断以下计算是否正确(1)427843968267=1697598942346(2)427843968267=1697598981248思路分析:若直接将右边算出,就可判断417843968267=169778335328,可知以上两结果均是错的;但是计算量太大。如果右式和左式相等,则它们除以某一个数余数一定相同。因为求一个数除以9的余数只需要先求这个数数字之和除以9的余数,便是原数除以9的余数。我考虑上式除以9的余数,如果余数不相同,则上式一定不成立。(1)从个位数字可知,右式的个位数字只能是8,而右式个位为6,因此上式不成立。(2)右式和左式的个位数字相同,
10、因而无法断定上式是否成立,但是4+2+7+8+4=25,257(mod9)3+9+6+8+2+6+7=41,415(mod9)427847(mod9);39682675(mod9)42784396826735(mod9)8(mod9)(1+6+9+7+5+9+8+9+4+2+3+4+8)3(mod9)因此(2)式不成立以上是用除9取余数来验证结果是否正确,常被称为弃九法。不过应该注意,用弃九法可发现错误,但用弃九法没找出错误却不能保证原题一定正确。习题1、求169411611被7除的余数。3、判断结果是否正确:(1)54839117=49888511(2)12264522683=3344、乘法
11、算式314592653=291093995的横线处漏写了一个数字,你能以最快的办法补出吗?5、13511,13903,14589被自然数m除所得余数相同,问m最大值是多少?窗体顶端窗体底端奥数武汉站 奥数题库 小学奥数专题 正文 小学奥数竞赛专题之同余问题来源:网络 文章作者:匿名 2009-02-15 13:33:28标签:小学 奥数 竞赛 专题 问题奥数精华资讯 免费订阅小学奥数竞赛专题之同余问题专题介绍:同余问题生活中我会经常遇到与余数有关的问题,比如:某年级有将近400名学生。有一次演出节目排队时出现:如果每8人站成一列则多余1人;如果改为每9人站成一列则仍多余1人;结果发现现成每10
12、人结成一列,结果还是多余1人;聪名的你知道该年级共有学生多少名吗?假设有一名学生不参加演出,则结果一定是不管每列站8人或9人或10人都将刚好站齐。因此此时学生人数应是8、9、10公倍数,而8、9、10的最小公倍数是360,因此可知该年级共有361人。研究与余数有关的问题,能帮助我们解决很多较为复杂的问题。分析1、两个整数a和b,除以一个大于1的自然数m所得余数相同,就称a和b对于模m同余或称a和b在模m下同余,即ab(modm)2、同余的重要性质及举例。1aa(modm)(a为任意自然)2若ab(modm),则ba(modm)3若ab(modm),bc(modm)则ac(modm)4若ab(m
13、odm),则acbc(modm)5若ab(modm),cd(modm),则ac=bd(modm)6若ab(modm)则anbm(modm)其中性质3常被称为同余的可传递性,性质4、5常被称为同余的可乘性,性质6常被称为同余的可开方性注意:一般地同余没有可除性,但是:如果:ac=bc(modm)且(c,m)=1则ab(modm)3、整数分类:1用2来将整数分类,分为两类:1,3,5,7,9,(奇数)0,2,4,6,8,(偶数)2用3来将整数分类,分为三类:0,3,6,9,12,(被3除余数是0)1,4,7,10,13,(被3除余数是1)2,5,8,11,14,(被3除余数是2)3在模6的情况下,
14、可将整数分成六类,分别是:0(mod6):0,6,12,18,24,1(mod6):1,7,13,19,25,2(mod6):2,8,14,20,26,3(mod6):3,9,15,21,27,4(mod6):4,10,16,22,29,5(mod6):5,11,17,23,29,经典例题例1:求4373091993被7除的余数。思路分析:如果将4373091993算出以后,再除以7,从而引得到,即4373091993=269120769,此数被7除的余数为1。但是能否寻找更为简变的办法呢?4733(mod7)3091(mod7)由同余的可乘性知:43730931(mod7)3(mod7)又因
15、为19935(mod7)所以:437309199335(mod7)15(mod7)1(mod7)即:4373091993被7除余1。例2: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,结果余数
16、有类似的规律,继续观察,可以得到:0,1,3,2,3,1,0,5,3,4,3,5,0,1,3,2,3,可以看出余数前12个数一段,将重复出现。702=510,第六段的第十个数为4,这便是原来数中第70个数被6除的余数。思路分析:我们被直接用除法算式,结果如何。例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的公倍数。
17、因此我们可以以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,1
18、99,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(mo
19、d7)不符合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判断以下计算是否正确(1)427843968267=1697598942346(2)427843968267=1697598981248思路分析:若直接将右边算出,就可判断417843968267=169778335328,
20、可知以上两结果均是错的;但是计算量太大。如果右式和左式相等,则它们除以某一个数余数一定相同。因为求一个数除以9的余数只需要先求这个数数字之和除以9的余数,便是原数除以9的余数。我考虑上式除以9的余数,如果余数不相同,则上式一定不成立。(1)从个位数字可知,右式的个位数字只能是8,而右式个位为6,因此上式不成立。(2)右式和左式的个位数字相同,因而无法断定上式是否成立,但是4+2+7+8+4=25,257(mod9)3+9+6+8+2+6+7=41,415(mod9)427847(mod9);39682675(mod9)42784396826735(mod9)8(mod9)(1+6+9+7+5+9+8+9+4+2+3+4+8)3(mod9)因此(2)式不成立以上是用除9取余数来验证结果是否正确,常被称为弃九法。不过应该注意,用弃九法可发现错误,但用弃九法没找出错误却不能保证原题一定正确。习题1、求169411611被7除的余数。3、判断结果是否正确:(1)54839117=49888511(2)12264522683=3344、乘法算式314592653=291093995的横线处漏写了一个数字,你能以最快的办法补出吗?5、13511,13903,14589被自然数m除所得余数相同,问m最大值是多少?