奥数-同余的概念及性质+详解过程讲解学习

1、第五讲 同余的概念和性质你会解答下面的问题吗？问题1今天是星期日，再过15天就是“六一”儿童节了，问“六一”儿童节是 星期几？这个问题并不难答因为，一个星期有7天，而15- 7=21,即15= 7X 2+1,所以 “六一”儿童节是星期一。问题 2： 1993 年的元旦是星期五， 1994 年的元旦是星期几？这个问题也难不倒我们.因为，1993年有365天，而365=7X 52+1，所以1994年的元 旦应该是星期六。问题 1、2 的实质是求用 7去除某一总的天数后所得的余数 . 在日常生活中，时常要注 意两个整数用某一固定的自然数去除， 所得的余数问题 .这样就产生了“同余”的概念. 如问题

2、1、2中的 15与 365除以 7后，余数都是 1，那么我们就说 15与 365对于模 7 同余。同余定义：若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余， 用式子表示为：a= b (modr) .(*)上式可读作：a同余于b，模m同余式(*)意味着(我们假设a> b)：a-b=mk，k 是整数，即 m|( a-b).例如： 15三365 ( mod7，因为 365-15=350=7 X 50。 56三20 (mod9，因为 56-20=36 = 9X4。 90三 0 (mod10，因为 90-0 = 90=10X 9。由例我们得到启发，a可被m整除，可用同余式表示为

3、：a= 0 (modm。例如，表示a是一个偶数，可以写a= 0 (mod 2)表示 b 是一个奇数，可以写b 三 1 (mod 2)补充定义：若m(a-b)，就说a、b对模m不同余，用式子表示是：a b ( modm)我们书写同余式的方式， 使我们想起等式， 而事实上， 同余式与等式在其性质上相似 同余式有如下一些性质(其中 a、b、c、d是整数，而m是自然数)。性质1: a=a (mod m，(反身性)这个性质很显然.因为a-a=0=m - 0。性质2：若a= b ( mod m，那么b= a (mod m ,(对称性)。'性质 3: 若 a= b ( mod m , b= c (m

4、od m)，那么 a= c (mod m),(传递性)。性质 4：若 a= b ( mod m , c= d (mod m，那么 a±c=b±d (mod m ,(可加减性 。性质 5：若 a= b ( mod m , c= d (mod m)，那么 ac= bd (mod m (可乘性)。性质6:若a= b ( mod m，那么an= bn (mod m),(其中n为自然数)。'性质 7： 若 ac= bc (mod m , ( c, m) =1, 那么 a= b (mod m，(记号(c, m)表示c与m的最大公约数)。注意同余式性质7的条件(c, n)二1,否

5、则像普通等式一样，两边约去，就是错的。例如 6= 10 (mod 4)，而 35 (mod 4)，因为(2, 4)工 1。请你自己举些例子验证上面的性质。同余是研究自然数的性质的基本概念,是可除性的符号语言。例 1 判定 288 和 214 对于模 37 是否同余, 74 与 20 呢？解：288-214=74=37X 2。 288三214 (mod37) 74-20=54，而 3754, 7420 (mod37。例2求乘积418X 814X 1616除以13所得的余数。分析 若先求乘积，再求余数，计算量太大 . 利用同余的性质可以使“大数化小”，减 少计算量。解：418三 2 (mod13

6、,814三 8 (mod13 , 1616三 4 ( mod13 , 根据同余的性质 5可得：418X 814X 1616三2X 8X 4三64三 12 (mod13。答：乘积 418X 814X 1616除以 13余数是 12。例 3 求 14389除以 7 的余数。分析 同余的性质能使 “大数化小” ,凡求大数的余数问题首先考虑用同余的性质化大 为小. 这道题先把底数在同余意义下变小,然后从低次幂入手, 重复平方, 找找有什么规律。解法 1：t 143三 3 (mod789 89 143 = 3 (mod 7 )/ 89= 64+16+8+1而 32= 2 (mod 7),43 = 4 (

7、mod7 ,38三 16三 2 ( mod 7),36=4 (mod 7),332三 16三 2 (mod 7),364=4 (mod 7)。.389三364 316 38 3三4X 4X 2X 3三5 (mod 7),14389= 5 (mod 7)。答：14389除以7的余数是5。解法 2:证得 14389= 389 (mod 7)后，6243 三3 X 3 三2X 4三 1 (mod 7),.384=( 36) 14= 1 (mod 7)。.389三384 34 3三 1 X4X 3三5 (mod 7)。89.143 = 5 (mod 7)。例4四盏灯如图所示组成舞台彩灯，且每 30秒钟

8、灯的颜色改变一次，第一次上下两 灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直 进行下去请问开灯1小时四盏灯的颜色如何排列？1=30秒匱囿30秒華一次甫二欢分析 与解答经观察试验我们可以发现，每经过4次互换，四盏灯的颜色排列重复一次， 而1小时=60分钟=120X 30秒，所以这道题实质是求120除以4的余数，因为120三0(mod 4),所以开灯1小时四盏灯的颜色排列刚好同一开始一样。例5设自然数N =尙细厂町師其中彌、叶蚣细分别是个位 十位，上的数码，再设 M=a肝a1 + an，求证：NM(mod 9)。分析 首先把整数N改写成关于10的幕的形式，然后利用10=

9、1 (mod 9) <证明；T W=気亦/=X 100 0+! x 100-0+- + a/X10+ac二备X lOjVi *叽t十坷X 10+又 1 = 1 (mod 9)，10= 1 (mod 9)，210 = 1 ( mod 9)，10n= 1 ( mod 9),上面这些同余式两边分别同乘以 a。、ai、a2、an,再相加得：2ao+ ai x 10+比 x 1。+anX 10n=ao+ ai+ a2 + + an (mod 9),即 N = M (mod 9).这道例题证明了十进制数的一个特有的性质：任何一个整数模 9 同余于它的各数位上数字之和。以后我们求一个整数被 9除的余数

10、,只要先计算这个整数各数位上数字之和,再求这 个和被 9 除的余数即可。例如,求 1 827496被9除的余数,只要先求( 1+8+2+7+4+9+6),再求和被 9除 的余数。再观察一下上面求和式 .我们可以发现,和不一定要求出 . 因为和式中 1+8, 2+7, 9 被9除都余 0,求余数时可不予考虑 .这样只需求 4+6被9除的余数.因此, 1827496 被9除余数是 1。有人时常利用十进制数的这个特性检验几个数相加、相减、相乘的结果对不对,这种 检查方法叫：弃九法。弃九法最经常地是用于乘法 . 我们来看一个例子。用弃九法检验乘式5483x 9117三49888511是否正确？因为 5

11、483 三5+ 4+ 8+ 3三 11 三2 (mod 9),9117三 9+ 1 + 1 + 7三 0 (mod 9),所以 5483 x 9117三2X 0三0 ( mod 9)。但是 49888511 三 4+9+ 8+8+8+ 5+1+1=8 (mod9 ,所以5483 x 9117工49888511，即乘积不正确。要注意的是弃九法只能知道原题错误或有可能正确,但不能保证一定正确。例如，9875= 9+ 8+7+5= 2 (mod 9), 4873= 4+ 8+ 7+ 3= 4 (mod 9),32475689三 3+2+4+7+ 5+6+8+9=8 (mod 9),这时，9875X4

12、873三2X4三32475689 (mod 9)。但观察个位数字立刻可以判定 9875X 4873工32475689.因为末位数字5和3相乘不可 能等于 9。弃九法也可以用来检验除法和乘方的结果。例 6 用弃九法检验下面的计算是否正确：23372458- 7312= 3544。解：把除式转化为：3544X 7312= 23372458。3544 = 3+ 5 + 4+ 4= 7 (mod 9),7312三 7+ 3+ 1+ 2= 4 (mod 9), 3544 X 7312= 7X 4= 1 (mod 9),但 23372458=2+3+3+8=7(mod 9)。而 17( mod 9) 3544 X 7312工 23372458,即 23372458 - 7312工3544。例 7 求自然数 2100+ 3101 + 4102 的个位数字。分析 求自然数的个位