数论之同余与余数问题

1、第14讲 数论之同余与余数问题1、 被除数除数=商余数，被除数=除数商+余数2、 和差积的余数同余余数的和差积。3、 同余：ax余r, bx余r，则(a-b)是x的倍数，这种技巧常用于求除数的题目。4、 求被除数三大类问题:余同(最小公倍数的倍数加余数)，差同（最小公倍数的倍数减差），都不同（剩余定理）。5、 整除与余数：除以3或9的余数看数字之和，7、11、13是三位一格，奇位和减偶位和（减不够加7、11、13的若干倍），11也可以一位一格，奇位和减偶位和（减不够加11的若干倍）6、 个位数字：自然数的m次方的个位数字都可以看成4次方1个周期。7、 有规律的余数问题，常利用“和差积的余数同余

2、余数的和差积”，结合周期简化题目。【和差积的余数同余余数的和差积】【1】【解析】（9+7+2）(9-7)(7-2)=1825=180，180除以11余4.【2】【解】、除以3，余数是0，所以只须看表达式除以3余几注意：如果a除以3余, b 除以3余. ，那 ab 除以3所得的余数就是内除以3所得的余数因为4、7除以3余1，所以、，除以3，余数也是1 . 因为5、8除以3余2，所以、除以3，余数与, 除以3的余数相同而=16 除以3余1，所以=2除以3 余2 , =除以3余l（=11） 于是除以3，所得余数与l4l211除以3，所得余数相同，即余数是1 . 【3】【解】 有已知，乙，丙，丁三人取

3、走的七盒中，糖的块数是丁所取糖块数的5倍.八盒糖的总块数是917242830313344=216 216除以5的余数为1，所以甲取走的一盒除以5余1.因此甲取走的一盒中有31块奶糖.【4】【解法1】 甲余11人，乙余3611=25人.甲团人数与乙团人数的积除以36，余数与1125除以36的余数相同，即余23.所以最后一卷拍了23张，还可拍3623=13张.【解法2】因为除去最后一辆车，其它个车里两团代表人数都是36的倍数，所以剩下胶片是最后一辆车里两团代表拍完照留下的. 251136=723 还可拍3623=13(张).【5】【分析】任何数乘方的尾数都是4 个数一周期7是7、9、3、1循环，因

4、为20104 502 2，所以 尾数是9. 8 是8、4、2、6循环，因为98 4余2，所以尾数是4 . 9 是9、1、9、9循环，因为20094余1 ，所以尾的数是9 . 9+94=45，个位为5.【6】【分析】 求结果除以l0的余数即求从l 到2005 这2005 个数的个位数字是10 个一循环的，而对于一个数的幂方的个位数，我们知道它总是4 个一循环的，因此把每个加数的个位数按20 个一组，则不同组中对应的数字应该是一样的 首先计算的个位数字为m . 2005 个加数中有100 组多5 个数，100 组的个位数是m100的个位数即o , 另外5 个数为，它们和的个位数字是1476523

5、的个位数3.【7】【分析】 同余的性质的应用【解】 1433 ( mod7 ) ( mod 7) 1(mod 7) 5 (mod 7) . 【评析】 这类题都是通过找几次方除以7得余数1作为突破，大大简化题目的难度。【巩固】【解析】20118余3，与除以8的余数相同，33除以8余1，所以【同余-用于求除数】同余：ax余r, bx余r，则(a-b)是x的倍数。【基础知识练习】 【分析】 所求自然数减去 63 的差可被 247 与 248 整除，再考虑这个差被 26 除的余数【解】 设所求自然数减去63，差是 a ，则 a 被 247 与 248 整除，247 = 1913 , 248=2 124

6、 所以 a 被13与2整除，13与2 互质，得 a 被 26 整除原来的自然数是 a + 63 ，所以只要考虑 63 被 26 除后的余数 63 = 262+ 11 因此这个自然数被 26 除余11 答：所求余数是11. 【评析】 如果一个整数能被甲、乙两数整除，并不能得出它被甲、乙两数的积整除在甲、乙两数互质时，才能导出这个数被甲、乙两数的积整除 【1】【解析】由85-69=16，93-85=8，推出a=8或4或2，978=121.所以丁团分成每组a人的若干组后还剩1人。【2】【解析】 这个数a除55l,745个数去除551,745,1,1133,1327,所得的余数相同,所以有551,74

