高中数学竞赛专题讲座专题训练同余部分的例题与习题.docx
《高中数学竞赛专题讲座专题训练同余部分的例题与习题.docx》由会员分享，可在线阅读，更多相关《高中数学竞赛专题讲座专题训练同余部分的例题与习题.docx（63页珍藏版）》请在冰点文库上搜索。
高中数学竞赛专题讲座专题训练同余部分的例题与习题
v1.0可编写可改正
同余的见解与应用
见解与性质
1.定义：
若整数a,b被整数m（m≥1）除的余数同样,则称a同余于b模m,或a,b对模m同余.记为a≡b（modm）.
余数r:
0≤r<1.
2.性质：
（ⅰ）a≡b（modm）m|a-b,即a=b+mk,k∈Z.
（ⅱ）若a≡b（modm）,b≡c（modm）,则a≡c（modm）.
（ⅲ）若a1≡b1（modm）,a2≡b2（modm），则a1±a2≡b1±b2（modm）,a1a2≡b1b2（modm）;
nn
n-1
x
n-1
10
n
n
n-1
x
n-1
10
是两个整系数多项式
i
≡
（ⅳ）设f（x）=ax+a
++ax+a,g（x）=b
x+b
++bx+b
知足a
b（modm）（0≤i≤n）.若a≡b（modm）,则
f（a）≡f（b）（modm）.（ⅴ）ac≡bc（modm）a≡b（mod
m
）,
i
（c,m）
（ⅵ）若m≥1,（a,m）=1,
则存在整数
c使得ac≡1（modm）.称c为a对模m的逆或倒数,记为c=a-1（modm）;
a
b（modm1）
ab（mod[m1,m2]）;（ⅷ）若a≡b（modm1）,a≡b（modm2）,且（m1,m2）=
（ⅶ）
同时建立
a
b（modm2）
1,则a≡b（modm1m2）.
3.节余类：
设m为正整数，把全体整数按对模m的余数分红m类，相应m个会合记为：
K0,K1,,Km-1,此中
Kr={qm+r|q∈Z,0≤余数r≤m-1}称为模m的一个节余类。
性质：
（ⅰ）Z
Ki且Ki∩Kj=φ（i≠j）.
0i
m1
（ⅱ）每一整数仅在
K,K,,K
m-1
一个里.
01
（ⅲ）对随意a、b∈Z，则a、b∈Kra≡b（modm）.
4.
完满节余系：
设K0,K1,,Km-1为模m的所有节余类，从每个Kr里任取一个ar，得m个数a0,a1,,am-1组
成的数组，叫做模
m的一个完满节余系。
0,1,2,
m-1叫做模m的最小非负完满节余系
。
性质：
（ⅰ）m个整数组成模
m的一完满节余系
两两对模m不同样余。
（ⅱ）若（a,m）=1，则x与ax+b同时跑遍模
m的完满节余系。
5.
既约节余系：
假如Kr里的每一个数都与
m互质，则Kr叫与m互质的节余类，在与模
m互质的所有节余
类中，从每一类任取一个数所做成的数组，叫做模
m的一个既约节余系。
性质：
（ⅰ）Kr与模m互质
Kr中有一个数与
m互质；
（ⅱ）与模m互质的节余类的个数等于（m）;
11
p
n
v1.0可编写可改正
（ⅲ）若（a,m）=1,则x与ax+b同时跑遍模m的既约节余系。
（ⅳ）设（a,p）=1,
0
d
1,a,,a
do-1
o
=
则d是a关于模p的阶
ao≡1（modp）,且
对模p两两不同样余.特别地,d
Φ（p）
1,a,,a
Φ（p）-1组成模p的一个既约节余系.
例1.
设x
∈{-1,1},i=1,2,,101,证明:
x
+2x++100x
101
≠0.
i
1
2
证明:
∵x1+2x2++100x101≡1+2++101≡51≡1（mod2）∴建立.
例2.
设p为质数.求证:
Cnp
n
（modp）.
p
证明:
∵n≡0,1,2,,p-1（modp）∴
必有某
一个i（0
≤i≤p-1）使得
n≡i（modp）,从而
n
n
i
p
p
.∴n（n-
1）（n-i+1）（n-i-
1）（n-p+1）≡i（i
-1）1（p-1）（i+1）
≡（p-1）!
（modp）
，
∴（p-1）!
Cnp=（p-1）!
n（n-1）（n-i+1）（n-i-
1）（n-p+1）
n
i
≡（p-1）!
n
i
（modp）,
即
（p-1）!
Cnp
≡（p-1）!
ni
（modp）,因
p!
p
p
（（p-
1）!
p）=1
∴Cnp
ni
n
（modp）
p
p
nin（modp）.
pp
例3.设m>0,证明必有一个仅由0或1组成的自然数a是m的倍数.
证明：
考虑数字全为1的数:
1,11,111,1111,中必有两个在modm的同一节余类中,它们的差即为所
求的a.
例4.证明从随意m个整数a1,a2,,am中,必可选出若干个数,它们的和（包含只一个加数）能被m整除.
证明：
考虑m个数a1,a1+a2,a1+a2+a3,,a1+a2++am,假如此中有一个数能被m整除,则结论建立,不然,
必有两个数属于modm的同一节余类,这两个数的差即知足要求.
例5.证明数11,111,1111,中无平方数.
证明：
因随意整数n2≡0或1（mod4）,而11≡111≡1111≡≡3（mod4）,所以,数11,111,1111,中无
平方数.
例6.确立n5=1335+1105+845+275.
22
v1.0可编写可改正
5
5
5
5
5
n
个位数字为4,明显n
的首位数字为
1,进一步估
解：
因n≡3+0+4+7
≡3+4+7≡4（mod10）,所以
计
5
5
+（84+27）
5
5
5
5
5
5
133<167,所以n
可取134,144,154,164,又
:
n
<2×133
<3×133
<
133,所以,n<
4
4
5
5
5
≡3（mod3）,故n=144.
n≡1+（-1）
注：
欧拉猜想
4个自然数的
5次方之和不是
5次方,于1962
年被三位美国数学家颠覆
例6就是他们举的
反例.
例7.
求32006的个位数及末两位数字.
解
：
（1）
即
求
a（0≤a≤9）,
使
得
2006
≡a（mod10）.∵3
2
≡9≡-1（mod10）,
4
2006
2004+2
4X501+2
3
∴3≡1（mod10）,3
≡3
≡3≡
32（mod10）,故
32006的个位数是
9;
（2）
即求
b（0≤b≤99）,使得
32006≡b（mod100）.注意到:
4
X25=100且
（4,25）=1,3
4
≡81≡1（mod5）,∵3
4
≡81≡6（mod25）,3
8
12
16
≡-54≡-4
≡36≡11（mod25）,∴3≡66≡-9（mod25）,3
20
2
20
②,由
①,②得
（mod25）∴3≡-24≡1（mod25）
①;∵3≡1（mod4）∴3≡1（mod4）
20
2006
3
≡1（mod100）,∴3≡
320X100
?
3
6≡29（mod100）,故
32006的末两位数字是29.
例8.求1X3X5X7XX2005的末3位数字.
解：
注意到:
8X125=1000且（8,125）=1，∵（2n-3）（2n-1）（2n+1）（2n+3）≡（4n2-9）（4n2-1）≡1（mod8），及
M=
1X3X5X7XX2005=125m是1003个奇数之积，∴M≡1X3X5≡7（mod8）,125m≡5m≡7（mod8），∴m≡
3（mod8），∴M≡125m≡125X3≡375（mod8），∴M≡125m≡375（mod8）.即1X3X5X7XX2005的末3位数字
为375.
例9.
求大于5的素数平方被
30除的余数.
解：
设p是大于5的素数,且p≡r（mod30）（r<30）
，∵（p,30）=1∴（r,30）=1,r=1,7,11,
13,17,19,23,29，
2
∵1≡
112≡192≡292≡1（mod30）,72≡132≡172≡232≡19（mod30），∴p2≡1或19（mod30）
例10.设n,k为正整数,求证:
存在无量多个形如n?
2k-7
的平方数.
2
k
）建立的整数m.当k=1,2,3
时,取m=1+4r（r
为正奇数）,
2
k
）.
解：
即求使得m+7≡0（mod2
则有m+7≡0（mod2
2
k
）,明显m为奇数,关于k+1，∵（m+a?
2
k-1
2
2
k
≡
设对k（≥3）有整数m使得m+7≡0（mod2
）
+7≡m+7+ma?
2
33
v1.0可编写可改正
k
k+1
）,此中b=
m2
7
+
同奇偶,则有（m+a?
2
k-1
）
2
+7≡0（mod2
k+1
2（am+b）（mod2
2k
∈Z,取正整数a,b
），∴对随意正
整数k存在无量多个整数
2
k
m使得m+7≡0（mod2）.
例11.
设对随意正整数n≥1,b
的质因数都大于
n.证明：
n!
|a（a+b）（a+2b）（a+3b）
[a+（n
-1）b]
证
明
：
∵b
的
质
因数
都大
于
n，∴（b,n!
）=1∴bb-1≡1（modn!
）
，
∴（b-1）na（a+b）（a+2b）（a+3b）
[a+（n
-1）b]≡
（ab-1）（ab-1+1）（ab-1+2）（ab-1+3）[ab-1+（n-1）]≡0（modn!
）
，
∵（b-1,n!
）=1
，
∴n!
|a（a+b）（a+2b）（a+3b）[a+（n-1）b]
例12.设m>n≥1,求最小的m+n使得1000|1978m-1978n.
m
n
n
nk
-1）
≡0（mod2
33
解：
令k=m-n,则1978-1978
≡0（mod1000）
2?
989
（1978
?
5）
2n
0（mod
23）n3
1978≡3（mod5）∴1978
4
20
20
1978k
1
，∵
≡1（mod5），∵1978≡3（mod25）∴1978≡3≡
0（mod53）
1（mod25）
，
∵1978≡-22（mod5
3
）,（-22）
20
20
20
4
4
2
3
20
≡26
≡（25-3）
≡3≡（243）
≡7≡（50-1）
≡26（mod5）∴1978
（mod53）,
∴197840≡（25+1）2≡51（mod53）,197860≡（25+1）（50+1）≡76（mod53）,197880≡（50+1）2≡101（mod53）,1978100≡
（25+1）（100+1）≡1（mod53）,∴100|k∴k最小=100,m+n=m-n+2n最小=106.
例13.设a1,a2,a3,是整数序列,此中有无量多项为正整数,也有无量多项为负整数
.假定对每个正整数
n,数a1,a2,a3,
an被n除的余数都各不同样.证明:
在数列a1,a2,a3,
中,每个整数都恰好出现一次.
证明：
数列各项同时减去一个整数不改变此题的条件和结论
故不如设a1=0.此时对每个正整数
k必有
∣ak∣若∣ak∣≥k,取n=∣ak∣,则a1≡ak≡0（modn）,
矛盾.此刻对k概括证明a1,a2,,ak适合重排后
是绝对值小于
k的k个相邻整数.k=1
明显.设a1,a2,,a
k适合重排后为－（k－1－i）,
0,,i（0
≤i≤
k－1）,因为a
a,,a
a
k+1
是（modk+1）的一个完满节余系
故必a≡i+1（modk+1）,
但∣a∣1
2
k
k+1
k+1
ak+1只好是i+1
或－（k－i）,
进而a1,a2,,ak,ak+1适合重排后是绝对值小于
k+1的k+1
个相邻整数.
由此得
到:
1）.任一整数在数列中最多出现一次
;2）.若整数u和v（u都出此刻数列中,则u与v之间的所有整
数也出此刻数列中
.最后由正负项均无量多个（即数列含有随意大的正整数及随意小的负整数）就获得
:
每
个整数在数列中出现且只出现一次.
例14.偶数个人围着一张圆桌讨论，歇息后，他们依不同样序次从头围着圆桌坐下，证明最罕有两个人，他
44
v1.0可编写可改正
们中间的人数在歇息前与歇息后是相等的。
证明：
将座号依靠时针序次记为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的和=ji≡0（mod2n），而任一完满节余
系mod2n的和≡1+2++2n-1≡n（2n-1）≡0（mod2n）,矛盾！
故结论建立。
例15.证明：
无论n和k是如何的正整数,2n3k+4nk+10不可以能是连续正整数之积.
证明：
令p=nk,则2n3k+4nk+10=2p3+4p+10是偶数,取mod3,∵2p3+4p+10=（3p3+3p+9）-（p-1）p（p+1）+1
∴2p3+4p+10≡1（mod3）,进而2p3+4p+10不是3个或3个以上连续正整数之积,而两个连续正整数之积按
mod3分类:
3m（3m+1）≡0（mod3）,（3m+1）（3m+2）≡2（mod3）,（3m+3）（3m+2）≡0（mod3）∴原式也不是两个正整
数之积.综上知:
2n3k+4nk+10不可以能是连续正整数之积.
例16.设正整数a,b使得15a+16b和16a-15b都是正整数的平方，求这两个平方数所可能取的最小值（IMO37
－4）。
解：
设15a+16b=x2和16a-15b=y2,x,y∈Z+,则15x2+16y2=（13·37）a,16x
2-15y2=（13·37）b,若（37,y）=1,
设yy
1
≡1（mod37）,
则由
2
2
2
2
得15（xy
1
）
2
≡-16（mod37）,16（xy
1
2
15x+16y≡0（mod37）,16x-15y≡0（mod37）,
）
≡
15（mod37）
（xy
1）2≡-6（mod37）
，
这
是
不
可
能
的
，
因
仅
有
r2≡0,±1,±3,±4,±7,±9,±10,±12,±16（mod37）∴x=
37u,y=37v,0≡15u2+16v2≡2u2+3v2（mod13）,0≡16u2-15v2≡3u2-2v2（mod13）,若（13,u）=1
，设uu1≡1（mod13）,
则2（vu1）2≡-3（mod13）,3（vu1）2≡2（mod13）
（vu1）2≡5（mod13）,这是不可能的,因仅有
r2≡0,±1,±3,±4（mod13）
∴u=13s,v=13t,x=37·13s,y=37·13t,取s=t=1
得x2，y2的最小值为x2=y2=（13·37）
2=231361，此时，a=
13·37·31，b=13·37。
练习题
*
.证明x1
x2,不可以能都是质数.
1.设a,b,x0∈N,xn=axn-1+b,n=1,2,
证明：
设x1=p是质数,则p>a,（p,a）=1,x
2,x3,,xp+2这p+1个数中必有两个属于
modp的同一节余类,
即有m>n≥2,使得xm≡xn（modp）,由题意有xm-xn≡a（xm-1-xn-1）≡0（modp）,挨次类推,有xm-n+1-x1≡0（modp）,即
有
55
v1.0可编写可改正
p|xm-n+1,因数列增,所以xm-n+1>p,xm-n+1不是质数.
2.确立所有正整数n,使方程xn+（2+x）n+（2-x）n=0有整数解.
解：
明显,若n为偶数,则方程无实数根,若n=1,则x=-4.当n≥3且为奇数时∵方程左端是首项为1,
常数项为2n+1的多项式∴其整解只好是-2t（t为非负整数）形式:
若t=0,1,2则x=-1,-2,-4都不是方程的根;
若t≥3,则-2nt+（2-2t）n+（2+2t）n=0-2n（t-1）+（1-2t-1）n+（1+2t-1）n=0，∵-2n（t-1）+（1-2t-1）n+（1+2t-1）n≡2（mod4）∴
左端≠0.综上知,仅当n=1时,原方程有独一整解
x=-4.
3.
问能否存在一个无量项素数数列
p,p,,p
对随意n知足|p
n+1
-2p|=1
请说明原因.
12
n
n
解：
若存在,则由pn+1=2pn±1>pn知{pn}递加,p
3>3,p3≡1或2（mod3）.
升级会员 