《2011年山东数学竞赛夏令营1》由会员分享，可在线阅读，更多相关《2011年山东数学竞赛夏令营1（14页珍藏版）》请在金锄头文库上搜索。
1、12011 年山东数学竞赛夏令营年山东数学竞赛夏令营 1青岛二中青岛二中 邹明邹明剩余类与剩余系剩余类与剩余系1.剩余类的定义与性质剩余类的定义与性质(1)定义定义 1 设 m 为正整数，把全体整数按对模 m 的余数分成 m 类，相应m 个集合记为：K0,K1,Km-1,其中 Kr=qm+r|qZ,0余数 rm-1称为模 m的一个剩余类剩余类(也叫同余类也叫同余类)。K0,K1,Km-1为模 m 的全部剩余类.(2)性质性质()且 KiKj=(ij).imiKZ 10()每一整数仅在 K0,K1,Km-1一个里.()对任意 a、bZ，则 a、bKrab(modm).2.剩余系的定义与性质剩余系
2、的定义与性质(1)定义定义 2 设 K0,K1,Km-1为模 m 的全部剩余类，从每个 Kr里任取一个ar，得 m 个数 a0,a1,am-1组成的数组，叫做模 m 的一个完全剩余系完全剩余系,简称完系完系.特别地特别地,0,1,2,m-1 叫做模叫做模 m 的最小非负完全剩余系的最小非负完全剩余系.下述数组叫做模叫做模 m 的绝的绝对最小完全剩余系对最小完全剩余系:当当 m 为奇数时为奇数时,;当当 m 为偶为偶21, 1 , 0 , 1, 121,21mmm数时数时,或或.12, 1 , 0 , 1, 12,2mmm2, 1 , 0 , 1, 12mm (2)性质性质()m 个整数构成模
3、m 的一完全剩余系两两对模 m 不同余.()若(a,m)=1，则 x 与 ax+b 同时遍历模 m 的完全剩余系.证明证明:即证 a0,a1,am-1与 aa0+b, aa1+b,aam-1+b 同为模 m 的完全剩余系,因 a0,a1,am-1为模 m 的完系时,若 aai+baaj+b(modm),则 aiaj(modm),矛盾!反之,当 aa0+b, aa1+b,aam-1+b 为模 m 的完系时,若 aiaj(modm),则有2aai+baaj+b(modm),也矛盾!()设 m1,m2是两个互质的正整数,而 x,y 分别遍历模 m1,m2的完系,则m2x+m1y 历遍模 m1m2的完
4、系.证明证明:因 x,y 分别历遍 m1,m2个整数,所以,m2x+m1y 历遍 m1m2个整数.假定 m2x/+m1y/m2x/+m1y/(modm1m2),其中 x/,x/是 x 经历的完系中的数,而 y/,y/是 y 经历的完系中的数.因(m1,m2)=1,所以,m2x/m2x/(modm1),m1y/m1y/(modm2),从而 x/x/(modm1),y/y/(modm2),矛盾!3.既约剩余系的定义与性质既约剩余系的定义与性质(1)定义定义 3 如果剩余类 Kr里的每一个数都与 m 互质，则 Kr叫与 m 互质的剩余类.在与模 m 互质的全部剩余类中，从每一类中任取一个数所做成的数
5、组，叫做模 m 的一个既约既约(简化简化)剩余系剩余系.如:模 5 的简系 1,2,3,4;模 12 的简系 1,5,7,11.(2)性质性质()Kr与模 m 互质Kr中有一个数与 m 互质；证明证明:设 aKr,(m,a)=1,则对任意 bKr,因 abr(modm),所以,(m,a)=(m,r)=(m,b)=1,即 Kr与模 m 互质.()与模 m 互质的剩余类的个数等于,即模 m 的一个既约剩余系)m(由个整数组成(为欧拉函数);)m()m()若(a,m)=1,则 x 与 ax 同时遍历模 m 的既约剩余系.证明证明:因(a,m)=1,(x,m)=1,所以,(ax,m)=1.若 ax1a
6、x2(modm),则有x1x2(modm),矛盾!()若 a1,a2,a(m)是个与 m 互质的整数,并且两两对模 m 不同)m(3余,则 a1,a2,a(m)是模 m 的一个既约剩余系.证明证明:因 a1,a2,a(m)是个与 m 互质的整数,并且两两对模 m 不同余,)m(所以,a1,a2,a(m)属于个剩余类,且每个剩余类都与 m 互质,故)m(a1,a2,a(m)是模 m 的一个既约剩余系.()设 m1,m2是两个互质的正整数,而 x,y 分别历遍模 m1,m2的既约剩余系,则 m2x+m1y 历遍模 m1m2的既约剩余系.证明证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因
7、 x,y 分别历遍模 m1,m2的完系时,m2x+m1y 历遍模 m1m2的完系.由(m1,x)=(m2,y)=1,(m1,m2)=1 得(m2x,m1)=(m1y,m2)=1,所以,(m2x+m1y,m1)=1,(m2x+m1y,m2)=1,故(m2x+m1y, m1m2)=1.反之若(m2x+m1y, m1m2)=1,则(m2x+m1y,m1)=(m2x+m1y,m2)=1,所以,(m2x,m1)=(m1y,m2)=1,因(m1,m2)=1,所以,(m1,x)=(m2,y)=1.证毕.推论推论 1 若 m1,m2是两个互质的正整数,则.)()()(2121mmmm证明证明:因当 x,y 分
8、别历遍模 m1,m2的既约剩余系时,m2x+m1y 也历遍模 m1m2的既约剩余系,即 m2x+m1y 取遍个整数,又 x 取遍个整数,y 取遍)(21mm)(1m个整数,所以, m2x+m1y 取遍个整数,故.)(2m)()(21mm)()()(2121mmmm推论推论 2 设整数 n 的标准分解式为(为互异素数,k kpppn21 21kpp,1),则有.* 1,Nk)11 ()11)(11 ()(21kpppnn证明证明:由推论 1 得,而,)()()()(21 21k kpppn1)(ppp(即从 1 到这个数中,减去能被整除的数的个数),所以,ppp)()()(11 221 1122
9、11kk kkppppppn4.)11 ()11)(11 (21kpppn4.欧拉欧拉(Euler)与费尔马与费尔马(Fermat)定理定理欧拉欧拉(Euler)定理定理 设设 m 是大于是大于 1 的整数的整数,(a,m)=1,则则.)(mod1)(mam证明证明:设 r1,r2,r是模 m 的既约剩余系,则由性质 3 知 ar1,ar2,ar也)(m)(m是模 m 的既约剩余系,所以, ar1ar2arr1r2r(modm),即)(m)(m)(21)( mmrrra,因(,m)=1,所以,.)(21mrrr)(21mrrr)(mod1)(mam推论推论(Fermat 定理定理) 设设 p
10、为素数为素数,则对任意整数则对任意整数 a 都有都有.)(mod paap证明证明:若(a, p)=1,由及 Euler 定理得即1)( pp)(mod11pap;若(a, p)1,则 p|a,显然有.)(mod paap)(mod paap例例 1 设 m0,证明必有一个仅由 0 或 1 构成的自然数 a 是 m 的倍数.证明证明:考虑数字全为 1 的数:因 1,11,111,1111,中必有两个在 modm 的同一剩余类中,它们的差即为所求的 a.例例 2 证明从任意 m 个整数 a1,a2,am中,必可选出若干个数,它们的和(包括只一个加数)能被 m 整除.证明证明:考虑 m 个数 a1
11、,a1+a2,a1+a2+a3,a1+a2+am,如果其中有一个数能被m 整除,则结论成立,否则,必有两个数属于 modm 的同一剩余类,这两个数的差即满足要求.例例 3 设 f(x)=5x+2=f1(x), fn+1(x)=ffn(x).求证:对任意正整数 n,存在正整数 m,使得 2011|fn(m).证明证明:因 f2(x)=ff(x)=5(5x+2)+2=52x+52+2, f3(x)=ff2(x)=53x+522+52+2, fn(x)=5nx+5n-12+5n-22+2,5因(5n,2011)=1,所以,x 与 fn(x)同时历遍 mod2011 的完系,1x2011,所以,存在正
12、整数 m(1m2011)使得 fn(m)0(mod2011),即 2011|fn(m).例例 4 设是整数序列,其中有无穷多项为正整数,也有无穷多项为123,a a a 负整数.假设对每个正整数 ,数被 除的余数都各不相同.证明:在n123,na a aan数列中,每个整数都刚好出现一次.123,a a a 证明证明: :数列各项同时减去一个整数不改变本题的条件和结论,故不妨设 a1=0.此时对每个正整数 k 必有ak2,存在 x(1xp-1)使)4(mod1p.)(mod12px证证:充分性:因对 1xp-1,( p,x)=1,所以,)(mod1)(21 21pxxp p 21 2)(p x
13、,所以,为偶数,即)(mod1) 1(21 pp 21p).4(mod1p必要性:因 1xp-1 时,x,2x,(p-1)x 构成 modp 的既约剩余系,所以,存在1ap-1,使得 ax-1(mod p),若不存在 a(1ap-1), a=x,使 ax-1(mod p),则这样的 a,x 共配成对,则有,即为奇数,与21p)(mod1)!1() 1(21 ppp 21p矛盾!所以,必存在 x(1xp-1)使.14 kp)(mod12px引理引理 2 形如 4k+1(kZ)的素数有无限多个.证证：假设形如 4k+1 的素数只有 n 个:p1,p2,pn，则 p1,p2,pn都不是a=4(p1p
14、2pk)2+1 的素因数.设 q 是 a 的一个素因数,则有(2p1 p2pk)2-1(modq),因存在 1xq-1 使72p1 p2pkx(mod q),即 x2-1(modq),所以,由引理 1 知,矛盾！14 kq所以,形如 4k+1 的素数有无限多个.回到原题:由引理 1,2 知,存在无穷多个素数 p,使得存在 x(1xp-1)使.即 p|x2+1,因 px,所以, px!, x2+1x!,因这样的素数 p 无穷多,所以,相)(mod12px应的 x 也无穷多.例例 8 设 f(x)是周期函数,T 和 1 是 f(x)的周期且 01,2 得 r=3). )2(mod0) 1(mod0 mtrSmrS )3(mod0)2(mod011 trara取这样的 r,使得 rt 且 r,令 am+1=r, am+2=t,则这样得到的数,max21maaa列an满足要求.例例 13 证明:存在一个 nN*,使得对任意整数 k,整数 k2+k+n 没有小于 2011 的质因数.例例 14 证明:存在 kN*, 使得对任意 nN*,数 2nk+1 都是合数.例例 15 设 mN*,nZ,证明:数 2n 可以表为两个与 m 互素的整数之和.
