资源描述：
《高二数学竞赛班二试讲义.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、高二数学竞赛班二试讲义第4讲同余与剩余类一、知识点金1.同余班级姓名两个整数a,b除以正整数m，若余数相同，则称a与b关于模m同余，记作ab(modm)，这叫做同余式。2.性质以下性质均在整数范围内讨论，模为正整数。（1）若acbc(modm)，则当(c,m)1时，ab(modm)；则当(c,m)d时，ab(modm)。d（2）若Aa(modm1)，Aa(modm2)，且(m1,m2)1，则Aa(modm1m2)。（3）费尔马小定理：p为素数，对任意正整数a，都有p
2、(apa)。费尔马小定理的推论：设p为素数，a为正整数，且(a,p)1，ap11
3、(modp)。证明：由于a,2a,,(p1)a模p的余数各不相同，否则，若有iaja(modp)，其中1ijp1，则p
4、(ji)a，而p不整除a，所以p
5、(ji)，这是不可能的，因此a,2a,,(p1)a模p的余数必然取遍1,2,,p1这p1个数，仅可能顺序不同。故a2a(p1)a12(p1)(modp)。又p为素数，则((p3.剩余类1)!,p)1，所以由性质（1）得ap11(modp)。设mN*，把全体整数按对模m的余数进行分类，余数为r(0rm1)的所有整数归为一类，记为kr，kr称为模m的一个剩余类(r0,1,2,,
6、m1)。显然，kr是一个以m为公差的无穷等差数集。它有如下性质：（1）Zk0k1km1，且kikj；（2）对任意nZ，有唯一的r，使得nkr。（3）对任意a,bZ，a,bkrab(modm)。4.完全剩余系设Zk0,k1,,km1是模m的全部剩余类，从每个kr任取一个数ar，这m个数a0,a1,,am1组成的一个数组称为模m的一个完全剩余系，简称完系。0,1,2,,m1称为模m的最小非负完系。二、例题分析例1．（1）求证：n是正奇数时，6n3n2n1能被60整除。（2）n是自然数，它不能被17整除，求证：n81与n81中有且只有一个数被
7、17整除。例2．a1,a2,,a11；b1,b2,,b11是1,2,3,4,,11的两种不同排列。求证：a1b1,a2b2,,a11b11中至少有两个被11除所得的余数相同。例3．设三角形的三边长分别是整数l,m,n，且lmn。已知3l1043m1043n，104其中xxx，而x表示不超过x的最大整数，求这种三角形周长的最小值。三、同步检测1．计算55个5的乘积，则其最后三位数是（）A．125B．375C．625D．8752．19962000被29除的余数是。133．求证：2730
8、(nn)(n为任意整数)。4．求证：1992
9、8282!i1in
10、)，使得m5．两个数1992m与1992n的末三位数字完全相同，试求出正整数取得最小值。m,n(mn8．偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下。求证：至少有两个人，他们之间的人数在休息前与休息后是相同的。二、例题分析第4讲同余与剩余类答案例1．（1）当n是自然数时，anbn(ab)(an1an2bbn1)，当n是正奇数时，anbn(ab)(an1an2bbn1)，由于6n类似6n3n2n3n2n1(6n1(6n3n)(2n2n)(3n1)，所以3
11、6n3n1)，所以4
12、6n3n2n1，2n16n3n2n1(
13、6n1)(3n2n)，所以5
14、6n3n2n1，因为60345，3,4,5两两互素，故60
15、6n3n2n1（2）由17是素数，n不能被17整除，则(n,17)1。由费尔马小定理，得n1711(mod17)，即n161(mod17)，则(n81)(n81)0(mod17)，故n810(mod17)或n810(mod17)但是，(n81)(n81)2不能被17整除，所以n81与n81中有且只有一个数被17整除。例2．反证法：假设a1b1,a2b2,,a11b11被11除的余数两两不同，则这些余数等于0,1,2，⋯，10这11个值，为方便起见
16、，不失一般性，可设a1b1被11除的余数为0，令ka2b2a3b3a11b11，我们用两种方法计算k被11除的余数。一方面，这个余数等于1231010!被11除的余数，10!10(mod11)另一方面，数k的任一因子都不能被11整除，数k的因子中要两次遇到1～10中每个数，也就是k(10!)21021。矛盾！故a1b1,a2b2,,a11b11中至少有两个被11除所得的余数相同。3l3l3m3m3n3n例3．由题意[][][]，于是3l3m3n(mod104)，l104104104104104104即3l3m3n(mod24)①且3
17、3m3n(mod54)②因为(3,2)1，由①可知24
18、3l3m
