高中数学竞赛-数论

高中数学竞赛数论

剩余类及剩余系

1,剩余类的定义及性质

(1)定义1设m为正整数，把全体整数按对模m的余数分成m类，相应m

个集合记为:1<0,1<1=・,1<1«・1,其中Kr={qm+r|q£Z,0/余数r<m・l}称为模m的

一个剩余类(也叫同余类)。KO,K1,…,Km・l为模m的全部剩余类.

(2)性质(i)Z=U&且KiAKj=e(iWj).

(ii)每一整数仅在Ko,Ki,-,Km-i一个里.

(iii)对任意a、bWZ,则a、beKra=b(modm).

2.剩余系的定义及性质

⑴定义2设KO,K1,…,Km・l为模m的全部剩余类，从每个Kr里任取一个ar,得

m个数削声1,…,am・l组成的数组，叫做模m的一个完全剩余系，简称完系.

特别地012…,m-1叫做模m的最小非负完全剩余系.下述数组叫做模m的绝对

最小完全剩余系:当m为奇数时+L…TO」,…,一；当m为偶数

mm,.八,m,1m,.八.m

Bj,--+--+-LOJ,.

(2)性质(i)m个整数构成模m的一完全剩余系o两两对模m不同余.

(ii)若(a,m)=l,则x及ax+b同时遍历模m的完全剩余系.

证明：即证ao,ai,…，am-i及aao+b,aai+b,…，aam-i+b同为模m的完全剩余系,

因ao,ai,…，am-i为模m的完系时，若aai+b三aaj+b(modm),则ai=aj(modm),

矛盾!反之，当aao+b,aai+b,…，aam-i+b为模m的完系口寸，若为三aj(modm),则有

aa+b三aaj+b(modm),也矛盾！

(iii)设mi,m2是两个互质的正整数，而x,y分别遍历模mi,m2的完系，则

mix+miy历遍模muru的完系.

证明：因x,y分别历遍mi,m2个整数，所以,m?x+miy历遍rmnu个整数.

假定mzx'+miy，三m2X〃+miy〃(modmim2),其中x；x"是x经历的完系中的数，而

y’；y〃是y经历的完系中的数.因(mi,m2)=l,所以,m?x=m2X^(modmi),m।y!=miyz/

(modmz),从而x三x(modmi),y三y(modmz),矛盾！

3.既约剩余系的定义及性质

(1)定义3如果剩余类Kr里的每一个数都及m互质，则Kr叫及m互

质的剩余类.在及模m互质的全部剩余类中，从每一类中任取一个数所做成的数

组，叫做模m的一个既约(简化)剩余系.如:模5的简系123,4;模12的简系

1,5,7,11.

(2)性质(i)Kr及模m互质=Kr中有一个数及m互质；

证明:设〃£Kr,(m,4)=1,则对任意b《Kr,因♦三b三r(modm),所以,(m,a)=(m,r)=

(m,b)=l,即Kr及模m互质.

(ii)及模m互质的剩余类的个数等于甲(m),即模m的一个既约剩余系

