同余的概念和性质

1、第5讲 同余的概念和性质解题思路：理解并熟记同余的性质，运用同余性质把数化小、化易。同余定义：若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为： ab（modm）. 性质1：若ab（mod m），bc（mod m），那么ac（mod m），（传递性）。性质2：若ab（mod m），cd（mod m），那么a±cb±d（mod m），（可加减性）。性质3：若ab（mod m），cd（mod m），那么acbd（mod m）（可乘性）。性质4：若ab（mod m），那么anbn（mod m），（其中n为自然数）。性质5：若acbc（mod m），

2、（c，m）=1，那么ab（mod m），（记号（c，m）表示c与m的最大公约数）。例1 判定288和214对于模37是否同余，74与20呢？例2 求乘积418×814×1616除以13所得的余数。例3 求14389除以7的余数。例4 四盏灯如图所示组成舞台彩灯，且每30秒钟灯的颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列？十位，上的数码，再设M=，求证：NM（mod 9）例6 求自然数的个位数字。习题1.验证对于任意整数a、b，式子ab（mod1）成立，并说出它的含义。2.已知自

3、然数a、b、c，其中c3，a除以c余1，b除以c余2，则ab除以c余多少？3.1993年的六月一日是星期二，这一年的十月一日是星期几？4.求3333555555553333被7除的余数。5.所有自然数如下图排列.问300位于哪个字母下面？6. 数，被13除余多少？7.求1993100的个位数字.第五讲 同余的概念和性质你会解答下面的问题吗？问题1：今天是星期日，再过15天就是“六·一”儿童节了，问“六·一”儿童节是星期几？这个问题并不难答.因为，一个星期有7天，而15÷7=21，即157×2+1，所以“六·一”儿童节是星期一。问题2：1993年

4、的元旦是星期五，1994年的元旦是星期几？这个问题也难不倒我们.因为，1993年有365天，而365=7×52+1，所以1994年的元旦应该是星期六。问题1、2的实质是求用7去除某一总的天数后所得的余数.在日常生活中，时常要注意两个整数用某一固定的自然数去除，所得的余数问题.这样就产生了“同余”的概念.如问题1、2中的15与365除以7后，余数都是1，那么我们就说15与365对于模7同余。同余定义：若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：ab（modm）. （*）上式可读作：a同余于b，模m。同余式（*）意味着（我们假设ab）：a-b=mk，

5、k是整数，即m（a-b）.例如：15365（mod7），因为365-15=350=7×50。5620（mod9），因为56-20=369×4。900（mod10），因为90-090=10×9。由例我们得到启发，a可被m整除，可用同余式表示为：a0（modm）。例如，表示a是一个偶数，可以写a0（mod 2）表示b是一个奇数，可以写b1（mod 2）补充定义：若m（a-b），就说a、b对模m不同余，用式子表示是：ab（modm）我们书写同余式的方式，使我们想起等式，而事实上，同余式与等式在其性质上相似.同余式有如下一些性质（其中a、b、c、d是整数，而m是自然数）。

6、性质1：aa（mod m），（反身性）这个性质很显然.因为a-a=0=m·0。性质2：若ab（mod m），那么ba（mod m），（对称性）。性质3：若ab（mod m），bc（mod m），那么ac（mod m），（传递性）。性质4：若ab（mod m），cd（mod m），那么a±cb±d（mod m），（可加减性）。性质5：若ab（mod m），cd（mod m），那么acbd（mod m）（可乘性）。性质6：若ab（mod m），那么anbn（mod m），（其中n为自然数）。性质7：若acbc（mod m），（c，m）=1，那么ab（mod m），（记

7、号（c，m）表示c与m的最大公约数）。注意同余式性质7的条件（c，m）1，否则像普通等式一样，两边约去，就是错的。例如610（mod 4），而35（mod 4），因为（2，4）1。请你自己举些例子验证上面的性质。同余是研究自然数的性质的基本概念，是可除性的符号语言。例1 判定288和214对于模37是否同余，74与20呢？解：288-214=74=37×2。288214（mod37）。74-20=54，而3754，7420（mod37）。例2 求乘积418×814×1616除以13所得的余数。分析 若先求乘积，再求余数，计算量太大.利用同余的性质可以使“大数化小”

