第 17 讲 同 余
同余是数论中的重要概念，同余理论是研究整数问题的重要工具之一。
设m是一个给定的正整数，如果两个整数a与b用m除所得的余数相同，则称a与b对模同余，记作a?b(modm)，否则，就说a与b对模m不 同余，记作a?b(modm)，
显然，a?b(modm)?a?km?b,(k?Z)?m|(a?b)； 1、 同余是一种等价关系，即有自反性、对称性、传递性
1).反身性：a?a(modm)；
2).对称性：a?b(modm)?b?a(modm)；
3). 传递性：若a?b(modm)，b?c(modm)则a?c(modm); 2、加、减、乘、乘方运算
若 a?b（mod m） c?d（mod m）
cbd?则 a?c?b?d（mod m），a3、除法
（mod m），a?b（mod m）
nn设 ac?bd（mod m）则 a?b（mod
m）。 (c,m)A类例题 例1．证明： 一个数的各位数字的和被9除的余数等于这个数被9除的余数。 分析 20≡2(mod9)，500≡5(mod9)，7000≡7(mod9)，??，由于10n－1=9M，则10n
≡1(mod9)，故an×10n≡an (mod9)。可以考虑把此数变为多项式表示an×10n+ an-1×10n-1+?+ a1×10+a0后处理。
证明 设a=anan?1a1a0=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张，或者质数张牌，谁取到最后一张牌获胜，问：谁有必胜策略？
分析 原有32张牌，如果A总取奇数张牌，B只要取1张牌，使A面临偶数张牌就可以了，此时A总不能取完偶数张牌。但2是质数，A可以取两张牌。注意到32是4的倍数，
A只能取奇数张牌或2张牌，B的应对方案稍作调整，可以有必胜的策略。
解 B有必胜策略。由于32≡0（mod 4），
而A取的牌不能是4及其倍数，从而A取后，剩下的牌张数x≡3（mod 4），或x≡2（mod 4），或x≡1（mod 4），
于是B可以通过取1，2或3张牌，使得剩下的牌的张数y≡0（mod 4）， 所以，B依次此策略，在A取后，剩下的牌张数不同余于0（mod 4），总是有牌，而B取后剩下的牌的张数y≡0（mod 4），从而B能取到最后一张牌。
例3 在已知数列1，4，8，10，16，19，21，25，30，43中，相邻若干数之和，能被11整除的数组共有多少组。
分析 相邻若干数之和可通过Sk?a1?a2?现。
解 记数列各对应项为ai,i?1,2,并记Sk?a1?a2?10，?ak，k?1,2,,n中sm?st(m?t)来实
?ak ?S1,S2,,S10 依次
为1、5、13、23、39、58、79、104、134、177它们被11除的余数依次为1、5、2、1、6、
3、2、5、2、1。由此可得
S1?S4(mod11)?S10(mod11),S2?S8(mod11),S3?S7(mod11)?S9(mod11)
由于Sk?Sj是数列{ai}相邻项之和，且当Sk?Sj(mod11)时 11|Sk?Sj，则满足条件的数组有：3+1+3=7组。
说明 在解题的适当时候取模的运算会使运算量减少，并使过程变得简洁。
情景再现
1．能否把1，2，??，1980这1980个数分成四组，令每组数之和为S1，S2，S3，S4，且满足S2?S1，＝10，S3?S2＝10，S4?S3＝10。
2．两人做一种游戏：轮流报数，报出的数只能是1，2，3，4，5，6，7，8，9，10，把两人报出的数连加起来，如果得数是2003，最后报数的人就获胜．现在甲、乙两人已经依次报过3，5，7，5，6，乙再接着报下一个数，那么乙经过动脑筋，发现应该报某一号就有赢的把握．试问乙应该报哪一号？以后各次报数时乙应如何报数才能保证赢？ 3．（前南斯拉夫数学竞赛，1988年）有27个国家参加的一次国际会议，每个国家有两名代表．求证：不可能将54位代表安排在一张圆桌的周围就坐，使得任一国家的两位代表之间都夹有9个人．
B类例题
例4．共1998个小朋友围坐一圈，从某人开始逆时针方向报数，从1报到64，一直报下去，直到每人报过10次为止． ⑴ 有没有报过5，又报过10的人？ ⑵ 有没有报过5，又报过11的人？
分析 报过5（10）的人的编号模64的同余特征是本题的突破口。 解 把这些学生依次编为1——1998号． ⑴设既报过5又报过10 的人原编为x号，则有 x+1998k≡5 (mod 64) x+1998l≡10(mod 64)
∴ 1998(l－k)≡5(mod 64)，即1998(l－k)=5+64n，这不可能． ⑵ 既报5又报11的人原来编为x 号．
x+1998k≡5 (mod 64) x+1998l≡11(mod 64)
∴ 1998(l－k)≡6(mod 64)，即14(l－k)=6+64n，?7(l－k)=3+32n，取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|（7?12y?1）。
yy分析 x最大不超过7?12y?1的最小值18，7?12y?1?0（mod18）y。 ?7y?12y?1?0（mod2）, 7y?12y?1?0（mod9）
解 由条件，x |（7＋12－1），x |18，故x?18。下证：对任意y∈N，有18|（7?12y?1）。
y 事实上，首先7?1是偶数，所以2|（7?12y?1）；其次，当y=3k（k∈N*）时，7y?12y?13kkyy≡(7)?1≡1－1≡0（mod 9），当y=3k＋1（k∈N*）时，7?12y?1≡7?(7)?3?1
y3k
≡7＋3－1≡0（mod 9），当y=3k＋2时，7y?12y?1≡72?(73)k?3?1≡49－4≡0（mod 9）。故对任意y∈N*，有9|7y?12y?1。∵（2，9）=1 ∴18|7y?12y?1 所求的x为18
说明 本题中将7y?12y?1模18分解为模2与模9来处理充分观察到7模9的特征。
n例6 试求出一切可使n?2?1被3整除的自然数n。
分析 3|n?2n?1，则n?2n?2(mod3)。对n按6的同余类分类处理。
n解：若3|n?2n?1，则n?2n?2(mod3)考虑到n及2n，则当n?6k?1时，(k?0、1、2、)n?2?(6k?1)?2n6k?1?(12k?2)?(3?1)?2(mod3)k
当n?6k?2时，(k?0、1、2、)n?2n?(6k?2)?26k?2?(24k?8)?(3?1)k?2(mod3)当n?6k?3时，(k?0、1、2、)n?2n?(6k?3)?26k?3?0(mod3)当n?6k?4时，(k?0、1、2、)n?2n?(6k?4)?26k?4?(96k?64)?(3?1)k?1(mod3)
当n?6k?5时，(k?0、1、2、)n?2n?(6k?5)?26k?5?(6?32k?160)?(3?1)k?1(mod3)当n?6k?6时，(k?0、1、2、)n?2n?(6k?6)?26k?6?0(mod3)由上可知当且仅当n?6k?1，6k?2时，n?2n能被3整除；说明 要体会模6的选取。n?2中对n按模3分类，对2按模2分类可以分别确定结果，所以选择按模6分类。
nn
情景再现
4．设a为小于100的自然数，且a3+23能被24整除，这样的a有多少个？
105．求10除以13的余数。
n6． 有三堆棋子的个数分别为19，8，9．现进行如下操作：每次从三堆中的任意两堆中分别取出1个棋子，然后把这2个棋子都加到另一堆上去．试问：能否经过若干次这样的操作使得（1）三堆的棋子数目分别为2，12，22；（2）三堆棋子的数目均为12．
C类例题 例7（第20届IMO试题）数1978n与1978m的最末三位数相等，试求正整数m和n，使得n+m取最小值，这里n?m?1.
分析 数1978n与1978m的最末三位数相等等价于1978n-m≡1（mod1000），寻找最小的n-m及m。
n解 由已知1978?1078m(mod1000),而1000=8×125，所以
1978n?1078m(mod8) ①
1978n?1078m(mod125) ②
因n?m?1，且（1978m，125）=1，则由②式知1978n-m≡1（mod125）③
又直接验证知，1978的各次方幂的个位数字是以8、4、2、6循环出现的，所以只有n－m为4的倍数时，③式才能成立，因而可令n－m=4k.由于. n+m=（ n－m）+2m=4k+2m，因而只需确定出k和m的最小值.
4
先确定k的最小值：因为19784=（79×25+3）≡34≡1（mod5），19784≡34≡6（mod25）.故可令19784=5t+1，而5不整除t，从而0≡1978n-m－1=19784k－1=（5k+1）k－1≡
k(k?1)?(5t)2+k?5t(mod125)，显然，使上式成立的k的最小值为25. 2再确定m的最小值：因1978≡2（mod8），则由①式知，2n?2m(mod8) ④ 由于n?m?1,④式显然对m=1，2不成立，从而m的最小值为3.
故合于题设条件的n+m的最小值为106.
说明 此例中我们用了这样一个结论：1978的各次方幂的个位数字是以8，4，2，6循环出现，即，当r=1，2，3，4时，1978?1978p4q?r?8,4,2,6(mod10).这种现象在数学
上称为“模同期现象”.一般地，我们有如下定义：
整数列?xn?各项除以m（m?2，m∈N*）后的余数an组成数列?an?.若?an?是一个周期数列，则称?xn?是关于模m的周期数列，简称模m周期数列.满足an?T?an（或an?T?xn（modm））的最小正整数T称为它的周期.
例8 （第29届IMO预选题）设a是方程x?3x?1?0的最大正根，求证：17可以整除[a1788]与[a1988].其中[x]表示不超过x的最大整数.
na分析 探求????是本题的关键，而a的值无法准确计算得到。所以本题通过韦达定理寻n求了??a??的递推形式。
32证明 根据如下符号表可知，若设三根依次为????a，
2012江苏省数学竞赛《提优教程》教案：第36讲 - - 同 - 余