由(p(m)个整数组成(cp(m)为欧拉函数)；

(iii)若(a,m)=l,则x及ax同时遍历模m的既约剩余系.

证明:因(a,m)=1,(x,m)=1,所以，(ax,m)=1.若ax1三ax2(modm),则有

Xi三X2(modm),矛盾！

(iv)若0,42,…,〃小)是(p(m)个及m互质的整数,并且两两对模m不同余,

则…，曲(m)是模m的一个既约剩余系.

证明:因的,。2,…,外⑺是(p(m)个及m互质的整数,并且两两对模m不同余，

所以…,属于(p(m)个剩余类,且每个剩余类都及m互质，故出血・・・，的⑺

是模m的一个既约剩余系.

(v)设mi,m2是两个互质的正整数，而x,y分别历遍模mi,m2的既约剩余

系，则m2x+miy历遍模minu的既约剩余系.

证明:显然,既约剩余系是完系中所有及模互质的整数做成的.因x,y分别

历遍模rm,nu的完系时,imx+miy历遍模nnm?的完系.由(mi,x)=(m2,y)=l,

(mi,m2)=l得(m2X,mi)=(miy,m2)=l,所以，(m2x+miy,mi)=l,(m2x+miy,m2)=1,故

(m2X+m】y,mim2)=l.反之若(nux+miy,mim2)=l,则(m2X+miy,mi)=(m2X4-miy,m2)

二1,所以，(m2X,mi)=(miy,m2)=l,因(mi,m2)=l,所以，(nu,x)=(m2,y)=l.证毕.

推论1若mi,m2是两个互质的正整数，则。(“/)=9(町)。(加2).

证明:因当x,y分别历遍模mi,m2的既约剩余系时,n^x+miy也历遍模num?

的既约剩余系，即mox+imy取遍eO?"?)个整数，又x取遍。(班)个整数,y取遍

颂利2)个整数，所以，nux+miy取遍夕(叫烦和)个整数，故。(班"2)=(p(m](p(m?).

推论2设整数n的标准分解式为〃=p/…〃/《〃田••,/〃‘为互异素数,

%£N)则有例〃)=/?(1--)(1---)•••(1---).

PiPiPk

证明:由推论1得0(〃)=以〃：)0(〃2%)…夕(〃小),而。(P")=P"-P"\

(即从1到“.这片个数中，减去能被〃整除的数的个数)，所以，

。(九)=(〃:一)3%-P12~X)•••(〃/*-必41)

=72(1--)(1--

Pl〃2Pk

4.欧拉(Euler)及费尔马(Fermat)定理

欧拉(Euler淀理设m是大于1的整数则。如'〃)三i(nx)dm).

证明:设—I>(M是模m的既约剩余系，则由性质3知—,明小)也是

<p{,n}

模m的既约剩余系，所以，。口…。5⑼三口。…「伊(⑼(modm),即arxr2…叫神)三

4G…。(⑼，因(…％〃D,m尸1,所以，〃('〃)三1(modm).

推论(Fermat定理)设p为素数，则对任意整数〃都有。〃三々(modp).

证明:若(a,p)=l,由0(p)=及Euler定理得々〃一三l(modp)即

a〃三a(modp)；若(七p)W1,则p|a,显然有ap=a(modp).

例1设m>(),证明必有一个仅由()或1构成的自然数。是m的倍数.

证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm的同一剩

余类中，它们的差即为所求的a

例2证明从任意m个整数0M2,…,而中，必可选出若干个数，它们的和

(包括只一个加数)能被m整除.

证明:考虑m个数。1,。1+。2,0+。2+。3,…,0+G2+…+〃m,如果其中有一个数能被

m整除，则结论成立，否则，必有两个数属于modm的同一剩余类，这两个数的差即

满足要求.

例3设f(x)=5x+2=fi(x),fn+i(x)=f[fn(x)].求证:对任意正整数n,存在正整数m,

使得2011|fn(m).

2

证明:因f2(x)=f[f(x)]=5(5x+2)+2=5x+5X2+2,

32nn1

f3(x)=f[f2(x)]=5x+5X2+5X2+2,-,fn(x)=5x+5-X2+50乂2+・・・+2,

因(512011)=1,所以,x及fn(x)同时历遍mod2011的完系,1WxW20U,

所以，存在正整数m(lWmW2011)使得f£m)三0(mod2011),即2011|fn(m).

例4设4MM3厂是整数序列，其中有无穷多项为正整数,也有无穷多项为

负整数.假设对每个正整数〃，数人出吗，…此被〃除的余数都各不相同•证明：在

数列4gM3,•中，每个整数都刚好出现一次.

证明：数列各项同时减去一个整数不改变本题的条件和结论，故不妨设a.=0.

此时对每个正整数k必有IakIvk:若|akI2k,则取n=IakI,

则ai=ak=0(modn),矛盾.

现在对k归纳证明山22,...凡适当重排后是绝对值小于k的k个相邻整数.k=l

显然.设a处,…,ak适当重排后为-(kT-i),…,0,...,i(OWiWk-1),由于

ai,a2,...,ak,ak+i是(modk+1)的一个完全剩余系，故必ak+i三i+l(modk+1),但

Iak+iIvk+1,因此ak+i只能是i+1或-(k-i),从而a㈤,…,ak,ak+i适当重排后是绝对

值小于k+1的k+1个相邻整数.

由此得到:1).任一整数在数列中最多出现一次;2).若整数u和v(u<v)都出现在

数列中，则u及v之间的所有整数也出现在数列中.

最后由正负项均无穷多个(即数列含有任意大的正整数及任意小的负整数)

就得到:每个整数在数列中出现且只出现一次.

例5偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐

下,证明至少有两个人，他们中间的人数在休息前及休息后是相等的。

证明：将座号依顺时针次序记为1,2,…,2n,每个人休息前后的座号记为

(i,j),则i及j历遍完全剩余系mod2n0如果两个人(il,j1),(i2,j2)休息

前后在他们中间的人数不相等，则有j2-只羊i2-ilmod2n,即j2-i2壬

jl-il(mod2n),因此，j-i也历遍完全剩余系mod2n,所以，j-i的和二=

0(mod2n),而任一完全剩余系mod2n的和三1+2+…+2nT三n(2nT)学0(mod2n),

矛盾！故结论成立.

例6数列｛an｝定义为:aO=a(a£N*),an+l=an+(n£N).数列｛an｝中存在无穷

多项可被2011整除.

证明:因(40,2011)=1,所以,40—三l(n»d2011).

因当〃>0(2011)时，以201所以，数列｛斯(mod2011)｝构成模2011的完系,

且是周期数列，所以，数列｛如｝中存在无穷多项可被2011整除.

例7证明:存在无穷多个正整数n,使得n2+ltn!.

证明:弓I理1对素数p>2,p=l(mod4)<=>存在x(l)使/三-l(modp).

p-ip-i

证:充分性:因对1WxWpT,(p,x)=l,所以,x'T=(/)2=l(modp),(x2)2=

(-02三l(modp),所以,为偶数，即。三l(mod4).

必要性:因iWxWpT时,x,2x,…,(/?T)x构成modp的既约剩余系，所以，存在

1WaWp-l,使得tzx=-l(modp),若不存在〃(1WaWp-1),Q=X,使ox三-l(modp),

则这样的。,x共配成对，则有(-1)-三(〃-1)!三Tmod〃),即为奇数，及

〃=44+1矛盾!所以,必存在x(lWxWpT)使X?=-l(mod〃).

引理2形如4k+l(k£Z)的素数有无限多个.

证：假设形如4k+l的素数只有n个:pl,p2,・・・,pn,贝！Jpl,p2,—,pn都不是

。二4(p/〃2…pkp+l的素因数.

设夕是。的一个素因数，则有(2pip2…pk>三T(modq),因存在l<xWqT使

2plp2…pk三x(modq),即x2三-l(modq),所以,由引理1知，矛盾！

所以，形如4k+l的素数有无限多个.

回到原题:由引理1,2知，存在无穷多个素数p,使得存在x(lWx〈p7)使

/三-l(mod〃).即p*+l,因p>x,所以,p*x!,x?+ltx!,因这样的素数〃无穷多,所以,

相应的x也无穷多.

例8设f(x)是周期函数,T和1是f(x)的周期且()<T<1.证明:

(1)若T为有理数，则存在素数p,使得,是f(x)的周期；

P

(2)若T为无理数，则存在各项均为无理数的数列｛斯｝满足()<a田<asl

(n=l,2,…),且每个④都是f(x)的周期.

证明：(1)设T=(正整数m,n互质，且n22),因所以,m,2m,…,nm构成

modn的完系，故存在k《N”使得km三l(modn),即存在t《N使得km=nt+l,因

km]|]

f(x)=f(x+kT尸f(x+—)=f(x+t+一户f(x+一),所以一是周期.

nnnn

设n=S，其中MN*,p为素数，则是周期.故存在素数p,使:是周期.

⑵当T为无理数时，取。尸T,则T为无理数,()<T<1.设k<n时存在无理数

使得()<诙<四1<1,且诙是周期.对k+1,总存在存在u,v£N*,使得0<U6Zk_v<«k<l,

取"k+i=u〃k-v,则〃k+i是无理数且是f(x)的周期，且0<期+1<跺<1,递推知存在各

项均为无理数的数列｛小｝满足0<an+]V〃n<l(n=12…),且每个小都是f(x)的周期.

例9设正整数n22.求所有包含n个整数的集合A,使得A的任意非空子集

中所有元素的和不能被n+1整除.

解:设A=｛0血…0｝是满足条件的集合.臬=之=12…/)，依题意知，对

<=i

任意k=l,2,…,n都有n+l*Sk,且任意Sk,Sj(kWj)都有Sk美Sj(modn+1),所以,｛Sk｝包

含了modn+1的所有非零剩余，因对IWiSn,整数卬,S2S3,…,Sn也包含了mod(n+l)

的所有非零剩余，所以，所Si三〃i(modn+1),即A中任意跖三ai(modn+l).所以，对任

意1WkWn,〃1+。2+…+公三kai(modn+l).且k。岸0(modn+l),从而(。[再+1)=1.

取al=a得集合A=｛a+ki(n+l)|ki^Z,1WiWn,a£Z,且(a,n+l)=l｝为所求.

例10对任意正整数n,用S(n)表示集合｛1,2,…,n｝中所有及n互质的元素之和.

证明：2S(n)不是完全平方数；

例H求所有的奇质数p,使得.

例12求所有质数p,使得1©了+©.+…+(C俨了.

例13设n为大于1的奇数,ki,k2,…,匕是n个给定的整数，对1,2,…,n的每一

个排列a=(aba2,•••,an),记S(a)=.证明：存在两个1,2,…，n的排列b和c(bWc),

使得n!|S(b)-S(c).

证明：如果对12…,n的任意两个不同排列b和c(bWc),都有

n!裕(b)-S(c),那么当aE又遍所有排列时(共n!个)，S(a)遍历模n!的一个完系，

因此，有ZS(。)三1+2+…+n!三(modn!)①，另一方面,我们有

a

==£V，粗(〃-1)这力以三0(mod〃!)②.

aa/=1/=1ai=\j=\乙/=1

由①ZS(。)三邑(modn!)及②ZS(。)三0(modn!)(因n为奇数)矛盾!故原命题成立.

Q2Q

例14已知m,n为正整数，且m为奇数,(m,2Ll)=l.证明:m[.

证明:因1,2,•••,m构成modm的完系，(m,2)=1,所以2,4,•••,2m也构成

M川川

modm的完系，所以Z(2幻"三m)即(2”-1)2右,三0(nx)dm).

hlfc=l<=l

因(m,2J)=1,所以.得证.

例15已知x£(0,1),设y£(0,1)且对任意正整数n,y的小数点后第n位数字

是x的小数点后第2n位数字,证明:若x是有理数，则y也是有理数.

例16设A=｛0,…,劭(n)｝是模n的一个既约剩余系.如果方程x?三l(modn)

N

在A中解的个数为N,求证:小〃2…即⑺三(-1/(modn).

同余方程及同余方程组

1.同余方程(组)及其解的概念

定义1给定正整数m及n次整系数多项式/(幻=。〃无〃+。〃_，一4-+。/+。0

,则同余式f(x)三O(modm)①叫做模m的同余方程，若anO(modm),贝！］n叫做方程①的次数.

若x=a是使f(o)三O(modm)成立的一个整数,则x三〃(modm)叫做方程①的一个

解,即把剩余类a(modm)叫做①的一个解.

若Qi(modm),42(modm)均为方程①的解,且sq对模m不同余,就称它们是方

程①的不同解.由此可见,只需在模m的任一组完系中解方程①即可.

例1解方程2x2+x-l=0(mod7).

解:取mod7的完系:-3,-2,-1,0,1,2,3,直接验算知x三-3(modm)是解.

例2求方程4x2+27x-12=0(modl5).

解:取mod15的完系:-7,-6,…,T,0,1,­••,7,直接验算知x三-6,3(modm)是解.

2.一次同余方程

设则ax三b(modm),叫模m的一次同余方程.

定理1当(a,m)=l时，方程ox三b(modm)必有解，且解数为1.

证明:因当(4,m)=l时,x及ax同时遍历模m的完系，所以，有且仅有一个x使得

ax三b(modm).即x=«_,b(modm).

定理2方程ax三b(modm)有解。(o,m)|b,且有解时其解数为(a,m),及若xo是一

m

个特解，则它的3,m)个解是x三/+-——-r(modm),r=0,1,•••,(6r,/n)-1.

(a,m)

例3解方程6x三10(mod8).

解:因(6,8)=2,且T是一个特解，所以，方程6x三H)(mod8)的解为：

x=-1+4/(mod8),Z=0,1即x=-l,3(mod8).

例4解方程12x三6(mod9).

因(12,9)=3,且-1是一个特解，所以，方程12x三6(mod9)的解为：

x三一1+3r(mod8)J=0,1,2即x三-l,2,,5(mod8).

3.同余方程组

定义3给定正整数mi,ni2,…,mk和整系数多项式fi(x),f2(x),…,f“x),则同余式组

②，叫做同余方程组.若x=。是使方⑷三O(mcdnij)(l<jWk)成立的一个整数,

则x三。(modm)叫做方程组②的一个解，即把剩余类aGnodm)叫做②的一个解.其

中m=[mi,m2,—,mJ.

例5解方程组.

解:由例3知6x三10(mod8)的解是x三T,3(mod8).所以，原解方程组0

或或x三3(mod56)<=>x三31,3(mod56).

中国剩余定理:设K22,而ml,m2,…,mk是K个两两互质的正整数，令

M=m1m2,,,mk=m1M1=m2M2=,••=mkMk,则对任意整数al,a2,…,ak下列同余式

组：

③的正整数解是x三0MlM2M2M尸+…+〃kM]：Mk"(modM).

其中M『满足MjMj-1三1(modmj)(1/jWk),即Mj对模成的逆.

证明:⑴对iWjWk,因mjMi(iWj),mj|M,所以x三aMjMj三a,(modmj).

⑵设x,y都是同余式组的解，即x三，j(modmj),y三〃j(modmj)(lWjWk),

则x三y(modmj),即mj|x-y,因rm,m2,…,mk两两互质，所以M|x-yH|Jx=y(modM).

注:(1)存在无穷多个整数x满足同余方程组③,这些x属于同一模m的剩余类；

(2)同余方程组③仅有一个解x三0MlMJ+zM2M产+…+QkMkMk"(modM).

(3)当m,mi)=l(=l,2,…,n)时，同余方程组

x

ax=4(mod"])x=a~a{(mod/^)

ax=(mod/%,)x=a^a-,(mod/H0)

•・・♦......~..o...•••••••••~仍然具有定理结论.

}

QX三ak(mod/久)[x=a-ak(mod/%)

这在数论解题中具有里要应用.

例6"今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物

几何”.

解:设物数x,则有，这里mi=3,m2=5,m3=7,M=3X5X7=l()5,所以，

35X35.1三2X35.1=l(mod3)O35/三2(mod3),

21X2r1=2r'=l(mod5)«>21-1=l(mod3),

15义15-1三15/三1(111。€17)015/三1(010€13),所以,同余方程组的解为：

x=2x35x2+3x21x1+2x15x1=233=23(modl05),KPx=105k+23(kEN).

例7有兵一队，若分别列5,6,7,11行纵队，则末行人数分别为1,5,4,10.求兵数.

解:设兵数x,则淇中mi=5,m2=6,m3=7,m4=ll,M=2310,

462X462」三2X4624=l(mod5)<^>462*=3(mod5),

385X385/三385-1三l(mod6)o385」三l(mod6),

330X330「三330」三l(mod7)O330」三l(mod7),

210乂2104三21()/三l(modll)c21()yl(modll),所以,同余方程组的解为：

x三462x3+5x385+4x330+10x210=6371三211l(mod2310),

即x=2310k+2111(keN).

例8证明:对任意rr个两两互质的正整数:rm,m2,…,mn,总