1、第讲同余的概念和性质第讲-同余的概念和性质 作者：日期:第讲 同余的概念和性质解题思路：理解并熟记同余的性质,运用同余性质把数化小、化易。同余定义:若两个整数a、b被自然数m除有相同的余数,那么称a、b对于模m同余,用式子表示为： b（om） 性质1:若b（mo m)，bc(mod m）,那么ac（mod m)，(传递性）。性质2：若ab(odm）,d（mo m),那么acbd（mdm）,（可加减性)。 性质3:若ab(modm），cd(od m)，那么cbd(modm）（可乘性)。 性质4：若(md），那么ab（m),(其中为自然数）。 性质：若acbc(m），（c，m）=1，那么b(od
2、m),(记号(,m）表示c与m的最大公约数）。例1 判定88和14对于模37是否同余，4与20呢？例2 求乘积18811616除以13所得的余数。例3 求1489除以7的余数。例4 四盏灯如图所示组成舞台彩灯，且每秒钟灯的颜色改变一次,第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列？十位,上的数码，再设M+,求证：NM(mo9)例 求自然数+的个位数字。习题1.验证对于任意整数、b，式子b(od1）成立,并说出它的含义。2.已知自然数a、b、c,其中c3,除以c余1,除以c余，则a除以余多少？3.99年的六月一日是
3、星期二,这一年的十月一日是星期几？.求33355555333被7除的余数。.所有自然数如下图排列.问30位于哪个字母下面？6 数，被13除余多少?7.求193100的个位数字第五讲 同余的概念和性质 你会解答下面的问题吗?问题1：今天是星期日，再过15天就是“六一”儿童节了，问“六一”儿童节是星期几？ 这个问题并不难答.因为,一个星期有天，而57=2，即15=2+1,所以“六一”儿童节是星期一。 问题2:199年的元旦是星期五,94年的元旦是星期几？ 这个问题也难不倒我们.因为,93年有365天，而36752+1，所以199年的元旦应该是星期六。 问题1、2的实质是求用7去除某一总的天数后所得
4、的余数.在日常生活中,时常要注意两个整数用某一固定的自然数去除,所得的余数问题.这样就产生了“同余”的概念.如问题1、2中的1与365除以后,余数都是,那么我们就说15与35对于模同余。 同余定义：若两个整数a、b被自然数m除有相同的余数,那么称、对于模m同余，用式子表示为: ab(dm). (*) 上式可读作: a同余于b,模m。同余式（*)意味着(我们假设a）：=mk，k是整数,即m(a-）. 例如：15365(mo7)，因为6-5=35075。 5620（mod），因为56-2=369。 900(od)，因为90090=1。由例我们得到启发，可被整除，可用同余式表示为：a0（odm)。
5、例如,表示a是一个偶数，可以写 a0(mod2) 表示b是一个奇数,可以写 b（md ) 补充定义:若m（ab)，就说a、对模m不同余,用式子表示是： b(mdm)我们书写同余式的方式，使我们想起等式,而事实上，同余式与等式在其性质上相似同余式有如下一些性质(其中a、b、c、d是整数,而m是自然数）。 性质1:aa(mod m）,（反身性） 这个性质很显然.因为-=0=m0。 性质2:若ab(mod m），那么ba（mo m)，(对称性)。 性质3:若b（md m)，bc（mod ）,那么ac（modm),（传递性)。性质4:若a(mom），cd(modm），那么acbd(mod ),（可加减
6、性)。 性质5:若a(md m),cd（md m),那么acbd(md m）（可乘性)。性质6:若(mdm),那么anbn（mod ),（其中n为自然数）。性质7：若acbc(modm),(c,m）1，那么ab（odm），（记号（,)表示与m的最大公约数）。 注意同余式性质7的条件(c,)1，否则像普通等式一样,两边约去,就是错的。例如610（d 4),而35(m4）,因为(2，)。 请你自己举些例子验证上面的性质。同余是研究自然数的性质的基本概念,是可除性的符号语言。例1判定28和214对于模37是否同余，4与0呢？ 解:28-2144=37。 288214(m3)。 -2=4,而3754,
7、 720(mo7)。例2 求乘积48814161除以13所得的余数。分析若先求乘积,再求余数,计算量太大.利用同余的性质可以使“大数化小”,减少计算量。解:2（md3)， 814（m1）,1614(mod13)， 根据同余的性质5可得: 4881116812（o13)。 答:乘积484116除以13余数是1。例 求14389除以7的余数。分析 同余的性质能使“大数化小”,凡求大数的余数问题首先考虑用同余的性质化大为小.这道题先把底数在同余意义下变小，然后从低次幂入手，重复平方,找找有什么规律。解法：133(md7） 1489389(d7)864+16+8+1 而22（mod 7)，34(mod
8、7）， 3816（od 7)， 31(mo ）， 33212(mod 7), 3644（md 7）。 38936431834423(md ), 4395(od7)。 答：48除以7的余数是5。 解法：证得149389（od7)后，363341(mod 7), 384(3)141（mod 7）。3893841435(mod7）。143895（mod )。例4 四盏灯如图所示组成舞台彩灯,且每30秒钟灯的颜色改变一次,第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列?分析 与解答经观察试验我们可以发现，每经过次互换，四盏
9、灯的颜色排列重复一次，而1小时=60分钟=200秒,所以这道题实质是求120除以4的余数,因为0(o4）,所以开灯1小时四盏灯的颜色排列刚好同一开始一样。十位,上的数码，再设M0a1an，求证:N（md9）。分析 首先把整数改写成关于1的幂的形式,然后利用101(mod9)。 又 11（d 9）, 01（mod 9), 1021（d 9）， 10n1（mo 9), 上面这些同余式两边分别同乘以、a2、an,再相加得： 0a110+a2102+n10n a+a+a2+n（md9)， 即 N(mod 9)这道例题证明了十进制数的一个特有的性质: 任何一个整数模9同余于它的各数位上数字之和。 以后我
10、们求一个整数被9除的余数，只要先计算这个整数各数位上数字之和,再求这个和被9除的余数即可。 例如，求1827496被9除的余数,只要先求(+82+496)，再求和被9除的余数。 再观察一下上面求和式.我们可以发现,和不一定要求出.因为和式中1+8,2+7,9被9除都余0,求余数时可不予考虑这样只需求46被除的余数因此，82496被9除余数是1。有人时常利用十进制数的这个特性检验几个数相加、相减、相乘的结果对不对,这种检查方法叫:弃九法。弃九法最经常地是用于乘法.我们来看一个例子。用弃九法检验乘式58397488811是否正确？ 因为 483548+112（mo 9), 9179+170(od
11、）， 所以 58391120（mo 9）。但是498885114+9+88+85+1+1 （md9）， 所以 548917498881,即乘积不正确。 要注意的是弃九法只能知道原题错误或有可能正确，但不能保证一定正确。 例如，989+87+52(m9）， 473487+34（od 9)， 34756893+756+8+9 (mod 9)， 这时,873432468(md ）。 但观察个位数字立刻可以判定988733475689.因为末位数字5和相乘不可能等于9。 弃九法也可以用来检验除法和乘方的结果。例6用弃九法检验下面的计算是否正确: 2372312544。 解：把除式转化为： 354473
12、12=232458。 3+447（mod ）, 31273+1+24（od 9)， 5473171(mod 9)， 但23372582+3387(mod 9）。 而 17（mod) 5431237248， 即2337245832354。例7求自然数21031014102的个位数字。分析 求自然数的个位数字即是求这个自然数除以0的余数问题。解:2002466（od 10），31134115（mod 10)， 4102(22)00426(mod 10）,210031014106365（od 10)， 即自然数100+11+102的个位数字是5.习题五 1.验证对于任意整数、b,式子ab(md）成立
13、,并说出它的含义。 2.已知自然数、b、c,其中c,a除以余1，b除以c余2,则ab除以c余多少?3.993年的六月一日是星期二,这一年的十月一日是星期几? .求33555555333被7除的余数。 5.所有自然数如下图排列问30位于哪个字母下面？ 数,被13除余多少?(提示:先试除，可知13|11111，而19931（mod 6)。 .用弃九法检验下面运算是否正确： 84537231534；2357891=11485; 11492132899739459。 8求193100的个位数字习题五解答1.例：1a-b，23（mod1）,7（mod 1），式子ab(mod 1)的含义是：任意整数、b对模1同余.整数是模1的同余类。 .解:1（md ）,b2（d ）， b=2(mod c) 即除以c余。 93年的十月一日是星期五。 4.解: 3331（mod 7）， 33335551(od7)。又 5554（o 7）, 5555333=433（od ）。而 31(mod 7）, 4333(4)111（mod 7）, 333355555555331+12(mod 7）， 即333355555555333被除余2。 解：3006(m 7)。 300与6在同一列，在下面。6.答：余1。 .不正确; 不正确；不正确。8.1