7、5,1133,1327两两做差而得到的数一定是除数a的倍数 1327-1133=194,1133-745=388,745-551=194,1327-745=582,1327-551=776,1133-551=582 这些数都是a的倍数,所以a是它们的公约数,而它们的最大公约数(194，388，194，582，776，582)=194 所以,这个数最大可能为194【3】【分析与解】 设这个除数为m,设它除63,90,130所得的余数依次为a,b,c,商依次为a,b,c 63m=aa 90m=bb 130m=cc a+b+c=25,则(63+90+130)-(a+b+c)=(a+b+c)m,即28

8、3-25=258=(a+b+c)m所以m是258的约数.258=2343,显然当除数m为2、3、6时,3个余数的和最大为3(2-1)=3，3(3-1)=6,3(6-1)=15,所以均不满足 而当除数m为432,433,4323时,它除63的余数均是63,所以也不满足 那么除数m只能是43,它除63,90,130的余数依次为20,4,1,余数的和为25,满足显然这3个余数中最大的为20【余数三大类问题-用于求被除数】(1)余同：最小公倍数的倍数+余数，（2）差同(差=除数-余数)：最小公倍数的倍数-差 (3)都不同：结合中国剩余定理与不定方程两边对某数求余数的方法。【1】【分析】 n 加上 1

9、，就可以被 10 、 9 、 8 、 、 2 整除【解】 由于n十l被10、9、8、2整除，而10、 9 、 8 、 、 2 的最小公倍数是 5987=2520 因此， n 十 1 被 2520 整除 n 的最小值是 2520 一 1 = 2519 答： n 的最小值是 2519 . 【2】【解】设这个数为23a7，因为它除以19余9，所以，23a7一9 =19a4a一2被19整除，即4a一2被19整除令a = l , 2 ，代入检验，在 a = 10 时，4a2 = 38 第一次被19整除，所以所求的自然教最小是23107 = 237 【3】【分析与解】设这个圆圈有n个孔,那么有n除以3余1

10、,n除以5余1.n能被7整除则将n-1是3、5的倍数,即是15的倍数,所以n=15t+1,又因为凡是7的倍数,即15t+1=7a,将系数与常数对7取模,有t+10(mod7),所以t取6或6与7的倍数和. 对应孔数为156+l=91或91与105的倍数和，满足题意的孔数只有91即这个圆圈上共有91个孔【活学活用】【1】 【解析一：教材方法】甲、乙两数的差被 3 整除，即甲、乙两数被 3 除的余数相同 一个自然数被 3 除，余数只有 3 种情况，即0、1、2. 由分析可知：甲、乙两数被 3 除，余数相同，下面分三种情况讨论（1） 如果甲、乙两数被 3 除都余 1 ，那么，它们的和被 3 整除，不

11、符合题意（2） 如果甲、乙两数被 3 除都余 1 ，那么，它们的和被 3 除余 2 , 也不符合题意（3） 如果甲、乙两数被 3 除都余 2 ，那么，它们的和被 3 除正好余 l . 答：甲数被 3 除的余数是 2 . 【解析二：致远推荐】a+b=3m+1，a-b=3n，解得2a=3m+3n+1，所以a=3(m+n)+12，无论m+n为奇数还是偶数，a除以3余2.【2】【解析】 设a、b、c为连续三项，则c= 3b一a考虑原数列各项除以3所得的余数，组成数列 0 , l , 0 , 2 , 0 , l , 0 , 2， 每4项重复出现考虑原数列各项除以2所得的余数，组成数列0，1，1，0，1，

