第5讲 同余的概念和性质.docx

第5讲同余的概念和性质解题思路：理解并熟记同余的性质，运用同余性质把数化小、化易。同余定义：假设两个整数a、b被自然数m除有一样的余数，那么称a、b对于模m同余，用式子表示为：性质1:假设a三bmodm,b三cCmodmJ,那么a三cCmodm传递性。性质2:假设a三bmodm,c三dmodmJ,那么a÷c三b÷dCmodm,性质3:假设a三bmodm,c三dCmodm，那么ac三bdmodm可乘性。其中n为自然数。性质4:假设a三bmodm，那么a"三b11modm性质5:彳及设ac三bcmodm),c,m=1,那么a三bmodm，记号c,m表示C与m的最大公约数。例1判定288和214对于模37是否同余，74与20呢？例2求乘积418X814X1616除以13所得的余数。例3求143，。除以7的余数。例4四盏灯如下图组成舞台彩灯，且每30秒钟灯的颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进展下去.请问开灯1小时四盏灯的颜色如何排列？HfIISS130秒度图30秒1囿开始第一次第二次例5设自然数N=anan-l'"alaO>其中a。、a：a?、，a&分别是个位,十位，上的数码，再设M=0+°HFan>求证：N三M(mod9例6求自然数210°+3101+4,02的个位数字。习题1 .验证对于任意整数a、b,式子a三b(modi)成立，并说出它的含义。2 .自然数a、b、c,其中c3,a除以C余1,b除以C余2,那么ab除以C余多少?六月一日是星期二，这一年的十月一日是星期几?5两+5555蚪被7除的余数。5 .所有自然数如下列图排列.问300位于哪个字母下面？ABCDEFG234-76589101114131215161993个16 .数五二1,被13除余多少？7,求1993°°的个位数字.第五讲同余的概念和性质你会解答下面的问题吗？问题1：今天是星期日，再过15天就是“六一儿童节了，问“六一儿童节是星期几？这个问题并不难答.因为，一个星期有7天，而15+7=2-1,即15=7X2+1,所以“六一儿童节是星期一。问题2：1993年的元旦是星期五，1994年的元旦是星期几？这个问题也难不倒我们.因为，1993年有365天，而365=7X52+1,所以1994年的元旦应该是星期六。“同余的概念.如问题1、2中的15与365除以7后，余数都是1,那么我们就说15与365对于模7同余。同余定义：假设两个整数a、b被自然数m除有一样的余数，那么称a、b对于模m同余，用式子表示为：a三b(modm).(*上式可读作：a同余于b,模m同余式(*意味着(我们假设a2b)：a-b=mk,k是整数,即ml(a-b).例如：15三365(mod7),因为365T5=350=7X50。56三20(mod9),因为56-20=36=9X4。90三0(modl0),因为90-0=90=10X9。由例我们得到启发，a可被m整除，可用同余式表示为：a三0(modm)。例如，表示a是一个偶数，可以写a三0(mod2)表示b是一个奇数，可以写b三l(mod2)补充定义：假设m'(a-b),就说a、b对模m不同余，用式子表示是:a卢b(modm)我们书写同余式的方式，使我们想起等式，而事实上，同余式与等式在其性质上相似.同余式有如下一些性质(其中a、b、c、d是整数，而m是自然数。性质1：a三a(modm，(反身性)这个性质很显然.因为a-a=0=m0。(对称性。性质3：假设a三b(modm),b三c(modm那么a三c(modm(传递性。性质4：假设a三b(modm减性。c三d(modm),那么a+c三b÷d(modm)(可加性质5：假设a三b(modm)c三d(modm),那么ac三bd(modm)(可乘性。性质6：假设a三b(modm，那么an三bn(modm(其中n为自然数)。性质7：假设ac三be(modm)表示C与m的最大公约数。(c,m)=1,那么a三b(modm),(记号(c,m)注意同余式性质7的条件(c,m)=1,否那么像普通等式一样，两边约去，就是错的。例如6三10(mod4),而3卢5(mod4),因为(2,4)10请你自己举些例子验证上面的性质。同余是研究自然数的性质的根本概念，是可除性的符号语言。例1判定288和214对于模37是否同余，74与20呢？解：V288-214=74=37×2o288三214(mod37)。774-20=54,而37*54,.74卢20(mod37)。例2求乘积418X814X1616除以13所得的余数。分析“大数化小，减少计算量。解：V418三2(modl3),814三8(modl3),1616三4(modl3),性质2：假设a三b(modm，那么b三a(modm根据同余的性质5可得：418×814×1616三2×8×4三64三12(modl3)。答：乘积418X814X1616除以13余数是12。例3求143呻余以7的余数。分析同余的性质能使“大数化小，凡求大数的余数问题首先考虑用同余的性质化大为小.这道题先把底数在同余意义下变小，然后从低次累入手，重复平方，找找有什么规律。解法1：V143三3(mod7)14389三389(mod7)V89=64+16+8+1而32三2(mod7),34三4(mod7),38三16三2(mod7),316三4(mod7),332三16三2(mod7),364三4(mod7)oV38三三3m.316.3三.3三4×4×2×3三5(mod7),14389三5(mod7)。答：143ffil除以7的余数是5。解法2：证得143"三3皿(mod7)后，36三32×34三2×4三1(mod7),384三(36)14三1(mod7)。.389三384343三1×4×3三5(mod7)o14389三5(mod7)。例4四盏灯如下图组成舞台彩灯，且每30秒钟灯的颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进展下去.请问开灯1小时四盏灯的颜色如何排列？adg三MU亘30秒回园30秒回回开始第一次第二次分析与解答经观察试验我们可以发现，每经过4次互换，四盏灯的颜色排列重复一次，而1小时=60分钟=120X30秒，所以这道题实质是求120除以4的余数，因为120三0(mod4),所以开灯1小时四盏灯的颜色排列刚好同一开场一样。例5设自然数N=ara*aia(),其中a。、ara?、，ar分别是个位,十位，上的数码，再设M=aO+alHFan,求证：N三M(mod9)。分析首先把整数N改写成关于10的哥的形式，然后利用10三1(mod9)。证明：:N=an-1-a1a0,IvIWo,F-I个O,1个0,=an×100-0+.1X167+-+a1X10+a0=×10n+an-lX10n-+3XIo+a0又:1三1(mod9),10三l(mod9,102三l(mod9)，10n三l(mod9),上面这些同余式两边分别同乘以a。、a,、a,、a,再相加得：a0-a×10+a2×102+an×10n三a0+a+a2HFan(mod9,即N三M(mod9.这道例题证明了十进制数的一个特有的性质：任何一个整数模9同余于它的各数位上数字之和。以后我们求一个整数被9除的余数，只要先计算这个整数各数位上数字之和，再求这个和被9除的余数即可。例如，求1827496被9除的余数，只要先求(1+8+2+7+4+9+6),再求和被9除的余数。再观察一下上面求和式.我们可以发现，和不一定要求出.因为和式中1+8,2+7,9被9除都余0,求余数时可不予考虑.这样只需求4+6被9除的余数.因此，1827496被9除余数是1。有人时常利用十进制数的这个特性检验几个数相加、相减、相乘的结果对不对，这种检查方法叫：弃九法。弃九法最经常地是用于乘法.我们来看一个例子。用弃九法检验乘式5483×9117三49888511是否正确？因为5483三5+4+8+3三11三2(mod9),9117三9+1+1+7三0(mod9),所以5483×9117三2×0三0(mod9。但是49888511三4+9+8+8+8÷5+l+l三8(mod9),所以5483×911749888511,即乘积不正确。要注意的是弃九法只能知道原题错误或有可能正确，但不能保证一定正确。例如，9875三9+8+7+5三2(mod9),4873三4+8+7+3三4(mod9),32475689三3+2+4+7+5+6+8+9三8(mod9,这时，9875×4873三2×4三32475689(mod9)。但观察个位数字立刻可以判定9875×487332475689.因为末位数字5和3相乘不可能等于9。弃九法也可以用来检验除法和乘方的结果。例6用弃九法检验下面的计算是否正确：23372458÷7312=3544o解：把除式转化为：3544×7312=23372458o,.3544三3+5+4+4三7(mod9),7312三7+3+1+2三4(mod9),.3544×7312三7×4三1(mod9),但23372458三2+3+3+8三7(mod9。而1卢7(mod9).3544×731223372458,即23372458÷731235440例7求自然数2100+3101+4102的个位数字。分析求自然数的个位数字即是求这个自然数除以10的余数问题。解：V2100三24x25三625三6(mod10，3101三34x2531三F531三3(modIo),4102三(2"10042三66三6(mod10),.2100+3101+4102三6+3+6三5(mod10),即自然数2呐+3皿+钎的个位数字是5.习题五1 .验证对于任意整数a、b,式子a三b(modi)成立，并说出它的含义。2 .自然数a、b、c,其中c3,a除以C余1,b除以C余2,那么ab除以C余多少？3 .1993年的六月一日是星期二，这一年的十月一日是星期几？由5+5555被7除的余数。5.所有自然数如下列图排列.问300位于哪个字母下面？ABCDEFG2347 658 9101114 131215 161993个16 .五:71数，被13除余多少？1提示：先试除，可知13111111,而1993三1(mod6)。7 .用弃九法检验下面运算是否正确:845X372=315340；12345×67891=838114385；1144192613÷28997=39459°融的个位数字.习题五解答1 .例：Ta-b,2三3(mod1),7三15(mod1),式子a三b(mod1)的含义是：任意整数a、b对模1同余.整数是模1的同余类。2 .解：Va三l(modC),b三2(modC),.ab=2(modC)即ab除以C余2。3 .1993年的十月一日是星期五。4 .解：,.3333三1(mod7),.33335555三1(mod7)。又,:5555三4(mod7,：.55553333=43333(mod7。而4s三l(mod7),.三(43)11三l(mod7),33335555+55553333三l+l三2(mod7),即3333蝴+5555*3被7除余2。5 .解：300三6(mod7)。.300与6在同一列，在D下面。6 .答：余1。7.不正确;不正确；不正确。8.1.