高中数学竞赛——数论.doc

高中数学竞赛 数论剩余类与剩余系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,m-1叫做模m的最小非负完全剩余系.下述数组叫做模m的绝对最小完全剩余系:当m为奇数时,;当m为偶数时,或.(2)性质()m个整数构成模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),则有aai+baaj+b(modm),也矛盾!()设m1,m2是两个互质的正整数,而x,y分别遍历模m1,m2的完系,则m2x+m1y历遍模m1m2的完系.证明:因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互质的全部剩余类中，从每一类中任取一个数所做成的数组，叫做模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,则x与ax同时遍历模m的既约剩余系.证明:因(a,m)=1,(x,m)=1,所以,(ax,m)=1.若ax1ax2(modm),则有x1x2(modm),矛盾!()若a1,a2,a(m)是个与m互质的整数,并且两两对模m不同余,则a1,a2,a(m)是模m的一个既约剩余系.证明:因a1,a2,a(m)是个与m互质的整数,并且两两对模m不同余,所以,a1,a2,a(m)属于个剩余类,且每个剩余类都与m互质,故a1,a2,a(m)是模m的一个既约剩余系.()设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,则m2x+m1y历遍模m1m2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因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是两个互质的正整数,则.证明:因当x,y分别历遍模m1,m2的既约剩余系时,m2x+m1y也历遍模m1m2的既约剩余系,即m2x+m1y取遍个整数,又x取遍个整数,y取遍个整数,所以, m2x+m1y取遍个整数,故.推论2 设整数n的标准分解式为(为互异素数,),则有.证明:由推论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的数:因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(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,因(5n,2011)=1,所以,x与fn(x)同时历遍mod2011的完系,1x2011,所以,存在正整数m(1m2011)使得fn(m)0(mod2011),即2011|fn(m).例4设是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设对每个正整数,数被除的余数都各不相同.证明:在数列中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a1=0.此时对每个正整数k必有akk:若akk,则取n=ak,则a1ak0(mod n),矛盾.现在对k归纳证明a1,a2,ak适当重排后是绝对值小于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,存在x(1xp-1)使.证:充分性:因对1xp-1,( p,x)=1,所以,所以,为偶数,即必要性:因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共配成对,则有,即为奇数,与矛盾!所以,必存在x(1xp-1)使.引理2形如4k+1(kZ)的素数有无限多个.证：假设形如4k+1的素数只有n个:p1,p2,pn，则p1,p2,pn都不是a=4(p1p2pk)2+1的素因数.设q是a的一个素因数,则有(2p1 p2pk)2-1(modq),因存在1xq-1使2p1 p2pkx(mod q),即x2-1(modq),所以,由引理1知,矛盾！所以,形如4k+1的素数有无限多个.回到原题:由引理1,2知,存在无穷多个素数p,使得存在x(1xp-1)使.即p|x2+1,因px,所以, px!, x2+1x!,因这样的素数p无穷多,所以,相应的x也无穷多. 例8设f(x)是周期函数,T和1是f(x)的周期且0T1.证明:(1)若T为有理数,则存在素数p,使得是f(x)的周期;(2)若T为无理数,则存在各项均为无理数的数列an满足0an+1an1(n=1,2, ),且每个an都是f(x)的周期.证明：(1)设T=(正整数m,n互质,且n2),因(m,n)=1,所以,m,2m,nm构成modn的完系,故存在kN*使得km1(modn),即存在tN*使得km=nt+1,因f(x)=f(x+kT)=f(x+)=f(x+t+)=f(x+),所以是周期.设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(x)的周期,且0ak