【提优教程】江苏省2012高中数学竞赛 第36讲 同余教案.doc

《【提优教程】江苏省2012高中数学竞赛 第36讲 同余教案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第36讲同余同余是数论中的重要概念，同余理论是研究整数问题的重要工具之一。设m是一个给定的正整数，如果两个整数a与b用m除所得的余数相同，则称a与b对模同余，记作，否则，就说a与b对模m不同余，记作，显然，；1、同余是一种等价关系，即有自反性、对称性、传递性1).反身性：；2).对称性：；3).传递性：若，则;2、加、减、乘、乘方运算若（modm）（modm）则（modm），（modm），（modm）3、除法设（modm）则（mod）。A类例题例1．证明：一个数的各位数字的和被9除的余数等于这个数被9除的余数。分析20≡2(mod9)，500≡5(mod9)，7000≡7(mo

2、d9)，……，由于10n－1=9M，则10n≡1(mod9)，故an×10n≡an(mod9)。可以考虑把此数变为多项式表示an×10n+an-1×10n-1+…+a1×10+a0后处理。证明设a==an×10n+an-1×10n-1+…+a1×10+a0，∵10≡1(mod9)，∴10n≡1(mod9)，∴an×10n+an-1×10n-1+…+a1×10+a0≡an+an-1+…+a1+a0。说明要熟练记忆并应用常见的数据模的特征。例2．A，B两人玩一种32张扑克牌的取牌游戏，A先取，以后轮流进行，每次只能从剩下的牌中取1张，或者质数张牌，谁取到最后一张牌获胜，问：谁有必胜

3、策略？分析13用心爱心专心原有32张牌，如果A总取奇数张牌，B只要取1张牌，使A面临偶数张牌就可以了，此时A总不能取完偶数张牌。但2是质数，A可以取两张牌。注意到32是4的倍数，A只能取奇数张牌或2张牌，B的应对方案稍作调整，可以有必胜的策略。解B有必胜策略。由于32≡0（mod4），而A取的牌不能是4及其倍数，从而A取后，剩下的牌张数x≡3（mod4），或x≡2（mod4），或x≡1（mod4），于是B可以通过取1，2或3张牌，使得剩下的牌的张数y≡0（mod4），所以，B依次此策略，在A取后，剩下的牌张数不同余于0（mod4），总是有牌，而B取后剩下的牌的张数y≡0（mod

4、4），从而B能取到最后一张牌。例3在已知数列1，4，8，10，16，19，21，25，30，43中，相邻若干数之和，能被11整除的数组共有多少组。分析相邻若干数之和可通过，中来实现。解记数列各对应项为并记依次为1、5、13、23、39、58、79、104、134、177它们被11除的余数依次为1、5、2、1、6、3、2、5、2、1。由此可得由于是数列相邻项之和，且当时，则满足条件的数组有：3+1+3=7组。说明在解题的适当时候取模的运算会使运算量减少，并使过程变得简洁。情景再现1．能否把1，2，……，1980这1980个数分成四组，令每组数之和为，且满足。2．两人做一种游戏：轮

5、流报数，报出的数只能是1，2，3，4，5，6，7，8，9，10，把两人报出的数连加起来，如果得数是2003，最后报数的人就获胜．现在甲、乙两人已经依次报过3，5，7，5，6，乙再接着报下一个数，那么乙经过动脑筋，发现应该报某一号就有赢的把握．试问乙应该报哪一号？以后各次报数时乙应如何报数才能保证赢？3．（前南斯拉夫数学竞赛，1988年）有27个国家参加的一次国际会议，每个国家有两名代表．求证：不可能将54位代表安排在一张圆桌的周围就坐，使得任一国家的两位代表之间都夹有9个人．B类例题13用心爱心专心例4．共1998个小朋友围坐一圈，从某人开始逆时针方向报数，从1报到64，一直报

6、下去，直到每人报过10次为止．⑴有没有报过5，又报过10的人？⑵有没有报过5，又报过11的人？分析报过5（10）的人的编号模64的同余特征是本题的突破口。解把这些学生依次编为1——1998号．⑴设既报过5又报过10的人原编为x号，则有x+1998k≡5(mod64)x+1998l≡10(mod64)∴1998(l－k)≡5(mod64)，即1998(l－k)=5+64n，这不可能．⑵既报5又报11的人原来编为x号．x+1998k≡5(mod64)x+1998l≡11(mod64)∴1998(l－k)≡6(mod64)，即14(l－k)=6+64n，Þ7(l－k)=3+32n，取

7、n=1，得l－k=5，即第k圈报5的人，第k+5圈后报11，∵1998×5=64×156+6，这说明前5圈报5的人共157个，即共有157人既报5又报11．说明本题是同余在解不定方程（组）上的一个简单应用。例5（1992年友谊杯国际数学竞赛）求最大的正整数x，使得对任意y∈N，有x

8、（）。分析x最大不超过的最小值18，（mod18）（mod2）,（mod9）。解由条件，x

9、（7＋12－1），x

10、18，故x≤18。下证：对任意y∈N，有18

11、（）。事实上，首先是偶数，所以2

12、（）；其次，当y=