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

高中数学竞赛 数论
剩余类与剩余系
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),也矛盾!
(ⅲ)设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的一个既约剩余系.
证明:因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的既约剩余系,所以, 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,
所以,存在正整数m(1≤m≤2011)使得fn(m)≡0(mod2011),即2011|fn(m).
例4设是整数序列,其中有无穷多项为正整数,也有无穷多项为
负整数.假设对每个正整数,数被除的余数都各不相同.证明:在数列中,每个整数都刚好出现一次.
证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a1=0.此时对每个正整数k必有∣ak∣<k:若∣ak∣≥k,则取n=∣ak∣,
则a1≡ak≡0(mod n),矛盾.
现在对k归纳证明a1,a2,…,ak适当重排后是绝对值小于k的k个相邻整数.k=1显然.设a1,a2,…,ak适当重排后为-(k-1-i),…,0,…,i (0≤i≤k-1),由于
a1,a2,…,ak,ak+1是(mod k+1)的一个完全剩余系,故必ak+1≡i+1(mod k+1), 但
∣ak+1∣<k+1,因此ak+1只能是i+1或-(k-i),从而a1,a2,…,ak,ak+1适当重排后是绝对值小于k+1的k+1个相邻整数.
    由此得到:1).任一整数在数列中最多出现一次;2).若整数u和v (u<v) 都出现在数列中,则u与v之间的所有整数也出现在数列中.
     最后由正负项均无穷多个（即数列含有任意大的正整数及任意小的负整数）就得到:每个整数在数列中出现且只出现一次.
例5偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下,证明至少有两个人，他们中间的人数在休息前与休息后是相等的。
证明：将座号依顺时针次序记为1,2,…,2n，每个人休息前后的座号记为
(i,j)，则i与j历遍完全剩余系mod2n。如果两个人(i1,j1),(i2,j2)休息前后在他们中间的人数不相等，则有j2-j1≢i2-i1mod2n，即j2-i2≢j1-i1(mod2n)，因此，j-i也历遍完全剩余系mod2n,所以,j-i的和=≡0(mod2n)，而任一完全剩余系mod2n的和≡1+2+…+2n-1≡n(2n-1)≢0(mod2n),矛盾！故结论成立.
例6数列{an}定义为: a0=a(a∈N*)，an+1=an+(n∈N).数列{an}中存在无穷多项可被2011整除.
证明:因(40,2011)=1,所以,.
因当时,,所以,数列{an(mod2011)}构成模2011的完系,且是周期数列,所以, 数列{an}中存在无穷多项可被2011整除.
例7证明:存在无穷多个正整数n,使得n2+1∤n!.
证明:引理1对素数p>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(mod p),若不存在a(1≤a≤p-1), a=x,使ax≡-1(mod p),
则这样的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的一个素因数,则有(2p1 p2…pk)2≡-1(modq),因存在1≤x≤q-1使
2p1 p2…pk≡x(mod q),即x2≡-1(modq),所以,由引理1知,矛盾！
所以,形如4k+1的素数有无限多个.
回到原题:由引理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)的周期且0<T<1.证明:
(1)若T为有理数,则存在素数p,使得是f(x)的周期;
(2)若T为无理数,则存在各项均为无理数的数列{an}满足0<an+1<an<1
(n=1,2, …),且每个an都是f(x)的周期.
证明：(1)设T=(正整数m,n互质,且n≥2),因(m,n)=1,所以,m,2m,…,nm构成
modn的完系,故存在k∈N*使得km≡1(modn),即存在t∈N*使得km=nt+1,因
f(x)=f(x+kT)=f(x+)=f(x+t+)=f(x+),所以是周期.
设n=kp,其中k∈N*, p为素数,则是周期.故存在素数p,使是周期.
(2)当T为无理数时,取a1=T,则T为无理数, 0<T<1.设k≤n时存在无理数
ak,使得0<ak<ak-1<1,且ak是周期.对k+1,总存在存在u,v∈N*,使得0<uak-v<ak<1,
取ak+1=uak-v,则ak+1是无理数且是f(x)的周期,且0<ak+1<ak<1,递推知存在各项均为无理数的数列{an}满足0<an+1<an<1(n=1,2,…),且每个an都是f(x)的周期.
例9设正整数n≥2.求所有包含n个整数的集合A,使得A的任意非空子集中所有元素的和不能被n+1整除.
解:设A={a1,a2,…,an}是满足条件的集合.,依题意知,对
任意k=1,2,…,n都有n+1∤Sk,且任意Sk, Sj(k≠j)都有Sk≢Sj(modn+1),所以,{Sk}包含了modn+1的所有非零剩余,因对1≤i≤n,整数ai,S2,S3,…,Sn也包含了mod(n+1)的所有非零剩余,所以, a1=S1≡ai(modn+1),即A中任意ai≡a1(modn+1).所以,对任意1≤k≤n, a1+a2+…+ak≡ka1(modn+1).且ka1≢0(modn+1),从而(a1,n+1)=1.
取a1=a得集合A={a+ki(n+1)|ki∈Z, 1≤i≤n,a∈Z,且(a,n+1)=1}为所求.
例10对任意正整数n,用S(n)表示集合{1,2,…,n}中所有与n互质的元素之和.
证明: 2S(n)不是完全平方数;
例11求所有的奇质数p,使得.
例12求所有质数p,使得.
例13设n为大于1的奇数,k1,k2,…,kn是n个给定的整数,对1,2,…,n的每一个排列a=(a1,a2,…,an),记S(a)=.证明:存在两个1,2,…,n的排列b和c(b≠c),使得n!|S(b)-S(c).
证明:如果对1,2,…,n的任意两个不同排列b和c(b≠c),都有
n!∤S(b)-S(c),那么当a取遍所有排列时(共n!个),S(a)遍历模n!的一个完系,
因此,有≡1+2+…+n!≡(modn!) ①, 另一方面,我们有
= ②.
由①≡(modn!)与②≡0(modn!)(因n为奇数)矛盾!故原命题成立.
例14已知m,n为正整数,且m为奇数,(m,2n-1)=1.证明:m|.
证明:因1,2,…,m构成modm的完系,(m,2)=1,所以2,4,…,2m也构成
modm的完系,所以即.
因(m,2n-1)=1,所以.得证.
例15已知x∈(0,1),设y∈(0,1)且对任意正整数n，y的小数点后第n位数字是x的小数点后第2n位数字.证明:若x是有理数,则y也是有理数.
例16设A={a1,a2,…,aφ(n)}是模n的一个既约剩余系.如果方程x2≡1(modn)在A中解的个数为N,求证: a1a2…aφ(n)≡(modn).

