15、同余法解题

1、第十五讲 同余法解题一、知识要点 在平时解题中，我们经常会遇到把着眼点放在余数上的问题。如：现在时刻是 7 时 30分，再过52小时是几时几分？我们知道一天是 24小时，52- 24=24,也就是说 52小时里包含两个整天再加上 4小时，这样就在 7时 30分的基础上加上 4小时，就是 11时 30分。很明显这个问题的着眼点是放在余数上了。1、同余的表达式和特殊符号 :37 和 44同除以 7，余数都是 2，把除数 7 称作“模 7”，37、44对于模7同余。记作：37三44(mod7), “三”读作同余。一般地，两个整数 A 和B,除以大于1的自然数M所得的余数相同，就称A、B对于模M同余，

2、记作：A三B(modM)2、同余的性质(1) A= A(modM)(每个整数都与自身同余，称为同余的反身性。)(2) 若A三B(modM)那么B三A(modM)(这称作同余的对称性)(3) 若A三B(modM) B三C(modM)贝U A三C(modM)(这称为同余的传递性)(4) 若A三B(modM) AD(modM)贝U A AB D(modM)(这称为同余的可加性、可减 性)贝U AX A BX D(modM)(称为同余的可乘性)(5) 若A= B(modM)则An = Bn (modM)，n为正整数，同余还有一个非常有趣的现象： 如果A三B(modM)那么M| (A B) (A-B的差

3、一定能被M整除),这是为什么呢？3、同余口诀：“差同减差，和同加和，余同取余，最小公倍加”这是同余问题的口诀。1) 、差同减差：用一个数除以几个不同的数，得到的余数，与除数的差相同，此时反 求的这个数，可以选除数的最小公倍数，减去这个相同的差数，称为：“差同减差”。 例：“一个数除以 4余1，除以 5余2，除以 6余3”，因为 4-1=5-2=6-3=3，所以取-3， 表示为 60n-3 。2) 、和同加和：用一个数除以几个不同的数，得到的余数，与除数的和相同，此时反 求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为：“和同加和”。 例：“一个数除以 4余3，除以 5余2，除以 6

4、余1”，因为 4+3=5+2=6+1=7，所以取+7， 表示为 60n+7。3) 、余同取余：用一个数除以几个不同的数，得到的余数相同，此时反求的这个数， 可以选除数的最小公倍数，加上这个相同的余数，称为：“余同取余”。例：“一个数 除以 4余1，除以 5余1，除以 6余1”，因为余数都是 1，所以取+1，表示为 60n+1。4) 、最小公倍加：所选取的数加上除数的最小公倍数的任意整数倍(即上面 1、2、3 中的60n)都满足条件，称为：“最小公倍加”，也称为：“公倍数作周期”。二、精典例题例1:有8只盒子，每只盒子内放有同一种笔。8只盒子所装笔的支数分别为17、23、33、36、38、42、

5、49、51支。在这些笔中，圆珠笔的支数是钢笔的支数的 2倍，钢笔的 支数是铅笔支数的-，只有一只盒子里放的是水彩笔。这盒水彩笔共有多少支？3【解析】“钢笔的支数是铅笔支数的-”可换为“铅笔的支数是钢笔的支数的 3倍”，那3么圆珠笔、铅笔、钢笔的总和一定是6的倍数，8盒一共有289支，因为289-6= 481,所以水彩笔的支数除以6 一定余1,故只能是49支。例2、用412、133和257除以一个相同的自然数，所得的余数相同，这个自然数最大 是几？【解析】假设这个自然数是a,因为412、133和257除以a所得的余数相同，所以a|(412 - 133),a | (412 257),a | (25

6、7 - 133),说明a是以上三个数中任意两数差的约数， 要求最大是几，就是求这三个差的最大公约数。(155,124,279)=31,所以a最大是31。例3、249 X 388X 234除以19,余数是几？【解析】如果把三个数相乘的积求出来再除以 19,就太麻烦了，利用同余思想解决就容 易了。因为 249三2 (mdo19 , 388 三 8 (mdo19 ,234 三6 (mdo19 ,所以 249X 388X 234三2X 8X 6三 1 (mdo19此题应用了同余的可乘性，同余的传递性。2222*萌 d例4、有一个1997位数，它的每个数位都是2,这个数除以13,商的第100位是几？最后

7、余数是几？2222* 厂 d【解析】 八 这个数除以13,商是有规律的。2222raw 13=170940170940商是170940六个数循环，那么I1 . - 1-,即川一-.二八F，我们从左向右数“ 170940的第4个数就是我们找的那个数“ 9”，所以商的第100位是9余数是几呢？2222凹访瓦-13 = 170940170940则 I 八所以商的个位数字应是“ 170940中的第4个，商应是9,相应的余数是5二、练习题1.求下列算式中的余数。1111叫厂#(1)3333V. /(3)-:2222、z /(2) i-.4444、 *(4)2.6254与37的积除以7,余数是几?3.如果某数除482, 992, 1094都余74,这个数是几?4、300、262、205被同一个整数除，得到相同的余数，这个整数是几?5、一个自然数被247除余63，被248除余63,求这个自然数被26除的余数6、一个自然数N被10除余9,被9除余8,被8除余7,被7除余6,被6除余5,被 5除余4,被4除余3,被3除余2,被2除余1,求N的