资源描述:
《高二数学竞赛班二试讲义.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