8、，减少计算量。解：4182（mod13），8148（mod13），16164（mod13）， 根据同余的性质5可得：418×814×16162×8×46412（mod13）。答：乘积418×814×1616除以13余数是12。例3 求14389除以7的余数。分析 同余的性质能使“大数化小”，凡求大数的余数问题首先考虑用同余的性质化大为小.这道题先把底数在同余意义下变小，然后从低次幂入手，重复平方，找找有什么规律。解法1：1433（mod7）14389389（mod 7）8964+16+8+1而322（mod 7），344（mod7），

9、38162（mod 7），3164（mod 7），332162（mod 7），3644（mod 7）。389364·316·38·34×4×2×35（mod 7），143895（mod 7）。答：14389除以7的余数是5。解法2：证得14389389（mod 7）后，3632×342×41（mod 7），384（36）141（mod 7）。389384·34·31×4×35（mod 7）。143895（mod 7）。例4 四盏灯如图所示组成舞台彩灯，且每30秒钟灯的颜色改变

10、一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列？分析 与解答经观察试验我们可以发现，每经过4次互换，四盏灯的颜色排列重复一次，而1小时=60分钟=120×30秒，所以这道题实质是求120除以4的余数，因为1200（mod 4），所以开灯1小时四盏灯的颜色排列刚好同一开始一样。十位，上的数码，再设M=a0a1an，求证：NM（mod 9）。分析 首先把整数N改写成关于10的幂的形式，然后利用101（mod 9）。又 11（mod 9），101（mod 9），1021（mod 9），10n1（mod 9

11、），上面这些同余式两边分别同乘以a0、a1、a2、an，再相加得：a0a1×10+a2×102+an×10na0a1a2an（mod 9），即 NM（mod 9）.这道例题证明了十进制数的一个特有的性质：任何一个整数模9同余于它的各数位上数字之和。以后我们求一个整数被9除的余数，只要先计算这个整数各数位上数字之和，再求这个和被9除的余数即可。例如，求1827496被9除的余数，只要先求（1+827496），再求和被9除的余数。再观察一下上面求和式.我们可以发现，和不一定要求出.因为和式中18，2+7，9被9除都余0，求余数时可不予考虑.这样只需求46被9除的余数.

12、因此，1827496被9除余数是1。有人时常利用十进制数的这个特性检验几个数相加、相减、相乘的结果对不对，这种检查方法叫：弃九法。弃九法最经常地是用于乘法.我们来看一个例子。用弃九法检验乘式5483×911749888511是否正确？因为 54835483112（mod 9），911791170（mod 9），所以 5483×91172×00（mod 9）。但是 498885114+98+8+85+1+18（mod9），所以 5483×911749888511，即乘积不正确。要注意的是弃九法只能知道原题错误或有可能正确，但不能保证一定正确。例如，9875

13、98+7+52（mod 9），487348734（mod 9），324756893+2+4+75+6+8+98（mod 9），这时，9875×48732×432475689（mod 9）。但观察个位数字立刻可以判定9875×487332475689.因为末位数字5和3相乘不可能等于9。弃九法也可以用来检验除法和乘方的结果。例6 用弃九法检验下面的计算是否正确：23372458÷73123544。解：把除式转化为：3544×731223372458。 354435447（mod 9），731273124（mod 9）， 3544×731

14、27×41（mod 9），但 2337245823387（mod 9）。而 17（mod 9） 3544×731223372458，即 23372458÷73123544。例7 求自然数210031014102的个位数字。分析 求自然数的个位数字即是求这个自然数除以10的余数问题。解：210024×256256（mod 10），310134×25·31125·313（mod 10），4102（22）100·426·66（mod 10）， 2100310141026365（mod 10），即自然数21003

15、1014102的个位数字是5. 习题五1.验证对于任意整数a、b，式子ab（mod1）成立，并说出它的含义。2.已知自然数a、b、c，其中c3，a除以c余1，b除以c余2，则ab除以c余多少？3.1993年的六月一日是星期二，这一年的十月一日是星期几？4.求3333555555553333被7除的余数。5.所有自然数如下图排列.问300位于哪个字母下面？6.数，被13除余多少？（提示：先试除，可知13|111111，而19931（mod 6）。7.用弃九法检验下面运算是否正确：845×372=315340；12345×67891=838114385；1144192613÷2899739459。8.求1993100的个位数字.  习题五解答1.例：1|a-b，23（mod 1），715（mod 1），式子ab（mod 1）的含义是：任意整数a、b对模1同余.整数是模1的同余类。2.解：a1（mod c），b2（mod c），ab2（mod c）即a