高中数学竞赛——数论 14页

高中数学竞赛数论剩余类与剩余系1.剩余类的定义与性质(1)定义1设m为正整数，把全体整数按对模m的余数分成m类，相应m个集合记为：K0,K1,…,Km-1,其中Kr={qm+r|q∈Z,0≤余数r≤m-1}称为模m的一个剩余类(也叫同余类)。K0,K1,…,Km-1为模m的全部剩余类.(2)性质(ⅰ)且Ki∩Kj=φ(i≠j).(ⅱ)每一整数仅在K0,K1,…,Km-1一个里.(ⅲ)对任意a、b∈Z，则a、b∈Kra≡b(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+b≡aaj+b(modm),则ai≡aj(modm),矛盾!反之,当aa0+b,aa1+b,…,aam-1+b为模m的完系时,若ai≡aj(modm),则有aai+b≡aaj+b(modm),也矛盾!14\n(ⅲ)设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互质；证明:设a∈Kr,(m,a)=1,则对任意b∈Kr,因a≡b≡r(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.若ax1≡ax2(modm),则有x1≡x2(modm),矛盾!(ⅳ)若a1,a2,…,aφ(m)是个与m互质的整数,并且两两对模m不同余,则a1,a2,…,aφ(m)是模m的一个既约剩余系.14\n证明:因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到这个数中,减去能被整除的数的个数),所以,.14\n4.欧拉(Euler)与费尔马(Fermat)定理欧拉(Euler)定理设m是大于1的整数,(a,m)=1,则.证明:设r1,r2,…,r是模m的既约剩余系,则由性质3知ar1,ar2,…,ar也是模m的既约剩余系,所以,ar1ar2…ar≡r1r2…r(modm),即,因(,m)=1,所以,.推论(Fermat定理)设p为素数,则对任意整数a都有.证明:若(a,p)=1,由及Euler定理得即;若(a,p)≠1,则p|a,显然有.例1设m>0,证明必有一个仅由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)=f[fn(x)].求证:对任意正整数n,存在正整数m,使得2011|fn(m).证明:因f2(x)=f[f(x)]=5(5x+2)+2=52x+5×2+2,f3(x)=f[f2(x)]=53x+52×2+5×2+2,…,fn(x)=5nx+5n-1×2+5n-2×2+…+2,因(5n,2011)=1,所以,x与fn(x)同时历遍mod2011的完系,1≤x≤2011,14\n所以,存在正整数m(1≤m≤2011)使得fn(m)≡0(mod2011),即2011|fn(m).例4设是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设对每个正整数,数被除的余数都各不相同.证明:在数列中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a1=0.此时对每个正整数k必有∣ak∣2,存在x(1≤x≤p-1)使.证:充分性:因对1≤x≤p-1,(p,x)=1,所以,,,所以,为偶数,即必要性:因1≤x≤p-1时,x,2x,…,(p-1)x构成modp的既约剩余系,所以,存在1≤a≤p-1,使得ax≡-1(modp),若不存在a(1≤a≤p-1),a=x,使ax≡-1(modp),则这样的a,x共配成对,则有,即为奇数,与矛盾!所以,必存在x(1≤x≤p-1)使.引理2形如4k+1(k∈Z)的素数有无限多个.证：假设形如4k+1的素数只有n个:p1,p2,…,pn，则p1,p2,…,pn都不是a=4(p1p2…pk)2+1的素因数.设q是a的一个素因数,则有(2p1p2…pk)2≡-1(modq),因存在1≤x≤q-1使2p1p2…pk≡x(modq),即x2≡-1(modq),所以,由引理1知,矛盾！所以,形如4k+1的素数有无限多个.14\n回到原题:由引理1,2知,存在无穷多个素数p,使得存在x(1≤x≤p-1)使.即p|x2+1,因p>x,所以,p∤x!,x2+1∤x!,因这样的素数p无穷多,所以,相应的x也无穷多.例8设f(x)是周期函数,T和1是f(x)的周期且01,2得r=3).取这样的r,使得r>t且r>,令am+1=r,am+2=t,则这样得到的数列{an}满足要求.例13证明:存在一个n∈N*,使得对任意整数k,整数k2+k+n没有小于2011的质因数.例14证明:存在k∈N*,使得对任意n∈N*,数2nk+1都是合数.例15设m∈N*,n∈Z,证明:数2n可以表为两个与m互素的整数之和.14