12、1，0，1，1，每3项重复出现.因此，原数列最右边的（第70个）数，除以3余1（70 = 4172），除以2 所余0（70=3231）于是最右一个数被6除余4.【3】【分析】 算出 7 所得的余数，便可推得结论若把 2004连乘，用所得的结果除以 7 ，计算太复杂了！因此先找出与 2004 除以 7同余的最小数，然后根据余数的有关性质解题【解】 因为 2004 除以 7 的余数是 2 . 所以 7 与7 的余数相同而= = = 所以7与7=17的余数相同.故 7 的余数为 1 . 因为今天是星期一，所以再过天是星期二【评析】 若 a =pqr，则q与q 余数相同，在遇到一些非常大的数的若干次幂

13、时，可使用幂的相关性质进行分解，使大数化成小数，如：=,=【天天练】【1】【解】 甲数是13的倍数加7，乙数是13的倍数加9，所以它们的积是13的倍数加79，而79除以13余11，所以甲、乙的积除以13余11 . 【2】【解】 甲、乙手中卡片上的数之和必是3的倍数. 六张卡片上的数分别除以3，依次余2、1、0、0、1、l，推知只有后五个数之和能被3整除，所以丙手中卡片上的数是1193 . 【3】【解析】如下表所示：号码101126173193盘数1012103126221517312031930101101，126，173，193被3除的余数分别为2，0，2，1，故他们之间的比赛盘数如上表，由

14、表可以看出，126号运动员打了5盘是最多的。【4】【解】 1477一49 = 1428 是这两位数的倍数又1428=223717 =5128=6821 =8417 因此，所求的两位数51或68或84【5】【解】由199246=43 14得1992=464314，所以a= 43,r =14.【6】【分析】 这个整数除300、262得到相同的余数所以300一262的差，一定被这个整数整除也就是说，这个整数是300一262的因数同样，这个整数也是300一205的因数【解】 300一 262 = 38 =219 300 一 205 = 95 = 519所以这个整数是 19 . 答：这个整数是 19 .

15、【评析】 同余问题转化为整除问题，是解决这类问题的常用方法 【7】【解】 200一5 = 195 . 300一l = 299 , 400一10 = 390 195 , 299 , 390 的最大公约数是13于是，这个数是13 . 【8】【解】2008 被这样的自然数除余数是10 ，那么，1998 就是这些自然数的倍数，换句话说，我们要求1998 的约数有几个，但注意到除数比余数大，所以我们要求的是1998 的约数中那些大于10 的，枚举显然不可取，我们考虑用约数个数公式： 1998237 , d (1998) (ll)(3l) (1l) 16 其中小于10 的约数有l, 2, 3, 6, 9，

16、去掉它们还有11 个，因此这样的自然数共有11个【评析】 注意到除数比余数大【9】【分析】 同余的性质5的应用若ab ( mod m) , cd ( mod m)，那么acbd ( mod m) （可乘性）. 【解】 4182 (mod 13), 8148 (mod 13), 16164(mod 13), 根据同余的性质5 可得41881416162846412 (mod 13) . 所以，乘积418 火81 生只1616 除以13 余数是12 . 【评析】 若先求乘积，再求余数，计算量太大利用同余的性质可以使“大数化小”，减少计算量【10】【分析】a 与b 的和除以c的余数，等于a , b

17、分别除以c的余数之和（或这个和除以c 的余数）当余数之和大于除数时，所求余数等于余数之和再除以c 的余数【解】 根据递推关系把这串数除以9的余数列出来如下：l、3、8、4、6、2、7、o、5、l、3， 发现恰好每9个一循环，2000被9 除余数是2 ，所以第200个和第2 个一样除以9 的余数是3 . 【11】【解】 去掉3人后，总数被3、5、7整除，因而是105的倍数，原人数在90110之间，因而是1053=108.【12】【解】 3,4,5,6=60,601=59(人) 答：上体育课的同学最少有59名.【13】【解析】 到会人数加上1，正好是9与7的公倍数，因而是63的倍数. 这个数除以5余4，在63的小于200的倍数63 , 126 , 189中，只有189满足这一条件. 因此到会的代表有l88（= 189一l）人【14】【解析】如果 a = 35 ，则它被 14 除的余数是 7 . 如果 a 大于 35 ，则 a 一 35 能被 1981