高中数学竞赛专题讲座专题训练

竞赛试卷
同余的概念与应用
概念与性质
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
≡b
1
(modm),a
2
≡b
2
(mod m)，则a
1
±a
2
≡b
1
±b
2
(mo dm),a
1
a
2
≡b
1
b
2
(modm );
(ⅳ)设f(x)=a
n
x
n
+a
n-1x
n-1
+…+a
1
x+a
0
,g(x)=b
n
x
n
+b
n-1
x
n-1
+…+b
1< br>x+b
0
是两个整系数多项式,满足a
i
≡
b
i< br>(modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac ≡bc(modm)
?
a≡b(mod
m
),
(c,m)
(ⅵ)若m≥1,(a,m)=1,则存在整数c使得ac≡1(modm).称c为a对模m的逆或倒数,记为 c=a
-1
(modm);
?
a?b(modm
1
)
(ⅶ)
?
同时成立
?
a?
b
(mod[m
1
,m
2
]);( ⅷ)若a≡b(modm
1
),a≡b(modm
2
),且(m
1< br>,m
2
)=
?
a?b(modm
2
)
1, 则a≡b(modm
1
m
2
).
3. 剩余类：设m为正整数，把 全体整数按对模m的余数分成m类，相应m个集合记为：K
0
,K
1
,…,K
m-1
,
其中K
r
={qm+r|q∈Z,0≤余数r≤m-1}称 为模m的一个剩余类。
性质：(ⅰ)
Z?
0?
i
?
m?1
?K
i
且K
i
∩K
j
=φ(i≠j).
(ⅱ)每一整数仅在K
0
,K
1
,…,K
m-1
一个里.
(ⅲ)对任意a、b∈Z，则a、b∈K
r
?
a≡b(modm).
4. 完全剩余系：设K
0
,K
1
,…,K
m-1
为模m的全部剩余类，从每个K
r
里任取一个a
r
，得m个数a
0< br>,a
1
,…,a
m-1
组成的数组，叫做模m的一个完全剩余系。0, 1,2,…,m-1叫做模m的最小非负完全剩余系。
性质：(ⅰ)m个整数构成模m的一完全剩余系
?
两两对模m不同余。
(ⅱ)若(a,m)=1，则x与ax+b同时跑遍模m的完全剩余系。
5. 既约剩余系：如果K< br>r
里的每一个数都与m互质，则K
r
叫与m互质的剩余类，在与模m互质的全部 剩
余类中，从每一类任取一个数所做成的数组，叫做模m的一个既约剩余系。
性质：(ⅰ)K
r
与模m互质
?
K
r
中有一个数与m互质；
(ⅱ)与模m互质的剩余类的个数等于
?(m)
;
(ⅲ)若(a,m)=1,则x与ax+b同时跑遍模m的既约剩余系。
(ⅳ)设(a,p)= 1,则d
0
是a对于模p的阶
?
a
d
o≡1(modp), 且1,a,…,a
do-1
对模p两两不同余.特别地,d
o
=
Φ (p)
?
1,a,…,a
Φ(p)-1
构成模p的一个既约剩余系.
例1. 设x
i
∈{-1,1},i=1,2,…,101,证明:x
1+2x
2
+…+100x
101
≠0.
证明:∵x< br>1
+2x
2
+…+100x
101
≡1+2+…+101≡5 1≡1(mod2)∴成立.
?
n
?
p
C?
例2. 设p为质数.求证:
n
?
p
?
(modp)
.
? ?
?
n
?
n?i
证明:∵n≡0,1,2,…,p-1(modp) ∴必有某一个i(0≤i≤p-1)使得n≡i(modp),从而
??
?
p
?
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)!
C
n
=(p-1)!n(n-1)…(n-i+1)(n-i-

竞赛试卷
n?i
?
n
?
n?in?in? i
p
p
C??

??
(modp
C
1)… (n-p+1)≡(p-1)!(modp),即(p-1)!
n
≡(p-1)!(modp) ,因((p-1)!,p)=1∴
n
p!pp
p
?
p
??
n?i
?
n
?
?
??
(modp)
.
p
?
p
?
例3. 设m>0,证明必有一个仅由0或1构成的自然数a是m的倍数.
证明：考虑数字全为1的数 :1,11,111,1111,…中必有两个在modm的同一剩余类中,它们的差即为所求
的a.
例4. 证明从任意m个整数a
1
,a
2
,…,a
m
中,必可选出若干个数,它们的和(包括只一个加数)能被m整除.
证明：考虑m个数a< br>1
,a
1
+a
2
,a
1
+a
2+a
3
,…,a
1
+a
2
+…+a
m
,如果其中有一个数能被m整除,则结论成立,否
则,必有两个数属于modm的同一剩余类,这两个数 的差即满足要求.
例5. 证明数11,111,1111,…中无平方数.
证明 ：因任意整数n
2
≡0或1(mod4),而11≡111≡1111≡…≡3(mod4), 所以,数11,111,1111,…中无平方数.
例6. 确定n
5
=1335
+110
5
+84
5
+27
5
.
解：因n
5
≡3
5
+0
5
+4
5
+75
≡3+4+7≡4(mod10),所以n个位数字为4,显然n的首位数字为1,进一步估p
n
5
?
5
?
5
计:n
5
< 2×133
5
+(84+27)
5
<3×133
5
<
??
?133
,所以,n<
?133
<167,所以n可取134,144 ,154,164,又
4
?
4
?
n
5
≡1
5
+(-1)
5
≡3(mod3),故n=144.
注：欧拉猜测4个自然 数的5次方之和不是5次方,于1962年被三位美国数学家推翻,例6就是他们举的
反例.
例7. 求3
2006
的个位数及末两位数字.
解：(1)即求a(0≤a ≤9),使得3
2006
≡a(mod10).∵3
2
≡9≡-1(mod1 0),∴3
4
≡1(mod10),3
2006
≡3
2004+2< br>≡3
4X501+2
≡
3
2
(mod10),故3
2006
的个位数是9;(2)即求b(0≤b≤99),使得3
2006
≡b(mo d100).注意到:4

X25=100且
(4,25)=1,3
4
≡81≡1(mod5),∵3
4
≡81≡6(mod25),3
8
≡36 ≡11(mod25),∴3
12
≡66≡-9(mod25),3
16
≡- 54≡-4(mod2
5)∴3
20
≡-24≡1(mod25) ①;∵3
2
≡1(mod4)∴3
20
≡1(mod4) ②,由①,②得3
20
≡1(mod100),∴3
2006
≡
3
20 X100
?3
6
≡29(mod100),故3
2 006
的末两位数字是29.
例8. 求1

X3

X5

X

7

X…X2005的末3位数字.
解：注意到:8X125=1000且(8,125)=1，∵(2n-3)(2n-1)(2n+1) (2n+3)≡(4n
2
-9)(4n
2
-1)≡1(mod8)，及M=
1

X3

X5

X

7

X…X2005=125m是1003个奇数之积，∴M≡1

X3

X5≡7(mod8), 125m≡5m≡7(mod8)，∴m≡
3(mod8)，∴M≡125m≡125X3≡375(mod8)，∴M≡125m≡375(mod8) .即1

X3

X5

X

7

X…X2005的末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，∵1
2
≡
11
2
≡19
2
≡29
2
≡1(mod30), 7
2
≡13
2
≡17
2
≡23
2
≡19( mod30)，∴p
2
≡1或19(mod30)
例10. 设n,k为正整数,求证:存在无限多个形如n?2
k
-7的平方数.
解：即求使得 m
2
+7≡0(mod2
k
)成立的整数m.当k=1,2,3时,取m=1 +4r(r为正奇数),则有m
2
+7≡0(mod2
k
).
设对k (≥3)有整数m使得m
2
+7≡0(mod2
k
),显然m为奇数,对于k +1，∵(m+a?2
k-1
)
2
+7≡m
2
+7+ma? 2
k
≡
2
m?7
kk+1
2(am+b)(mod2), 其中b=∈Z
+
,取正整数a,b同奇偶,则有(m+a?2
k-1
)
2
+7≡0(mod2
k+1
)，∴对任意
k
2
5
正整数k存在无限多个整数m使得m
2
+7≡0(mod2
k
).
例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
)
n
a(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|1978
m
-1978
n
.
解：令k=m-n,则1978
m
-1978
n
≡0(mod100 0)
?
2
n
?989
n
(1978
k
-1 ) ≡0(mod2
3
?5
3
)
?

n3
?
?
2?0(mod2)?n?3
，∵1978≡3(mod5) ∴1978
4
≡1(mod5)，∵1978≡3(mod25) ∴1978
20
≡3
20
≡
?
k3
?
?
1978?1?0(mod5)
1(mod25)，∵1978≡-22(mod5
3
),(-22)
20
≡(25-3)
20
≡3
20
≡(243)
4
≡7
4
≡(50-1)
2
≡26(mod5
3
)∴1978
20
≡26
(mod5
3
),
∴1978
40
≡(25+1)
2
≡51(mod5
3< br>),1978
60
≡(25+1)(50+1)≡76(mod5
3
) ,1978
80
≡(50+1)
2
≡101(mod5
3
) ,1978
100
≡
(25+1)(100+1)≡1(mod5
3
),∴100|k∴k
最小
=100, m+n=m-n+2n
最小
=106.
例13. 设
a
1
,a
2
,a
3
,
数
a
1
,a
2< br>,a
3
,
是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设 对每个正整数
n
,
中,每个整数都刚好出现一次.
,a
n
被
n
除的余数都各不相同.证明:在数列
a
1
,a
2
,a
3
,
证明：数列各项同时减去一个整数不改变本题的条件和结论,故不 妨设a
1
=0.此时对每个正整数k必有
∣a
k
∣k
∣≥k,取n=∣a
k
∣,则a
1
≡a
k
≡ 0(mod n),矛盾.现在对k归纳证明a
1
,a
2
,…,a
k
适当重排后是绝
对值小于k的k个相邻整数.k=1显然.设a
1
,a
2
,…,a
k
适当重排后为－(k－1－i),…,0,…,i (0≤i ≤ k －1),由于
a
1
,a
2
,…,a
k
,a
k+1
是(mod k+1)的一个完全剩余系,故必a
k+1
≡i+1(mod k+1), 但∣a
k+1
∣k+1
只能是
i+1 或－(k－i),从而a
1
,a
2
,…,a
k
,a
k+1
适当重排后是绝对值小于k+1的k+1个相邻整数. 由此得到:1).任一整
数在数列中最多出现一次;2).若整数u和v (u中.最后由正负项均无穷多个（即数列含有任意大的正整数及任 意小的负整数）就得到:每个整数在数列中
出现且只出现一次.
例14. 偶数个人围着一张 圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下，证明至少有两个人，他
们中间的人数在休息前与 休息后是相等的。
证明：将座号依顺时针次序记为1,2,…,2n，每个人休息前后的座号记为(i ,j)，则i与j跑遍完全剩余系
mod2n。如果两个人(i
1
,j
1)，(i
2
,j
2
)休息前后在他们中间的人数不相等，则有j
2
-j
1
≡i
2
-i
1
mod2n，即j
2
-i
2
≡
j
1
-i
1
(mod2n) ，因此，j－i也跑遍完全剩余系mod2n∴j－i的和=
?
j?
?
i≡0(mod2n)，而任一完全剩余系
mod2n的和≡1+2+…+2n-1≡n(2n-1) ≡0(mod2n),矛盾！故结论成立。
例15. 证明：不论n和k是怎样的正整数,2n
3k
+4n
k
+10不可能是连续正整数之积.
证明：令p=n
k
,则2n
3k
+4n
k
+10=2p
3
+4p+10是偶数,取mod3,∵2p
3
+4p+10=(3p
3
+3p +9)-(p-1)p(p+1)+1
∴2p
3
+4p+10≡1(mod3),从 而2p
3
+4p+10不是3个或3个以上连续正整数之积,而两个连续正整数之积按
mod3分类: 3m(3m+1)≡0(mod3),(3m+1)(3m+2)≡2(mod3),(3m+ 3)(3m+2)≡0(mod3)∴原式也不是两个正
整数之积.综上知:2n
3k
+4n
k
+10不可能是连续正整数之积.
例16. 设正整数a,b使得15a+ 16b和16a-15b都是正整数的平方，求这两个平方数所可能取的最小值
(IMO
37< br>－
4
)。
解：设15a+16b=x
2
和16a-15b= y
2
,x,y∈Z
+
,则15x
2
+16y
2=(13·37)a,16x
2
-15y
2
=(13·37)b,若(3 7,y)=1,
设yy
1
≡1(mod37),则由15x
2
+16 y
2
≡0(mod37),16x
2
-15y
2
≡0(mo d37),得15(xy
1
)
2
≡-16(mod37),16(xy
1
)
2
≡
15(mod37)
?
(xy
1
)
2
≡-6(mod37)，这是不可能的，因仅有r
2
≡0,±1 ,±3,±4,±7,±9,±10,±12,±16(mod37)∴x=
37u,y=37v,0 ≡15u
2
+16v
2
≡2u
2
+3v
2
(mod13),0≡16u
2
-15v
2
≡3u
2
-2v
2
(mod13),若(13,u)=1，设uu
1
≡1(mod13),< br>则2(vu
1
)
2
≡-3(mod13),3(vu
1
)
2
≡2(mod13)
?
(vu
1
)
2
≡5(mod13),这是不可能的,因仅有r
2
≡0,±1,±3,±4(mod13)
∴u=13s,v=13t,x=37·13s,y=37·13t,取s=t=1得x
2，y
2
的最小值为x
2
=y
2
=(13·37)
2
=231361，此时，a=
13·37·31，b=13·37。
练习题
1. 设a,b,x
0
∈N
*
,x
n
=ax
n-1
+b ,n=1,2, ….证明x
1
,x
2
,…不可能都是质数.
证明：设x
1
=p是质数,则p>a,(p,a)=1, x
2
,x
3
,…,x
p+2
这p+1个数中必有两个属于modp的同一剩余类,
即有 m>n≥2,使得x
m
≡x
n
(modp),由题意有x
m
-x
n
≡a(x
m-1
-x
n-1
)≡0(modp),依 次类推,有x
m-n+1
-x
1
≡0(modp),即有

竞赛试卷
p|x
m-n+1
,因数列增,所以x
m-n+1
>p, x
m-n+1
不是质数.
2. 确定所有正整数n,使方程x
n
+ (2+x)
n
+(2-x)
n
=0有整数解.
解：显然, 若n为偶数,则方程无实数根,若n=1,则x=-4.当n≥3且为奇数时∵方程左端是首项为1,常数
项为2
n+1
的多项式∴其整解只能是-2
t
(t为非负整数)形式:若t =0,1,2则x=-1,-2,-4都不是方程的根;若t≥3,
则-2
nt
+(2 -2
t
)
n
+(2+2
t
)
n
=0
?
-2
n(t-1)
+(1-2
t-1
)
n
+( 1+2
t-1
)
n
=0，∵-2
n(t-1)
+(1-2< br>t-1
)
n
+(1+2
t-1
)
n
≡2(m od4)∴左端≠0.综
上知,仅当n=1时,原方程有唯一整解x=-4.
3. 问是否存 在一个无限项素数数列p
1
,p
2
,…,p
n
,…对任意n 满足|p
n+1
-2p
n
|=1?请说明理由.
解：若存在,则由 p
n+1
=2p
n
±1>p
n
知{p
n
} 递增, p
3
>3, p
3
≡1或2(mod3).若p
3
≡1(mod3),则p
4
=2p
3
-1即
p
4
≡ 1(mod3)∴p
5
=2p
4
-1,…,p
n
=2pn-1
-1∴p
n
=2
n-3
p
3
-2
n-3
+1,取n-3=p
3
-1则由
2
p
3
? 1
≡1(modp
3
)
知p
n
≡0(modp
3
),矛盾!若p
3
≡2(mod3), 则p
4
=2p
3< br>+1,即p
4
≡2(mod3)∴p
5
=2p
4
+1 ,…,p
n
=2p
n-1
+1,
∴p
n
=2n-3
p
3
+2
n-3
-1,取n-3=p
3
-1则由
2
p
3
?1
≡1(modp
3
)知pn
≡0(modp
3
),矛盾!
3
n
3
L
3
m
4. 设三角形的三边长分别为整数 L,m,n,且L>m>n.已知
{
4
}?{
4
}?
{4
}
,其中{x}表示x的小数部
10
1010
分.求三角形周 长的最小值.
3
L
3
m
3
n
解：∵
{< br>4
}?{
4
}?{
4
}
∴3
L
,3
m
,3
n
的末四位数相同,从而10
4
|3
L-3
m
=3
m
(3
L-m
-1),10
4|3
L-m
-1∴L-m
101010
12233k122
= 4k,其中k∈N
*
.∵3
L-m
=81
k
=(1+80)
k
=1+
C
k
80?C
k
80?C
k80???80
∴10
4
|3
L-m
-1
?
1 0
4
|
C
k
80

?C
k
80? C
123
12323
3
C
k
80?C
k
8 0
2
?C
k
80
3
?
125|
C
k
?C
k
80?C
k
80
2
=k(40k-39) +
C
k
80?C
k
80
2
∴5|k,
80
2
∵5|
C
k
125|
C
k
80，∵125|k(40k-39)+
C
k
80
，∴125|k(40k- 39)∵5?40k-39∴125?40k-39∴125|k,k=125r,其中
r∈N
*
.即L-m=4k=500r,同理m-n=500s,s∈N
*
.∵n>L-m= 500r≥500∴n
小
=501，∵m=n+500s≥501+500=
100 1，∴m
小
=1001,L≥500+1001=1501,所求三角形周长的最小值为501 +1001+1501=3003.
解法2：由已知得3
L
≡3
m
≡3
n
≡(mod10
4
)即3
L
≡3
m
≡3
n
≡(mod2
4
) ①，3
L
≡3
m
≡3
n
≡(mod5
4
) ②，由①
得3
m-n
≡1(mod2
4
) ∵3
4
≡1(mod2
4
) ∴4|m-n,m-n=4k,由②得3
m-n
≡3
4k
≡1(mod5
4
),现求满足此式的k:∵3< br>4k
-1≡
3232
k(k?1)
28
k(k?1)(k? 2)
312
(1+5?2)-1≡5k?2+?5?2+?5?2≡0(mod5
4< br>)
?
k=5
3
t,m-n=500t,同理L-n=
26< br>4k4
500r,其中t,r为正整数，∵L>m>n∴r>t,即三角形三条边为500r+n , 500t+n和n,且有n>500(r-t)≥500∴仅
当t=1,r=2,n=501时,1 000+501+500+501+501=3003.
5. 如果整数n不是2的倍数,也不是5的倍数.证明n必能整除一个各位都是1的数。
m个
n?
1个
????
?????
?
?????
证明：若数
1
,
11
,
111
,
?
,
111
?
1
中有被n整除者，则问题得证；否则必有
111
?
1< br>与
111
?
1
(m>r)
r个
m个
m个r个 m
?
r个r个
r
个
??????????????????
?????
?????
使得
111
?
1
≡
111< br>?
1(modn)
，即
n|[111
?
1?111
?
1]?111
?
10
?
0
，因n不是2和5的倍
m
?
r个
?????
数，所以
n|
111
?
1
，得证。
6. 设a是4568
7777
的各位数之和, b是a的各位数之和,c是b的各位数之和.求c.

竞赛试卷
解： ∵4568
7777
<10000
7777
=10
4×7777共4×7777+1=31109位数，∴a<9×31109=279981,b<2+5×9=47,
c<4+9=13，∵4568
7777
≡5
7777
≡5
3×2592+1
≡5(-1)
2592
≡5(mod9)，∴a≡b≡c≡5(mo d9) ∴c=5.
7. 对于给定的正整数k,用f
1
(k)表示k的各位数之和 的平方,并设f
n+1
(k)=f
1
(f
n
(k))(n≥ 1).试求f
2005
(2
2006
)的值.
解：注意到10m
≡1(mod9)∴正整数N=a
n
×10
n
+…+a
1
×10+a
0
≡a
n
+…+a
1
+a
0
(mod9).设f
1
(2
2006
)=a
1
2
,则
a
1
≡2
2006
≡2
3×668
? 4≡4(mod9), 设f
2
(2
2006
)=f
1
(a
1
2
)=a
2
2
,则a
2
≡a
1
2
≡7(mod9),设f
3
(2
2006
)= f
1
(a
2
2
)=a
3
2
,则a
3
≡a
2
2
≡
4(mod9),，∵lg2
2006
=2 006×lg2<700∴f
1
(2
2006
)<(9×700)
2
<4×10
7
,f
2
(2
2006
)<(3+9× 7)
2
<4500,f
3
(2
2006
)<(3+
3×9)
2
=30
2
∵a
3
<30∴a
3
=4,13,22.，f
3
(2
2006
)∈{16,169,242}, f
3
(2
2006
)=16时, f
4
(2
2006
)=7
2
=49, f
5
(2
2006
)=13
2
=
169,f
6
(2
2006
)=16
2
=256, f
7
(2
2006
)=13
2
=169,…,f
2 n
(2
2006
)=16
2
=256,f
2n+1
(2
2006
)=13
2
=169∴f
2005
(2
2006
)=169.
8. 试求
7
7
?
7
(100个7)的末四位数.
7
?
7
解：∵7≡-1(mod4)∴
7
≡-1( mod4)(98个7),设
7
7
?
7
7
?
7=4k+3(98个7),k∈Z
+
,则
7
7
?
77
?
7
=7
4k+3
(99个
7)∵7
4< br>≡1(mod100)∴7
4k
≡1(mod100),
7
≡7
4k+3
≡7
3
≡43(mod100).又设
7
=7
1 00m+43
(100个7),m∈Z
+
.
∵7
4
≡24 01(mod10000)∴7
8
≡4801(mod10000), 7
16
≡9601(mod10000),7
32
≡9201(mod10000), 7
64
≡
8401(mod10000),7
100
≡7
4
?7
32
?7
64
≡2401?9201?8401≡1(mod 10000),7
100m
≡1(mod10000),7
100m+43
≡ 7
43
≡
7
3
?7
8
?7
32
≡2343 (mod100 00)，∴
7
7
?
7
(100个7)≡7
100m+43< br>≡2343(mod10000),
7
7
?
7
(100个7) 的末四位数
为2343.
三. 重要定理及应用
1. Euler定理：设整数m>1,且(a,m)=1.则有a
φ(m)
≡1(modm).
2. Fermat定理：设p是素数,则对任意正整数a有a
p
≡a(modp).
证明：若p|a,则显然成立.若(p,a)=1,则a,2a,…,(p-1)a对modp余数各不 相同(若p|(m-n)a(n则p|m-n,m=n,矛盾!).所以,a?2a? …?(p-1)a≡1?2?…?(p-1)(modp),即a
p-1
?(p-1)!≡(p -1)!(modp)，∵(p,p-1)=1，
∴a
p
≡a(modp).

3. 设(a,m)=1,c是使得a
c
≡1(modm)的最小正整数,则c|φ(m).
4. Wilson定理：设p是素数,则(p -1)!≡-1(mod p).
5.中国 剩余定理：设K≥2,而m
1
,m
2
,…,m
k
是K个两两 互质的正整数，令M=m
1
m
2
…m
k
=m
1M
1
=m
2
M
k
=…=
?
x?a< br>1
(modm
1
)
?
x?a(modm)
?
22
-1-1-1
?
m
k
M
k
，则下列同余式组：
?
的正整数解是x≡a
1
M
1
M
1
+a< br>2
M
2
M
2
+…+a
k
M
k
M
k
(modM).
?
?
?
?
x?a
k
(modm
k
)
例1. （Ⅰ）设n为大于1的整数，证明2
n
-1不能被n整除。
（Ⅱ）试求所有能使2
n
+1被n
2
整除的素数n。
证明 ：（Ⅰ）若n为偶数，则结论成立；若n为奇素数，则2
n
-1≡1(modn),结论成立； 若n为奇合数，
则n的质因数(奇素数)都不整除2
n
-1，即n不整除2
n
-1，故结论为真。
（Ⅱ）易知使2
n
+1≡0(modn
2
)的素数n为奇数，∴(2,n)=1，2
n
≡2(modn)∵2
n+1≡0(modn)∴3≡0(modn)
即n|3，n=3显然满足题意。
x
5
x
3
7x
??
例2. 证明对任意整数x,是整数.
5315
3x
5
?5x
3
?7x
证明：即
15
,由Fermat定理得x
5
≡x(mod5),∴3x
5+5x
3
+7x≡3x+7x≡10x≡0(mod5)，

竞赛试 卷
∵x
3
≡x(mod3)∴3x
5
+5x
3
+ 7x≡5x+7x≡12x≡0(mod3)，∵(3,5)=1∴3x
5
+5x
3< br>+7x≡0(mod15),得证.
例3. 设p是大于3的素数.求证:42p|3
p
-2
p
-1.
证明：∵ 42=2×3×7,2|3
p
-2
p
-1,3|3
p
-2< br>p
-1,由Fermat定理得3
p
≡3(modp), 2
p
≡2(modp)，∴3
p
-2
p
-1≡
0(modp)∵3
6
≡1(mod7), 2
6
≡1(mod7) ,p>3是素数，∴p≡1(mod6)或p≡5(mod6)，∴3
p
-2
p
-1≡3
6k+1
-2
6k+1
-1≡3-
2-1≡0(mod 7)或3
p
-2
p
-1≡3
6k+5
-2
6k+5
-1≡5-4-1≡0(mod7)即7|3
p
-2
p
-1∴42p |3
p
-2
p
-1.
例4. 已知m,n为正整数,且m为奇数, (m,2-1)=1.证明:m|
n
?
k
k?1
m
n
.
mm
证明：∵1,2,…,m构成modm的完系,(m,2)=1∴2,4,…,2m 也构成modm的完系∴
?
(2k)
k?1
n
?

?
k
n
(modm
k?1
?
(2k)
k?1
m
n
?
?
k(modm)
即
(2?1)
?
k?0(modm)
∵(m,2-1)=1，∴
m|
?
k
n
得证.
nnn
n
mm
m
k?1k?1
k?1
例5. 求与 数列
?
a
n
?2
n
?3
n
?6
n
?1,n?1
?
中所有项都互质的所有正整数.
解：显然(1,a
n
)=1.设m>1是与{a
n
}中所有项都互质的正整数,p为m的一个质因数,若 p>3,则由费马小
定理得:
2
p?
p?1
?1
?
modp
?
,
3
p?1
?1
?
modp
?
,
6
p?1
?1
?
modp
?
，记
2
p?1
?mp?1
,
3
p?1
?np?

1
mp?1np?1tp?1
???1
=
236
3?np ?1
,
6
?
p?1
p?2p?2p?2
?tp?1
(
m,n,t?Z
),则
a
p?2
?2?3?6?1?
3m p?2np?tp3m?2n?t
?p?
，∵由a
p-2
为整数,
( p,6)?1
，∴6|3m+2n+t,
pa
p?2
这与(m,a
p -2
)=1
66
矛盾!若p=2或3,则a
2
=48=2
4
?3,p|a
2
也矛盾!故与
?
a
n
?
中 所有项都互质的正整数只有1.
例6. 求使得7
d
≡1(mod2
r)(整数r≥3)的最小正整数d
0
.
1
2
r?2
r -1rk
解：∵Φ(2)=2(1-)=2及d
0
|Φ(2)∴d
0
=2, 0≤k≤r-1.先证:对任意奇数a,必有
a
2
rr
?1(mod 2
r
)
:
r=n+1归纳法,设a=2t+1,当r=3时,a=4t(t+ 1)+1≡1(mod2),设当r=n时,
a
23
2
n?2
?1( mod2
n
)
,则当
时,
a
2
n?1
?1 ?(a
2
n?2
?1)(a
2
n?2
?1)
可被2
n+1
整除,即有
a
2
n?1
?1(mod2
n? 1
)
,故结论成立. 由此可
知d
0
=2中的k满足0≤k≤r-2 .我们证明:对任意整数r≥3,必有
7
k
2
r?3
?
1( mod2):归纳法,当r=3时,显然成立,
r
n-1
设当r=n时,
7< br>2
n?3
?
1(mod2)∵
7
n
2
n?3
≡1(mod2) ∴
7
n-1
2
n?3
=1+s?2,其 中整数2
?
s,∴
7
2
n?2
?

(7< br>r
2
n?3
2
)?1?s(1
7
2
n?2< br>?(7
2
n?3
2
2
j
)?1?s(1?s?2)2
n?2n
,2
?
1+s?2,即
n-2
7
2
n?2
?
1(mod2
n+1
)∴
7
2
r?3< br>?
1(mod2),由此推
得:
7
?
1(mod2),0≤j ≤r-3,故d=2
r
0
r-2
为所求.
例7求所有的正整数对(p,n)满足:(ⅰ)p是素数; (ⅱ)n≤2p; (ⅲ)n
p-1
|(p-1)
n
+1.
解：显然(p,1)和(2 ,2)是满足题意的正整数对，下设n≥2,p≥3.∵(p-1)
n
+1为奇数∴n为奇数且 n<2p，
记q为n的最小素因子，则q|(p-1)
n
+1即(p-1)
n
≡-1(modq),且(q,p-1)=1,(n,q-1)=1,存在u,v∈Z使得

竞赛试卷
un+v(q-1)=1,由Fermat小定理得：p-1≡(p-1)
nu
(p-1)
v(q-1)
≡(-1)
u
(modq)∵q为奇数∴u必为奇数,p-1≡
p1p?1p?1
-1(modq)，从而 p=q，∵n<2p=2q及q是n的最小素因子∴n=p=q.∵(p-1)
p
+1=
p?C
p
p???C
p
p

∴p
p-1
|(p-1)
p
+1
?
p≤3∴p=3,满足题意的所有的正整数对为(p, 1)、(2,2)、(3,3)其中p为任意质数(IMO
40
).
方法2 ：对任意素数p，数对(p,1)是解；当p=2时，仅有数对(2,1)、(2,2)是解；下设p≥3，n≥ 2，若
(p,n)是解，则n是奇数，设n的最小素因子是q，n=q
d
m(q?m) ，则
(p-1)≡(p-1)(modq)∴
(p?1)
q
q
d?
(p-1)(modq)
∵q|(p-1)+1，∴
(p?1)
n< br>q
d
m
?(p?1)
n
?(p?1)
m
?? 1(modq)
，∵(p-1)
2m
≡1(modq)，∴q|(p-1)
2 m
-1，
∵(p-1)
q-1
≡1(modq)，∴q|(p-1)
q-1
-1∵q是n的最小素因子∴(2m,q-1)=2，设p-1对模q的阶为r,则r|2m, r|q-1，
∴r=2∴q|(p-1)
2
-1=p(p-2)，∵(m,q-1) =1,若q|p-2,则q|(p-1)
m
+1=[(p-2)+1]
m
+1 = (p-2)
m
+…+m(p-2)+2
?
q|2
p?1
p-1
与n是奇数矛盾∴q|p,必有q=p，∵n=qm=pm<2p=2q∴n=q=p,又由(ⅲ )得p|(p-1)+1=p-…+p
2
2
ddp-1p
展开式仅有4项∴n =p=3。故满足条件的所有的正整数对为(p,n)=(p,1)、(2,2)、(3,3)。
例8. 已知p为奇素数.证明：
2p?1
k?
?
k?1
p ?1
p(p?1)
(modp
2
)
.
2
证明：∵ p-1为偶数∴
2p?22p?2
2p?12p?12p?1
2p-12p-1
p
2p?1
?C
1
p?k???C
k?[k?(p?k)]
，∵k+(p-k)=
2p?12p?1
??
p?1
p?1
2< br>k?1k?1
12p?22p?22p?2
，∴k
2p-1
+(p-k )
2p-1
≡
C
2p?1
p?k
C
2
?k ???C
2p?1
p
p?1
p?k
12p?2
≡p(2p- 1)k
2p-2
(modp
2
),由Fermat定理知k
p-1< br>≡
p?1
p?1
2
1(modp)，∴(2p-1)k
2p -2
≡2p-1≡-1(modp)即(2p-1)k
2p-2
=pm-1，∴p(2 p-1)k
2p-2
≡p
2
m-p≡-p(modp
2
)， ∴
p?1
p?1
2
?
k
k?1
2p?1

?
?
(?p)?
k?1
?
k
2p?1
?< br>?
(?p)??
k?1k?1
p(p?1)p(p?1)p(p?1)
?p
2
??(modp
2
)

222
练习题
1. 求所有的素数对(x,y)满足x
y
-y
x
=xy
2
-19.
解：∵x
y
=y
x
+xy
2
- 19及Fermat定理x
y
≡x(mody)，∴x
y
≡x≡-19(mo dy)∴y|x+19,同理x|y-19,xy|(x+19)(y-
19),即xy|19(y- x-19)∴xy|y-x-19.(ⅰ)当x=2时,2
y
=3y
2
-19 ,由y|x+19=21得y=3,7,检验知(2,3)和(2,7)都是
解.(ⅱ)当y=2时,x
2
=2
x
+4x-19,且x|(-17)∴x=17检验知(17,2)非 解.(ⅲ)当x≥3时,当y≥3时,由xy|y-x-19及
y≤x+19得:3x≤xy≤x+19 -y≤x+16即3x≤x+16∴x≤8,x=3,5,7.此时,由y|x+19=22,24,26得y= 11,3,13不满足
x|y-19,非解.∴满足x
y
-y
x
=x y
2
-19的所有素数对(x,y)=(2,3)和(2,7).
2. 证明：不存在非负整数k和m,使得k!+48=48(k+1)
m
.
证明：k=0 ,m=0显然不是解.下设k,m为正整数.1
0
.若k+1为合数,则k+1|k!, k+1|48∵48|k!∴k≥6,
k=7,11,23,47检验知都不是解.2
0.若k+1为素数,由Wilson定理知k!≡-1(modk+1),即k+1|k!+1，∵k!+4 8=
48(k+1)
m
∴k+1|47,k=46.方程为46!+48=48?4 7
m
即
46!
?1
=47
m
,取mod4得1≡( -1)
m
(mod4)∴m为偶数,
48
令m=2m
1
.则 有
(47
m
1
?1)(47
m
1
46!46!m
2
∵23|,
47
1
?1?2(mod23)
，?1)
=
4848

竞赛试卷
∴23
2
|
∴23
2
|
47
47
m
1
?1
m
1
，∵
47
m
1
?(46?1)
m
1< br>≡46m
1
+1(mod23
2
)，
?1
?
23
2
|46m
1
?
23|m
1
∴m=2m
1
≥46,故有46!+48<48?47
m
.综上所述,不存在非负整数k
和m,使得k!+48=48(k+1)
m
.
3. 已知p是一个大于5的素数. 求证:至少存在两个不同的正整数q
1
,q
2
满足:(ⅰ)1≤q
1
,q
2
≤p-1; (ⅱ)q
i
p-1
≡
1(modp
2
)(i=1,2).
证明：引理:若a
b
?1(modc),则必存在素数q|a且q
b
≡1(modc).证明原题:由二项 式定理可知(p-1)
p-1
,
(p+1)
p-1
, (2p-1)
p-1
, (2p+1)
p-1
这四个数在modp
2
下的余数均不为1∴存在q
1
|p-1且q
1
p-1
≡1( modp
2
).(ⅰ)若
q
1
≠2,则令q
2
=2 ,易知q
2
|p+1,且q
2
p-1
≡1(modp
2), q
1
,q
2
即为所求.(ⅱ)若q
1
=2,则由2p-1, 2p+1中必有一数被
3整除,可令q
2
=3,则必有q
2
|2p- 1或2p+1,且q
2
p-1
≡1(modp
2
)得证.
4. 证明,对于每一个素数p,总存在无穷多个正整数n使得p|2
n
-n.
证明：若p=2,则n取任意偶数,结论成立;若p>2,则由Fermat定理得2
p-1
≡1(modp),令n=(mp-1)(p-1),m
为任意正整数,则n≡1(mo dp),2
n
≡1(modp)∴2
n
-n≡0(modp),即有p|2< br>n
-n.故结论成立.

5. 已知k为正整数,k≥2, p
1,p
2
,…,p
k
为奇素数,且(a,p
1
p
2
…p
k
)=1.证明a
(p
1
?1)(p
2?1)?(p
k
?1)
-1有不同
于p
1
,p
2
,…,p
k
的奇素数因数.
证明：∵(a,p
1
p2
…p
k
)=1∴(a,p
1
)=1, 由Fermat定理得 :
a
p
1
?1
?1(modp
1
)
,又
(p
1
?1)(p
2
?1)
?
(p
k?1)
2
(p
2
?1)(p
3
?1)?(p
k
?1)
为正整数，∴
a
2
同理得
(p
1
? 1)(p
2
?1)?(p
k
?1)
2
?1(modp
1
)
即
p
1
|a?1
,
p
2
, p
3
,
?
,p
k
|a
(p
1
?1 )(p
2
?1)
?
(p
k
?1)
2
(p? 1)(p
2
?1)?(p
k
?1)
?1
,∵
1为偶数∴
a
2
(p
1
?1)(p
2
?1)?
(p
k
?1)
2

?0或1(mod
?1) (p
2
?1)?(p
k
?1)
2
?0或1(mod4)，且4
?
a
因数∴
a
(p
1
?1)(p
2
?1)
?
(p
k
?1)
(p
1
?1) (p
2
?1)
?
(p
k
?1)
2
?1,即
a
(p
1
?1)(p
2
?1)
?
(p
k
?1)
2
?1
有异于p
1
,p
2< br>,…,p
k
的奇素数
?1]
有异于p
1
,p
2
,…,p
k
的奇
?1?[a
(p
1
?1)(p< br>2
?1)
?
(p
k
?1)
2
?1][a(p
1
?1)(p
2
?1)
?
(p
k
?1)
2
素数因数.
6. 已知p为素数.证明,存在一个素数q,使得对任意正整 数n,q
?
n
p
-p.
p
p
?1
pp
?1
p?122
?p?
?
?p?p?1?p?1(modp)
，∴
证明：∵中至少有一个素因子q满
p?1
p?1
足q? 1(modp).若存在正整数n使得n≡p(modq),则有
n
2p
p
2
?p
p
?1(modq)
(∵p|p
p
-1),由Ferm at定
理得: n
q-1
≡1(modq)及p
2
?q-1,(p< br>2
,q-1)|p(∵(p
2
,q-1)=1或p)，∴n
p
≡1(modq)∵n
p
≡p(modq)∴p≡1(modq)
∴1+p+p2
+…+p
p-1
≡p(modq)，∵q是1+p+p
2
+… +p
p-1
的一个质因子∴p≡0(modq)与p≡1(modq)矛盾!
7. 设正整数a,b,c,d,m,n满足:a+b+c+d=m
2
, a
2
+b
2
+c
2
+d
2
=1989,且其中a,b,c,d 的最大者为n
2
.试求m,n的
值.
解:显然,a,b,c,d不全为偶数 (1奇或3奇),从而m为奇数.∵m
2
=a+b+c+d
?4(a
2
?b
2
?c
2
?d
2
)?

21989
c
2
?d
2
)?21989
<90,∴m
2
只能取{1
2
,3
2
,5
2
,7
2
,9
2
},∵(a+b+c+d)
2
>a
2
+b
2+c
2
+d
2
=1989∴m
2
>
1989< br>即m
2
≥45∴m
2

竞赛试卷
=49或81.若m
2
=49即a+b+c+d=49.∵a,b,c,d 的最大者 为d=n
2
∴4n
4
≥a
2
+b
2
+c< br>2
+d
2
=1989∴n≥5,∵a+b+c=
49-n
2
∴5≤n≤6即n=5或6,d=25或36.a+b+c=24或13, a
2
+b
2
+c
2
=1364或693,∵(a+b+c )
2
=24
2
=576>a
2
+
b
2< br>+c
2
或(a+b+c)
2
=13
2
=169>a< br>2
+b
2
+c
2
,∴此时方程无解.∴m
2
=a+b+c+n
2
=81, a
2+b
2
+c
2
+n
4
=1989,∵4n
2< br>≥81
∴n≥5∵1989-n
4
≥3即n
4
≤1992∴ 5≤n≤6即n=5或6. 当n=5时,a+b+c=56,a
2
+b
2
+c
2
=1364,∵4|1364=a
2
+
b
2
+c
2
∴a,b,c均为偶数:a=2a
1
,b=2b
1
,c=2c
1< br>且a
1
2
+b
1
2
+c
1
2
=341, a
1
+b
1
+c
1
=28∵a
1
2
+b
1
2
+c
1
2

=341≡1(mod4)
∴a
1
,b
1
,c
1
必定两个偶数一个奇数: a
1
=2a
2
,b
1
=2b
2
,c
1
=2k-1且2(a
2
+b
2
+k)=29矛盾!当n=6时,a +b+c=45,a
2
+
b
2
+c
2
=693 ,∵693≡1(mod4)∴a=2a
1
,b=2b
1
,c=2k-1且a
1
+b
1
+k=23,a
1
2
+b
12
+k(k-1) =173,∵k(k-1)为偶数
∴a
1
,b
1
一奇一偶: a1
=2a
2
,b
1
=2r-1且2a
2
+2r +k=24,4a
2
2
+4r(r-1)+k(k-1) =172∴2|k,4|k (k-1)∴4|k,又
(a
1
?b
1
)
2
(23 ?k)
2
?
∵173-k(k-1) =
a
1
?b
1
?
,即有k
2
-16k+61≤0∴7≤k≤9,∵4|k∴k=8,a< br>2
+r=8,a
2
2
+
22
22
r(r- 1)=29,消去a
2
得2r
2
-17r+35=0,解得r=5,(a,b ,c,d)=(12,18,15,36)∴m
2
=81,n
2
=36,(m ,n)=(9,6).
8. 求方程2
x
?3
y
-5
z< br>?7
w
=1的所有非负整数解(x,y,z,w).
解:(1)若y=0,则 2
x
-5
z
?7
w
=1,当z≠0时, 2
x≡1(mod5)∵2
4
≡1(mod5)∴4|x,从而3|2
x
-1 =5
z
?7
w
,这不可能
∴z=0, 2
x
-7< br>w
=1,当x=1,2,3时,(x,w)=(1,0),(3,1);当x≥4时, 7
w
=2
x
-1≡-1(mod16),但当w为偶数时7
w
≡ < br>1(mod16),当w为奇数时7
w
≡7(mod16),矛盾.∴这时解为(1,0 ,0,0),(3,0,0,1);(2)若y>0.①当x=1时,2?3
y
-
5
z
?7
w
=1,则5
z
?7
w
≡-1(m od3),即(-1)
z
≡-1(mod3)∴z为奇数∴2?3
y
≡1(m od5)∵3
4
≡1(mod5),∴y≡1(mod4)即
y=4m+1.当w≠0 时, 2?3
y
≡1(mod7)∵3
6
≡1(mod7)∴y≡4(mod 6),y=6n+4=4m+1,即6n=4m-3矛盾∴必有w=0,
2?3
y
- 5
z
=1,当y=1时,z=1;当y≥2时,5
z
≡-1(mod9)∵5
6
≡1(mod9)∴z≡3(mod6),5
3
+1|5
z
+1,7|5
z
+1=2?3
y
矛盾!
∴这时解为(1,1,1 ,0),②当x≥2时,∵5
z
?7
w
≡-1(mod4),5
z< br>?7
w
≡-1(mod3)即
(-1)
w
≡-1(mod4) ,(-1)
z
≡-1(mod3)∴w,z都是奇数,2
x
?3
y< br>=5
z
?7
w
+1≡35+1≡4(mod8),∴x=2,y=2k ,方程为
4?3
y
-5
z
?7
w
=1∴4?3y
≡1(mod5),y≡2(mod4),
4?3
y
≡1(mod7 ),y≡2(mod6)∴y≡2(mod12),设y=12m+2(m≥0),则5
z
?7
w
=4?3
12m+2
-1=(2?3
6m+1
-1)(2 ?3
6m+1
+1)
?
2?3
6m?1
?1?5
z
?
∵2?3
6m+1
+1≡0(mod7),(2?3
6m+1< br>-1,2?3
6m+1
+1)=1∴5|2?3
6m+1
-1,∴?
,若m≥1,则5
z
≡
6m?1w
?
?1?7?
2?3
z
?
?
2?3?1?5
-1(mod9),由 ①的证明知不可能.若m=0,则y=2,
?
得z=w=1,得解(2,2,1,1).故原方 程的所有解
w
?
?
2?3?1?7
为:(x,y,z,w)=(1, 0,0,0),(3,0,0,1),(1,1,1,0),(2,2,1,1).
9. 求方程5< br>x
+1=2
y
+2
z
?5
t
的所有正整数解 (x,y,z,t).
解:设(x,y,z,t)是方程的正整数解,则2
y
≡1( mod5)∵2
4
≡1(mod5)∴4|y,对方程两边mod4得
2
z< br>≡2(mod4)∴z=1.设y=4r,得5
x
+1=2
4r
+2? 5
t
即5
x
-2?5
t
=16
r
-1,两 边mod3得:(-1)
x
+(-1)
t
≡0(mod3)∴x,t一奇一< br>偶∵5
t
≡1或5(mod8)∴对5
x
=2?5
t
+16
r
-1,两边mod8得: 5
x
≡2?5
t
-1≡ 1(mod8)∴x为偶数,t为奇数.(1)若t=1,
则5
x
=16
r< br>+9,设x=2m,则(5
m
-3)(5
m
+3)=16
r< br>.∵(5
m
-3,5
m
+3)=(5
m
-3,6)= 2∴5
m
-3=2,5
m
+3=2
4r-1,
∴m=1,2
4r-1
=2
3
∴r=1,y=4,x=2,得解(x,y,z,t)=( 2,4,1,1);(2)若t>1,则t≥3,x≥4,5
3
|5
x
-2? 5
t
=16
r
-1∵16
r
-1=(15+1)
r
=15
r
+…+
1
?15
∴5|r,令r=5k,则16
5k
-1≡5
5k
-1≡(5?3
2
)
k
-1≡0(mod11),∴11|5
x
-2?5
t
=5
t
(5
x-t
-2),即11|5
x-t
-2,但
C
r
2
?15
2
+
C
r
5
n
≡1,3,4, 5,9(mod11),即11
?
5
x-t
-2,矛盾!故原方程有唯一解( x,y,z,t)=(2,4,1,1).