同余方程与同余方程组
1.同余方程(组)及其解的概念
定义1 给定正整数m及n次整系数多项式
，则同余式f(x)≡0(modm)①叫做模m的同余方程,若an 0(modm),则n叫做方程①的次数.
若x=a是使f(a)≡0(modm)成立的一个整数,则x≡a(modm)叫做方程①的一个解,即把剩余类a(modm)叫做①的一个解.
若a1(modm),a2(modm)均为方程①的解,且a1,a2对模m不同余,就称它们是方程①的不同解.由此可见,只需在模m的任一组完系中解方程①即可.
例1解方程2x2+x-1≡0(mod7).
解:取mod7的完系:-3, -2,-1,0,1,2,3,直接验算知x≡-3(modm)是解.
例2求方程4x2+27x-12≡0(mod15).
解:取mod15的完系:-7, -6,…,-1,0,1,…,7,直接验算知x≡-6,3(modm)是解.
2.一次同余方程
设m∤a,则ax≡b(modm),叫模m的一次同余方程.
定理1当(a,m)=1时,方程ax≡b(modm)必有解,且解数为1.
证明:因当(a,m)=1时,x与ax同时遍历模m的完系,所以,有且仅有一个x使得
ax≡b(modm).即x≡a-1b(modm).
定理2方程ax≡b(modm)有解(a,m)|b,且有解时其解数为(a,m),及若x0是一个特解,则它的(a,m)个解是.
例3解方程6x≡10(mod8).
解:因(6,8)=2,且-1是一个特解,所以,方程6x≡10(mod8)的解为:
即.
例4解方程12x≡6(mod9).
因(12,9)=3,且-1是一个特解,所以,方程12x≡6(mod9)的解为:
即.
3.同余方程组
定义3给定正整数m1,m2,…,mk和整系数多项式f1(x),f2(x),…,fk(x),则同余式组
②,叫做同余方程组.若x=a是使fj(a)≡0(modmj)(1≤j≤k)成立的一个整数,则x≡a(modm)叫做方程组②的一个解,即把剩余类a(modm)叫做②的一个解.其中m=[m1,m2,…,mk].
例5解方程组.
解:由例3知6x≡10(mod8)的解是.所以,原解方程组
或或.
中国剩余定理:设K≥2,而m1,m2,…,mk是K个两两互质的正整数，令
M=m1m2…mk=m1M1=m2M2=…=mkMk，则对任意整数a1,a2,…,ak下列同余式组：
③的正整数解是x≡a1M1M1-1+a2M2M2-1+…+akMkMk-1(modM).
其中Mj-1满足MjMj-1≡1(modmj)(1≤j≤k),即Mj对模mj的逆.
证明:(1)对1≤j≤k,因mj|Mi(i≠j) ,mj|M,所以x≡ajMjMj-1≡aj(modmj).
(2)设x,y都是同余式组的解,即x≡aj(modmj),y≡aj(modmj)(1≤j≤k),
则x≡y(modmj),即mj|x-y,因m1,m2,…,mk两两互质,所以M| x-y即x≡y(modM).
注:(1)存在无穷多个整数x满足同余方程组③,这些x属于同一模m的剩余类;
(2)同余方程组③仅有一个解x≡a1M1M1-1+a2M2M2-1+…+akMkMk-1(modM).
(3)当(a,mi)=1(=1,2,…,n)时,同余方程组
仍然具有定理结论.
这在数论解题中具有重要应用.
例6“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何”.
解:设物数x,则有,这里m1=3,m2=5,m3=7,M=3×5×7=105,所以,
35×35-1≡2×35-1≡1(mod3)35-1≡2(mod3),
21×21-1≡21-1≡1(mod5)21-1≡1(mod3),
15×15-1≡15-1≡1(mod7)15-1≡1(mod3),所以,同余方程组的解为:
,即x=105k+23(k∈N).
例7有兵一队,若分别列5,6,7,11行纵队,则末行人数分别为1,5,4,10.求兵数.
解:设兵数x,则,其中m1=5,m2=6,m3=7,m4=11,M=2310,
462×462-1≡2×462-1≡1(mod5)462-1≡3(mod5),
385×385-1≡385-1≡1(mod6)385-1≡1(mod6),
330×330-1≡330-1≡1(mod7)330-1≡1(mod7),
210×210-1≡210-1≡1(mod11)210-1≡1(mod11),所以,同余方程组的解为:
,
即x=2310k+2111(k∈N).
例8证明:对任意n个两两互质的正整数:m1,m2,…,mn,总存在n个连续的自然数k+1,k+2,…,k+n使得mi|k+i(i=1,2,…,n).
证明:由剩余定理知,总存在整数k使得,即存在连续的自然数k+1,k+2,…,k+n使得mi|k+i(i=1,2,…,n).
例9证明:对任意n∈N*,存在n个连续正整数它们中每一个数都不是素数的幂(当然也不是素数).
证明:因都不是素数的幂时,只能是素数之积.对任意n∈N*,取两组不同的素
数p1,p2,…,pn与q1,q2,…,qn,则由剩余定理知存在m∈N*,使得
同时成立.于是,n个连续正整数m+1, m+2,…,m+n中,每一个数都有两个不同的素因子.故结论成立.
例10证明:存在一个含有N(≥2)个正整数的集合A,使得A中任意两个数都互质,且A中任意k(k≥2)个数的和都是合数.
例11证明:存在一个由正整数组成的递增数列{an},使得对任意k∈N*,数列
{k+an}中都至多有有限项为素数.
证明:用p1,p2,p3,…表示所有素数从小到大的排列.令a1=2,a2为适合
且大于a1的最小正整数a2=8,取a3适合且大于a2的最小正整数a2=38.假定a1,a2,…,an都已确定,则取an+1适合且大于an的最小正整数,由剩余定理知满足条件的an+1存在.则上述递推关系定义的数列{an}满足题意:因对任意k∈N*,当n≥k+1时,都有k+an≡0(modpk+1),
由{an}递增可知{k+an}从第k+2项起每一项都是pk+1的倍数,且都大于pk+1,所以,
数列{k+an}中至多有k+1项为素数.
例12是否存在一个由正整数组成的数列，使得每个正整数都恰在该数列中出现一次，且对任意正整数k，该数列的前k项之和是k的倍数？
解:取a1=1,假设a1,a2,…,am都已确定,令t为不在a1,a2,…,am中出现的最小正整数, S=a1+a2+…+am.由剩余定理知存在无穷多个r∈N*,使得
成立.(如a1=1,取t=2,适合且r>1,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 / 14