《高中数学竞赛——数论》由会员分享，可在线阅读，更多相关《高中数学竞赛——数论（14页珍藏版）》请在金锄头文库上搜索。
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).()每一整数仅在K0,K1,Km-1一个里.()对任意a、bZ，则a、bKrab(modm).2.剩余系的定义与性质(1)定义2 设K0,K1,Km-1为模m的全部剩余类，从每个Kr里任取一个ar，得m个数a0,a1,am-1组成的数组，叫做模m的一个完全剩余系,简称完系.特别地,0,1,
2、2,m-1叫做模m的最小非负完全剩余系.下述数组叫做模m的绝对最小完全剩余系:当m为奇数时,;当m为偶数时,或.(2)性质()m个整数构成模m的一完全剩余系两两对模m不同余.()假设(a,m)=1，则*与a*+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),则有aai+baaj+b(modm),也矛盾!()设m1,m2是两个互质
3、的正整数,而*,y分别遍历模m1,m2的完系,则m2*+m1y历遍模m1m2的完系.证明:因*,y分别历遍m1,m2个整数,所以,m2*+m1y历遍m1m2个整数.假定m2*/+m1y/m2*/+m1y/(modm1m2),其中*/,*/是*经历的完系中的数,而y/,y/是y经历的完系中的数.因(m1,m2)=1,所以,m2*/m2*/(modm1),m1y/m1y/(modm2),从而*/*/(modm1),y/y/(modm2),矛盾!3.既约剩余系的定义与性质 (1)定义3如果剩余类Kr里的每一个数都与m互质，则Kr叫与m互质的剩余类.在与模m互质的全部剩余类中，从每一类中任取一个数所做
4、成的数组，叫做模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的一个既约剩余系由个整数组成(为欧拉函数);()假设(a,m)=1,则*与a*同时遍历模m的既约剩余系.证明:因(a,m)=1,(*,m)=1,所以,(a*,m)=1.假设a*1a*2(modm),则有*1*2(modm),矛盾!()假设a1,a2,a(m)是个与m互质
5、的整数,并且两两对模m不同余,则a1,a2,a(m)是模m的一个既约剩余系.证明:因a1,a2,a(m)是个与m互质的整数,并且两两对模m不同余,所以,a1,a2,a(m)属于个剩余类,且每个剩余类都与m互质,故a1,a2,a(m)是模m的一个既约剩余系.()设m1,m2是两个互质的正整数,而*,y分别历遍模m1,m2的既约剩余系,则m2*+m1y历遍模m1m2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因*,y分别历遍模m1,m2的完系时,m2*+m1y历遍模m1m2的完系.由(m1,*)=(m2,y)=1,(m1,m2)=1得(m2*,m1)=(m1y,m2)=1
6、,所以,(m2*+m1y,m1)=1,(m2*+m1y,m2)=1,故(m2*+m1y, m1m2)=1.反之假设(m2*+m1y, m1m2)=1,则(m2*+m1y,m1)=(m2*+m1y,m2)=1,所以,(m2*,m1)=(m1y,m2)=1,因(m1,m2)=1,所以,(m1,*)=(m2,y)=1.证毕.推论1假设m1,m2是两个互质的正整数,则.证明:因当*,y分别历遍模m1,m2的既约剩余系时,m2*+m1y也历遍模m1m2的既约剩余系,即m2*+m1y取遍个整数,又*取遍个整数,y取遍个整数,所以, m2*+m1y取遍个整数,故.推论2 设整数n的标准分解式为(为互异素数,
7、),则有.证明:由推论1得,而,(即从1到这个数中,减去能被整除的数的个数),所以,.4.欧拉(Euler)与费尔马(Fermat)定理欧拉(Euler)定理 设m是大于1的整数,(a,m)=1,则.证明:设r1,r2,r是模m的既约剩余系,则由性质3知ar1,ar2,ar也是模m的既约剩余系,所以, ar1ar2arr1r2r(modm),即,因(,m)=1,所以,.推论(Fermat定理) 设p为素数,则对任意整数a都有.证明:假设(a, p)=1,由及Euler定理得即;假设(a, p)1,则p|a,显然有.例1设m0,证明必有一个仅由0或1构成的自然数a是m的倍数.证明:考虑数字全为1
8、的数:因1,11,111,1111,中必有两个在modm的同一剩余类中,它们的差即为所求的a.例2证明从任意m个整数a1,a2,am中,必可选出假设干个数,它们的和(包括只一个加数)能被m整除.证明:考虑m个数a1,a1+a2,a1+a2+a3,a1+a2+am,如果其中有一个数能被m整除,则结论成立,否则,必有两个数属于modm的同一剩余类,这两个数的差即满足要求.例3设f(*)=5*+2=f1(*), fn+1(*)=ffn(*).求证:对任意正整数n,存在正整数m,使得2011|fn(m).证明:因f2(*)=ff(*)=5(5*+2)+2=52*+52+2, f3(*)=ff2(*)=
9、53*+522+52+2, fn(*)=5n*+5n-12+5n-22+2,因(5n,2011)=1,所以,*与fn(*)同时历遍mod2011的完系,1*2011,所以,存在正整数m(1m2011)使得fn(m)0(mod2011),即2011|fn(m).例4设是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设对每个正整数,数被除的余数都各不一样.证明:在数列中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不改变此题的条件和结论,故不妨设a1=0.此时对每个正整数k必有akk:假设akk,则取n=ak,则a1ak0(mod n),矛盾.现在对k归纳证明a1,a2,ak
10、适当重排后是绝对值小于k的k个相邻整数.k=1显然.设a1,a2,ak适当重排后为-(k-1-i),0,i (0ik-1),由于a1,a2,ak,ak+1是(mod k+1)的一个完全剩余系,故必ak+1i+1(mod k+1),但ak+1k+1,因此ak+1只能是i+1或-(k-i),从而a1,a2,ak,ak+1适当重排后是绝对值小于k+1的k+1个相邻整数.由此得到:1).任一整数在数列中最多出现一次;2).假设整数u和v (u2,存在*(1*p-1)使.证:充分性:因对1*p-1,( p,*)=1,所以,所以,为偶数,即必要性:因1*p-1时,*,2*,(p-1)*构成modp的既约剩
11、余系,所以,存在1ap-1,使得a*-1(mod p),假设不存在a(1ap-1), a=*,使a*-1(mod p),则这样的a,*共配成对,则有,即为奇数,与矛盾!所以,必存在*(1*p-1)使.引理2形如4k+1(kZ)的素数有无限多个.证：假设形如4k+1的素数只有n个:p1,p2,pn，则p1,p2,pn都不是a=4(p1p2pk)2+1的素因数.设q是a的一个素因数,则有(2p1p2pk)2-1(modq),因存在1*q-1使2p1p2pk*(mod q),即*2-1(modq),所以,由引理1知,矛盾！所以,形如4k+1的素数有无限多个.回到原题:由引理1,2知,存在无穷多个素数
12、p,使得存在*(1*p-1)使.即p|*2+1,因p*,所以, p*!, *2+1*!,因这样的素数p无穷多,所以,相应的*也无穷多.例8设f(*)是周期函数,T和1是f(*)的周期且0T1.证明:(1)假设T为有理数,则存在素数p,使得是f(*)的周期;(2)假设T为无理数,则存在各项均为无理数的数列an满足0an+1an1(n=1,2, ),且每个an都是f(*)的周期.证明：(1)设T=(正整数m,n互质,且n2),因(m,n)=1,所以,m,2m,nm构成modn的完系,故存在kN*使得km1(modn),即存在tN*使得km=nt+1,因f(*)=f(*+kT)=f(*+)=f(*+
13、t+)=f(*+),所以是周期.设n=kp,其中kN*, p为素数,则是周期.故存在素数p,使是周期.(2)当T为无理数时,取a1=T,则T为无理数, 0T1.设kn时存在无理数ak,使得0akak-11,且ak是周期.对k+1,总存在存在u,vN*,使得0uak-vak1,取ak+1=uak-v,则ak+1是无理数且是f(*)的周期,且0ak+1ak1,递推知存在各项均为无理数的数列an满足0an+1an1(n=1,2,),且每个an都是f(*)的周期.例9设正整数n2.求所有包含n个整数的集合A,使得A的任意非空子集中所有元素的和不能被n+1整除.解:设A=a1,a2,an是满足条件的集合.,依题意知,对任意k=1,2,n都有n+1Sk,且任意Sk, Sj(kj)都有SkSj(modn+1),所以,Sk包含了modn+1的所有非零剩余,因对1in,整数ai,S2,S3,
