1、1高二数学竞赛班二试讲义第 4 讲 同余与剩余类班级 姓名 一、知识点金1同余两个整数 除以正整数 ，若余数相同，则称 与 关于模 同余，,abmabm记作 ，这叫做同余式。(od)2性质以下性质均在整数范围内讨论，模为正整数。（1）若 ，则当 时， ；()c(,)1c(od)则当 时， 。,dodab（2）若 ， ，且 ，则 。1(mo)A2()Am12(,)12(mod)Aa（3）费尔马小定理： 为素数，对任意正整数 ，都有 。pa|()p费尔马小定理的推论：设 为素数， 为正整数，且 ，,。1(od)pa证明：由于 模 的余数各不相同，否则，若有 ，其中,2(1)a (od)iajp，则
2、 ，而 不整除 ，所以 ，这是不可能的，因此ij|pjipa|()pj模 的余数必然取遍 这 个数，仅可能顺序不同。,() ,21故 。()mod又 为素数，则 ，所以由性质（1）得 。p()!,1(mod)p3剩余类设 ，把全体整数按对模 的余数进行分类，余数为 的所有整数归*mNr0为一类，记为 ， 称为模 的一个剩余类 。rk(,2,)r显然， 是一个以 为公差的无穷等差数集。它有如下性质：r（1） ，且 ；（2）对任意 ，有唯一的 ，使得011mZijknZr。rn（3）对任意 ， 。,ab,r(od)abm4完全剩余系 设 是模 的全部剩余类，从每个 任取一个数 ，011mk rkr
3、a这 个数 组成的一个数组称为模 的一个完全剩余系，简称完系。,称为模 的最小非负完系。,2二、例题分析例 1 （1）求证： 是正奇数时， 能被 整除。n6321nn60（2） 是自然数，它不能被 整除，求证： 与 中有且只有一个数被 整除。1788172例 2 ； 是 的两种不同排列。121,a21,b,34,1求证： 中至少有两个被 除所得的余数相同。a例 3设三角形的三边长分别是整数 ，且 。已知 ，,lmnln444331010lmn其中 ，而 表示不超过 的最大整数，求这种三角形周长的最小值。xxx3三、同步检测1计算 个 的乘积，则其最后三位数是（ ）5A B C D 237562
4、58752 被 除的余数是 。0963求证： 为任意整数 。1|()n)4求证：821!9|i45两个数 与 的末三位数字完全相同，试求出正整数 ，使得192mn ,()mn取得最小值。n8偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下。求证：至少有两个人，他们之间的人数在休息前与休息后是相同的。5第 4 讲 同余与剩余类答案二、例题分析例 1 （1）当 是自然数时， ，n121()nnnabab当 是正奇数时， ，12()由于 ，所以 ，632633|6n类似 ，所以nnnn4，所以 ，1()()5|1n因为 ， 两两互素，故045,02（2）由 是素数， 不能被 整除，则
5、 。717(,17)由费尔马小定理，得 ，即 ，(modn6(od)则 ，故 或8(1)0)n8n810(mod7)n但是， 不能被 整除，8(2所以 与 中有且只有一个数被 整除。17例 2反证法：假设 被 11 除的余数两两不同，则这些余数等于1,ab0,1,2，10 这 11 个值，为方便起见，不失一般性，可设 被 11 除的余数为 0，1ab令 ，我们用两种方法计算 被 11 除的余数。23k k一方面，这个余数等于 被 11 除的余数，2310!0!(mod1)另一方面，数 的任一因子都不能被 11 整除，数 的因子中要两次遇到 110 中每个数，也就是 。矛盾！(10!)故 中至少
6、有两个被 除所得的余数相同。12,ab例 3由题意 ，于是 ，444331010llmn43(od0)lmn即 且 (od2)lmn 4(od5)lm因为 ，由可知 ，故 ，(,)1|l2|(1)l所以有 。43l注意到 ，42344),9(),1(),3od所以 ， ，nkN同理，可由推出 ，故 。41od5mn45k下面求满足 的正整数 。443()因为 ，1520()kk即 4831245 0(mod)6k则 7(1)2()55k所以 ，代入上式得 ，,tN772| )tt所以 ，所以 ，所以5|64tsks6故 ， 为正整数， 同理可证 ， 为正整数，50mns50lmr所以三角形的三
7、边分别为 ,50,nsn由 ，得 ，则()()r1213s当 时三角形周长最小，其值为 30031,srn三、同步检测2A 提示： ，显然， ，设5275(mod8)50(mod12)512m，则 ， ，所以8mk8)(od8)则 ，所以最后三位数是 。1(1)03 提示：因为 是素数，且 ，所以 ，799|629(920287121266(5)47)5令 ，则13()fn753211(),),(fnfnfnfn都是 的因式。于是由费尔马小定理可知，|,|,5|,|,|()f又 两两互素，且 ，所以 。72320 1327|()6 的质因数分解式为 ，19198记8821! 182iiM因为
8、中所含 的幂指数是23，所以2703648634231!|i又因为 中所含 的幂指数是，所以821397821!|i下面证明 。先考虑证明当 时， 。|Mij(mod83)j不妨设 ，则由 是素数得 ，因而 ，182ij38|,3|i2!|2!ji所以 ，且 ，!(mod)ij 12!0(od)i所以 模 的余数两两不同，且取遍 ，82,8!131,28从而推得 ，即2120(mod83)iM|M又 两两互素，故 ，即,3|M19|7 ，199()()mnnmn而 ，故可取324,05由 ，知5|128od25n故有 ，则 ，所以 ，(8)(od)mn()1()m4()mnkN因此 96k7又
9、 ，则 ，96(104)kk11(8)(4)0(4)(mod25)mnkkC 即 ，)25od125所以 或 （不可能）k25k所以 ，从而 ，h1()0()()()k hh由二项式定理知， 4od1hh由此 的最小值为 5，于是 ，又 ，所以 ，mn0102n8用反证法证明。将每位的号码依顺时针记为 ，每一个人对应一个二元有序整数组 。其中1,2 (,)ij为他休息前后的座号，显然，对于全体人员而言， 与 均跑遍完全剩余系,ij ij，如果两个人 休息前后人数均不相同，则(mod2)n(,),ij，11odin即 。22jj因此，对于全体人员而言， 也跑遍完全剩余系 ，ji(mod2)n因此 的和ji0(od)jn而任一完全完全剩余系 的和 矛盾，得()1210(od2)n证
