关键词不能为空

当前您在: 主页 > 数学 >

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

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2020-09-21 13:34
tags:高中数学专题

高中数学书推荐-高中数学空集的表示

2020年9月21日发(作者:颜龙安)


同余的概念与应用
概念与性质
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 );
nn-1nn-1
(ⅳ)设f(x)=a
n
x+a
n- 1
x+…+a
1
x+a
0
,g(x)=b
n
x+b
n-1
x+…+b
1
x+b
0
是两个整系数多项式,满足a
i

b
i
(modm)(0≤i≤n).若a≡b(modm), 则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)
?
a≡b(mod
m
),
(c,m)
-1
(ⅵ)若m≥1,(a,m)=1,则存在 整数c使得ac≡1(modm).称c为a对模m的逆或倒数,记为c=a(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的阶
?
ao≡1(modp),且1,a,…,a< br>ddo-1
对模p两两不同余.特别地,d
o
=
Φ(p)
?
1,a,…,a构成模p的一个既约剩余系.
例1. 设xi
∈{-1,1},i=1,2,…,101,证明:x
1
+2x
2+…+100x
101
≠0.
证明:∵x
1
+2x< br>2
+…+100x
101
≡1+2+…+101≡51≡1(mod2)∴成立 .
Φ(p)-1
?
n
?
p
C?
例2. 设p为质数.求证:
n
?
p
?
(modp)
.
? ?
证明:∵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)!
C
n
=(p-1)!n(n-1)…(n-i+1)(n-i-
p< br>n?i
1)…(n-p+1)
p!
p
((p-1)!,p)=1∴C
n
?
n?i
≡(p-1)!
p
(modp),即(p -1)!
C
p
n
n?i
≡(p-1)!
p
(mod p),因
n?i
?
n
?
?

??
(mod p)
p
?
p
?
p
n
?
n?i
?< br>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,…中无平方数.
2
证明:因任意整数n≡0或1(mod4),而11≡111≡1111≡…≡3(mod4),所以,数11, 111,1111,…中无
平方数.
55555
例6. 确定n=133+110+84+27.
55555
解:因n≡3+0+4+7≡3 +4+7≡4(mod10),所以n个位数字为4,显然n的首位数字为1,进一步估
5
5< br>?
5
5555
?
计:n<2×133+(84+27)<3×133<
??
?133
,所以,n<
?133
<167,所以n可取134, 144,154,164,又
4
?
4
?
n≡1+(-1)≡3(mo d3),故n=144.
注:欧拉猜测4个自然数的5次方之和不是5次方,于1962年被三位美国 数学家推翻,例6就是他们举的
反例.
2006
例7. 求3的个位数及末两位数字.
解:(1)即求a(0≤a≤9),使得
24+24X501+ 2
3≡a(mod10).∵3≡9≡-1(mod10),∴3≡1(mod10),3≡3≡3≡
220062006
3(mod10),故3的个位数是9;(2)即求b(0≤b≤99) ,使得3≡b(mod100).注意到:4X25=100且
4481216
(4,25)= 1,3≡81≡1(mod5),∵3≡81≡6(mod25),3≡36≡11(mod25),∴3≡66 ≡-9(mod25),3≡-54≡-4
20220
(mod25)∴3≡-24≡1(mo d25) ①;∵3≡1(mod4)∴3≡1(mod4) ②,由①,②得
202006
3≡1(mod100),∴3≡
20 X10062006
3?3≡29(mod100),故3的末两位数字是29.

例8. 求1X3X5X7X…X2005的末3位数字.
22
解:注意到:8X1 25=1000且(8,125)=1,∵(2n-3)(2n-1)(2n+1)(2n+3)≡(4n-9) (4n-1)≡1(mod8),及
M=

1X3X5X7X…X20 05=125m是1003个奇数之积,∴M≡1X3X5≡7(mod8), 125m≡5m≡7(mod8),∴m≡

3(mod8),∴M≡125m≡1 25X3≡375(mod8),∴M≡125m≡375(mod8).即1X3X5X7X…X2005的末 3位数字
为375.
例9. 求大于5的素数平方被30除的余数.
解:设p是大 于5的素数,且p≡r(mod30)(r<30),∵(p,30)=1∴(r,30)=1,r=1,7,1 1,13,17,19,23,29,
2
∵1≡
22222222
11≡19≡29≡1(mod30), 7≡13≡17≡23≡19(mod30),∴p≡1或19(mod30)
555
5


例10. 设n,k为正整数,求证:存在无限多个形如n?2-7的平方数.
2k2k
解:即求使得m +7≡0(mod2)成立的整数m.当k=1,2,3时,取m=1+4r(r为正奇数),则有m+7≡0( mod2).
2kk-122k
设对k(≥3)有整数m使得m+7≡0(mod2),显然m 为奇数,对于k+1,∵(m+a?2)+7≡m+7+ma?2≡
k
m
2
?7
+k-12k+1
2(am+b)(mod2),其中b=∈Z,取正整数a,b同奇偶, 则有(m+a?2)+7≡0(mod2),∴对任意正
k
2
kk+1
整数k 存在无限多个整数m使得m+7≡0(mod2).
例11. 设对任意正整数n≥1,b的质因数都 大于n.证明:n!|a(a+b)(a+2b)(a+3b)…[a+(n-1)b]
-1
证明:∵b的质因数都大于n,∴(b,n!)=1∴bb≡1(modn!)
-1n
∴(b) a(a+b)(a+2b)(a+3b)…[a+(n-1)b]≡
-1-1-1-1-1-1
(ab)(ab+1)(ab+2)(ab+3)…[ab+(n-1)]≡0(modn!),∵(b,n! )=1
∴n!|a(a+b)(a+2b)(a+3b)…[a+(n-1)b]
mn
例12. 设m>n≥1,求最小的m+n使得1000|1978-1978.
mnnnk33
解:令k=m-n,则1978-1978≡0(mod1000)
?
2?989(1978-1) ≡0(mod2?5)
?

2k


n3
?
?
2?0(mod2)?n?3
42020
,∵1 978≡3(mod5) ∴1978≡1(mod5),∵1978≡3(mod25) ∴1978≡3≡
?
k3
?
?
1978?1?0(mod5)
1(mod25 ),∵1978≡-22(mod5),(-22)≡(25-3)≡3≡(243)≡7≡(50-1)≡26 (mod5)∴1978≡26
3
(mod5),

40
∴19 78≡(25+1)≡51(mod5),1978≡(25+1)(50+1)≡76(mod5),1978 ≡(50+1)≡101(mod5),1978≡
3
(25+1)(100+1)≡1(m od5),∴100|k∴k
最小
=100, m+n=m-n+2n
最小
=106.
例13. 设
a
1
,a
2
,a
3
,L
是整数序列,其中有无穷多项为正整数,也有无穷 多项为负整数.假设对每个正整数
32
n
,数
a
1
,a2
,a
3
,L,a
n

n
除的余数都各不相同 .证明:在数列
a
1
,a
2
,a
3
,L
中 ,每个整数都刚好出现一次.
证明:数列各项同时减去一个整数不改变本题的条件和结论,故 不妨设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
,a2
,…,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
a
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
(mo d2n),因此,j-i也跑遍完全剩余系mod2n∴j-i的和=
?
j?
?
i
≡0(mod2n),而任一完全剩余
系mod2n的和≡1+2+…+2n-1≡n(2 n-1)≡0(mod2n),矛盾!故结论成立。
3kk
例15. 证明:不论n和k是怎样的正整数,2n+4n+10不可能是连续正整数之积.
k3kk333
证明:令p=n,则2n+4n+10=2p+4p+10是偶数,取 mod3,∵2p+4p+10=(3p+3p+9)-(p-1)p(p+1)+1
33
∴ 2p+4p+10≡1(mod3),从而2p+4p+10不是3个或3个以上连续正整数之积,而两个连续正 整数之积按
mod3分类: 3m(3m+1)≡0(mod3),(3m+1)(3m+2)≡2(m od3),(3m+3)(3m+2)≡0(mod3)∴原式也不是两个正整


数之积. 综上知:2n+4n+10不可能是连续正整数之积.
例16. 设正整数a,b使得15a+16b 和16a-15b都是正整数的平方,求这两个平方数所可能取的最小值(IMO
37
-4)。
22+2222
解:设15a+16b=x和16a-15b=y,x,y∈Z,则 15x+16y=(13·37)a,16x-15y=(13·37)b,若(37,y)=1,
22 2222
设yy
1
≡1(mod37),则由15x+16y≡0(mod37),1 6x-15y≡0(mod37),得15(xy
1
)≡-16(mod37),16(xy< br>1
)≡
15(mod37)
?
(xy
1
)2
≡-6(mod37),这是不可能的,因仅有
2
r≡0,±1,±3,±4, ±7,±9,±10,±12,±16(mod37)∴x=
22222222
37u,y= 37v,0≡15u+16v≡2u+3v(mod13),0≡16u-15v≡3u-2v(mod13), 若(13,u)=1,设uu
1
≡1(mod13),
222
则2(vu1
)≡-3(mod13),3(vu
1
)≡2(mod13)
?
(vu
1
)≡5(mod13),这是不可能的,因仅有
2
r≡0,±1, ±3,±4(mod13)
22222
∴u=13s,v=13t,x=37·13s,y= 37·13t,取s=t=1得x,y的最小值为x=y=(13·37)=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
不是质数.
nnn
2. 确定所有正整数n,使方程x+(2+x)+(2-x)=0有整数解.
解:显然,若n为偶 数,则方程无实数根,若n=1,则x=-4.当n≥3且为奇数时∵方程左端是首项为1,
n+1t< br>常数项为2的多项式∴其整解只能是-2(t为非负整数)形式:若t=0,1,2则x=-1,-2,- 4都不是方程的根;
nttntnn(t-1)t-1nt-1nn(t-1)t-1nt-1n
若t≥3,则-2+(2-2)+(2+2)=0
?
-2+(1-2)+(1+2)=0,∵ -2+(1-2)+(1+2)≡2(mod4)∴
左端≠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
=2p
n-1
-1∴p
n
=2p
3-2+1,取n-3=p
3
-1则由
2
n-3n-3
3kkp
3
?1
≡1(modp
3
)
知p
n
≡0(modp
3
),矛盾!若p
3
≡2(mod3), 则p
4
=2p
3
+1,即p
4
≡2(mod3)∴p
5
= 2p
4
+1,…,p
n
=2p
n-1
+1,
∴p
n
=2p
3
+2-1,取n-3=p
3
-1则由
2
n-3n-3
p
3
?1
≡1(modp
3
)知p< br>n
≡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
Lmn4LmmL- m4L-m
解:∵
{
4
}?{
4
}?{
4
}
∴3,3,3的末四位数相同,从而10|3-3=3(3-1),10|3-1∴L-m
101010
*L-mkk4L-m4
?C
k
80?C
k
= 4k,其中k∈N.∵3=81=(1+80)=1+
C
k
80?C
k
80?C
k
80???80
∴10|3-1
?
10|
C< br>k
80

12233k1223
123232
123
3
?C
k
80?C
k
80
2
=k(40k-39) +
C
k
C
k
80?C
k
80
2
? C
k
80
3
?
125|
C
k
80
2
∵5|
C
k
80?C
k
80
∴5|k, 33
125|
C
k
80
2
,∵125|k(40k-3 9)+
C
k
80
2
,∴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=
1001,∴m

=1001,L≥500+100 1=1501,所求三角形周长的最小值为501+1001+1501=3003.
Lmn4Lmn 4Lmn4
解法2:由已知得3≡3≡3≡(mod10)即3≡3≡3≡(mod2) ①,3≡3≡3≡(mod5) ②,由
**


①得3≡1(mod2) ∵3≡1(mod2) ∴4|m-n,m-n=4k,由②得3≡3≡1(mod5),现求满足此式的
4k
k:∵3-1≡
(1+5?2)-1≡5k?2+
4k4
m-n44 4m-n4k4
k(k?1)
28
k(k?1)(k?2)
?5?2+
26
?5?2≡0(mod5)
?
k=5t,m-n=500t,同理L-n= < br>31243
500r,其中t,r为正整数,∵L>m>n∴r>t,即三角形三条边为500r +n, 500t+n和n,且有n>500(r-t)≥500∴
仅当t=1,r=2,n=501时 ,1000+501+500+501+501=3003.
5. 如果整数n不是2的倍数,也不是5的倍数.证明n必能整除一个各位都是1的数。
?
1个< br>?????
??
m
?

??
??
n
???
证明:若数
1
,
11
,
111
,? ,
111
?
1
中有被n整除者,则问题得证;否则必有
111
?
1

111
?
1
(m>r)
r个
r个
?
r个r个
r

??
m
?

??
??
m
?

?????????
m
??????< br>?????
使得
111
?
1

111
?1(modn)
,即
n|[111?1?111?1]?111?10?0
,因n 不是2和5的倍
?
r个
??
m
???
数,所以
n|
111
?
1
,得证。
6. 设a是的各位数之和, b是a的各位数之和,c是b的各位数之和.求c.
74×7777
解:∵<=10 共4×7777+1=31109位数,∴a<9×31109=279981,b<2+5×9=47, 77773×2592+12592
c<4+9=13,∵≡5≡5≡5(-1)≡5(mod9) ,∴a≡b≡c≡5(mod9) ∴c=5.
2006
7. 对于给定的正整数k,用f< br>1
(k)表示k的各位数之和的平方,并设f
n+1
(k)=f
1(f
n
(k))(n≥1).试求f
2005
(2)
的值. < br>mn20062
解:注意到10≡1(mod9)∴正整数N=a
n
×10+… +a
1
×10+a
0
≡a
n
+…+a
1
+ a
0
(mod9).设f
1
(2)=a
1
,则
20 063×6682
a
1
≡2≡2?4≡4(mod9), 设f
2
( 2)=f
1
(a
1
)=a
2
,则a
2
≡a
1
≡7(mod9),设f
3
(2)= f
1
(a
2
)=a
3
,则
2
a
3
≡a
2

2622006
4(mod9),,∵lg2=2006×lg2<700∴f
1(2)<(9×700)<4×10,f
2
(2)<(3+9×7)<4500,f
3
(2)<(3+
22220062
3×9)=30∵a
3
<3 0∴a
3
=4,13,22.,f
3
(2)∈{16,169,242}, f
3
(2)=16时, f
4
(2)=7=49, f
5
(2)=13=
262200622006
169,f
6
(2)=16=256, f
7
(2)=13=169,…,f
2n
(2)=16=256,f
2n+1
(2)=13=169∴f
2005
(2)=169.
8. 试求
7
7
?
7
(100个7)的末四位数.
7
?
7
解:∵7≡-1(mod4)∴
7
≡-1(mod4)(98个7),设
7
7
?
7
7
?< br>7
=4k+3(98个7),k∈Z,则
7
+
7
?
7
=7
4k+3
(99
7)∵7≡1(mod100)∴7≡1(mod100 ),
7
44k
48
≡7
4k+3
16
≡7≡43( mod100).又设
7
3
32
7
?
7
=7
100m+43
(100个7),m∈Z.
64
+
∵7≡2401(mod10000)∴7≡4801(mod10000), 7≡9601(mod10000),7≡9201(mod10000), 7≡
1m100m+4 343
8401(mod10000),7≡7?7?7≡2401?9201?8401≡1(mod 10000),7≡1(mod10000),7≡7≡
7?7?7≡2343 (mod10000 ),∴
7
3832
7
?
7
(100个7)≡7
10 0m+43
≡2343(mod10000),
7
7
?
7
( 100个7)的末四位数
为2343.
三. 重要定理及应用
φ(m)
1. Euler定理:设整数m>1,且(a,m)=1.则有a≡1(modm).
p
2. Fermat定理:设p是素数,则对任意正整数a有a≡a(modp).
证明:若p|a,则显然 成立.若(p,a)=1,则a,2a,…,(p-1)a对modp余数各不相同(若
p|(m-n) a(np-1
a?(p-1)!≡(p-1)!(modp),∵(p, p-1)=1,


∴a≡a(modp).

c
3. 设(a,m)=1,c是使得a≡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
1
M
1
=m
2
M
k
=…=
p
?
x?a
1
(modm
1
)
?
x?a(modm)
?
22
?
mM,则下列同余式组:的正整数解是x≡aMM
??
?
?
?
x?a
k
(modm
k
)
kk
n
-1
111
+a
2
M
2
M
2
+…+a
k
M
k
M
k
(modM).
-1-1
例1. (Ⅰ)设n为大于1的整数,证明2-1不能被n整除。
n2
(Ⅱ)试求所有能使2+1被n整除的素数n。
n
证明:(Ⅰ)若n为偶数,则结论 成立;若n为奇素数,则2-1≡1(modn),结论成立;若n为奇合数,
nn
则n的质因 数(奇素数)都不整除2-1,即n不整除2-1,故结论为真。
n2nn
(Ⅱ)易知 使2+1≡0(modn)的素数n为奇数,∴(2,n)=1,2≡2(modn)∵2+1≡0(modn) ∴3≡0(modn)
即n|3,n=3显然满足题意。
x
5
x
3
7x
??
例2. 证明对任意整数x,是整数.
5315
3x
5
?5x
3
?7x
证明:即 ,由
15
353
Fermat定理得x≡x(mod5),∴3x+5x+7x≡3x +7x≡10x≡0(mod5),
53
553
∵x≡x(mod3)∴3x+5x+ 7x≡5x+7x≡12x≡0(mod3),∵(3,5)=1∴3x+5x+7x≡0(mod15),得证 .
pp
例3. 设p是大于3的素数.求证:42p|3-2-1.
pppppp pp
证明:∵42=2×3×7,2|3-2-1,3|3-2-1,由Fermat定理得3≡3(m odp), 2≡2(modp),∴3-2-1≡
66pp6k+16k+1
0(modp)∵3≡1(mod7), 2≡1(mod7),p >3是素数,∴p≡1(mod6)或p≡5(mod6),∴3-2-1≡3-2-1≡3-
pp6 k+56k+5pppp
2-1≡0(mod7)或3-2-1≡3-2-1≡5-4-1≡0(mod 7)即7|3-2-1∴42p|3-2-1.
例4. 已知m,n为正整数,且m为奇数,(m,2 -1)=1.证明:m|
n
n
k
?
.
k?1
mm
m
证明:∵1,2,…,m构成modm的完系,(m,2)=1∴2,4,…,2m也构成m odm的完系∴
?
(2k)
k?1
n
?

?
k
n
(modm
k?1
?
(2k)
k?1
mn
?
?
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?1
?1
?
mo dp
?
,
3
p?1
?1
?
modp
?,
6
p?1
?1
?
modp
?
,记
2
p?1
?mp?1
,
3
p?1
?np?

1
p?
3?np?1
,
6
p?1
?tp?1
(m,n,t?Z
),则
a
p?2
?2
p?2
?3
p?2
?6
p?2
mp?1np?1tp?1
?1????1
=
236


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

7
2< br>r?3
?
1(mod2):归纳法,当r=3时,显然成立,设当
r
n -1
r=n时,
7
2
n?3
?
1(mod2)∵
7
n
2
n?3
≡1(mod2)
n-1
2
n?3< br>=1+s?2,其中整数2
?
s,∴
n?2
7
2
n? 2
?

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

∴p|(p-1)+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,
d
若(p,n)是解, 则n是奇数,设n的最小素因子是q,n=qm(q?m),则
p-1p
(p-1)≡(p-1 )(modq)∴
(p?1)
q
q
d
?
(p-1)(mod q)
?(p?1)
n
?(p?1)
m
??1(modq)
,∵(p-1)≡1(modq),
2m
∵q|(p-1)+1,∴
2m
n< br>(p?1)
q
d
m
∴q|(p-1)-1,
q-1q-1< br>∵(p-1)≡1(modq),∴q|(p-1)-1∵q是n的最小素因子∴(2m,q-1)=2, 设p-1对模q的阶为r,则
r|2m,r|q-1,
2mm
∴r=2∴q|(p- 1)-1=p(p-2),∵(m,q-1)=1,若q|p-2,则q|(p-1)+1=[(p-2)+1] +1=
mdd
(p-2)+…+m(p-2)+2
?
q|2与n是奇数矛盾 ∴q|p,必有q=p,∵n=qm=pm<2p=2q∴n=q=p,又由(ⅲ)得
p|(p-1)+ 1=
p-1p
p?1
p-12
p-…+p展开式仅有4项∴n=p=3。故满 足条件的所有的正整数对为(p,n)=(p,1)、
2
(2,2)、(3,3)。


例8. 已知p为奇素数.证明:
?
k
2p?1
?< br>k?1
p?1
p(p?1)
(modp
2
)
. 2
证明:∵p-1为偶数∴
?
k
k?1
p?1
2p?1
2p?112p?22p?2
2p-12p-1
?C
2
?k?
?
?
[k
2p?1
?(p?k)
2p?1
]
,∵ k+(p-k)=
p

??C
2p?1p?1
p
p?12
k?1
2p-12p-1
12p?22p?22p?2
,∴k+(p- k)≡
C
2p?1
p?k
C
2
p?k???Cp?k
p?12p?1
12p?2
≡p(2p-1)k
2p-2
(modp),由 Fermat定理知k≡
2p-2
2p-1
1(modp),∴(2p-1)kp?1
2p-2
≡2p-1≡-1(modp)即(2p-1)k
2p-2
=pm-1,∴p(2p-1)k≡pm-p≡-p(modp),
22

2p?1
k
?

?
?
(?p)??
k?1k?1
p ?1
2
p?1
2
p(p?1)p(p?1)p(p?1)
?p
2
??(modp
2
222
?
k
2p?1
??
(?p)??
k?1k?1
p?1
p(p?1)p(p?1)p(p? 1)
?p
2
??(modp
2
)

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

4848
22

47?(46?1)
m
1
m
≡46m
1
+1(m od23),∴23|
47
m
1
?1
?
23|46m
?
23|m∴m=2m≥46,故有
2
111
m
46!+48<4 8?47.综上所述,不存在非负整数k和m,使得k!+48=48(k+1).
3. 已知p是一 个大于5的素数.求证:至少存在两个不同的正整数q
1
,q
2
满足:(ⅰ) 1≤q
1
,q
2
≤p-1;
p-1
(ⅱ)q
i

2
1(modp)(i=1,2).
bbp-1
证明:引理:若a?1(modc),则必存在素数q|a且q≡1(mo dc).证明原题:由二项式定理可知(p-1),
p-1p-1p-12p-12
(p+1), (2p-1), (2p+1)这四个数在mo dp下的余数均不为1∴存在q
1
|p-1且q
1
≡1(modp).(ⅰ) 若
p-12
q
1
≠2,则令q
2
=2,易知q
2< br>|p+1,且q
2
≡1(modp), q
1
,q
2
即为所求.(ⅱ)若q
1
=2,则由2p-1, 2p+1中必有一数
p-12
被3整除,可令q
2
=3,则必有q
2
|2p-1或2p+1,且q
2
≡1(modp)得证.
n
4. 证明,对于每一个素数p,总存在无穷多个正整数n使得p|2-n.
p-1
证明: 若p=2,则n取任意偶数,结论成立;若p>2,则由Fermat定理得2≡1(modp),令n=(mp -1)(p-1),m
nnn
为任意正整数,则n≡1(modp),2≡1(modp)∴2 -n≡0(modp),即有p|2-n.故结论成立.

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

21989
c
2
?d
2
)?2198 9
<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
即m
2
≥45∴m
2

=49或81.若m=49即a+b+c+d=49.∵a,b,c,d 的最大者为d=n∴4n≥a+b+c+d=1989∴n≥5,∵a+b+c=
2222222
49-n∴5≤n≤6即n=5或6,d=25或+b+c=24或13, a+b+c =1364或693,∵(a+b+c)=24=576>a+
22222222222242
b+c或(a+b+c)=13=169>a+b+c ,∴此时方程无解.∴m=a+b+c+n=81, a+b+c+n=1989,∵4n≥81
442222
∴n≥5∵1989-n≥3即n≤1992∴5≤n≤6即n=5或6. 当n=5时,a+b+c=56,a+b+c =1364,∵4|1364=a+
22222222
b+c∴a,b,c均为偶数:a=2a
1
,b=2b
1
,c=2c
1
且a
1
+b
1
+c
1
=341, a
1
+b
1
+c
1
=28∵a
1
+b
1
+c
1
=341≡1(mod4)
2
∴a
1
,b
1
,c
1
必定两个偶数一个奇数: a
1
=2a2
,b
1
=2b
2
,c
1
=2k-1且2(a
2
+b
2
+k)=29矛盾!当n=6时,a+b+c=45,a+
2222
b+c =693,∵693≡1(mod4)∴a=2a
1
,b= 2b
1
,c=2k-1且a
1
+b
1
+k=23,a
1
+b
1
+k(k-1) =173,∵k(k-1)为偶数
2
∴ a
1
,b
1
一奇一偶: a
1
=2a
2
, b
1
=2r-1且2a
2
+2r+k=24,4a
2
+4r (r-1)+k(k-1) =172∴2|k,4|k(k-1)∴4|k,又
∵173-k(k-1)
2
22 42222
=
(a
1
?b
1
)
2
(23? k)
2
a
1
?b
1
??
22
22
2
,即有
k-16k+61≤0∴7≤k≤9,∵4|k∴k=8,a
2
+r =8,a
2
+
222
r(r-1)=29,消去a
2
得2 r-17r+35=0,解得r=5,(a,b,c,d)=(12,18,15,36)∴m=81,n=36 ,(m,n)=(9,6).
xyzw
8. 求方程2?3-5?7=1的所有非负整数解(x,y,z,w).


解:(1)若y=0,则2-5?7=1,当z≠0时, 2≡1(mod5)∵2≡1 (mod5)∴4|x,从而3|2-1=5?7,这不可能
xwwxw
∴z=0, 2-7=1,当x=1,2,3时,(x,w)=(1,0),(3,1);当x≥4时, 7=2-1≡-1(mod16),但当w为偶数时7≡
w
1(mod16),当w为奇数时 7≡7(mod16),矛盾.∴这时解为(1,0,0,0),(3,0,0,1);(2)若y>0.①当x =1
y
时,2?3-
zwzwzy4
5?7=1,则5?7≡-1(mod 3),即(-1)≡-1(mod3)∴z为奇数∴2?3≡1(mod5)∵3≡1(mod5),∴y≡1( mod4)
y6
即y=4m+1.当w≠0时, 2?3≡1(mod7)∵3≡1(mod7 )∴y≡4(mod6),y=6n+4=4m+1,即6n=4m-3矛盾∴必有
yzz63zzy< br>w=0, 2?3-5=1,当y=1时,z=1;当y≥2时,5≡-1(mod9)∵5≡1(mod 9)∴z≡3(mod6),5+1|5+1,7|5+1=2?3
zwzw
矛盾! ∴这时解 为(1,1,1,0),②当x≥2时,∵5?7≡-1(mod4),5?7≡-1(mod3)即
w zxyzw
(-1)≡-1(mod4),(-1)≡-1(mod3)∴w,z都是奇数,2?3=5 ?7+1≡35+1≡4(mod8),∴x=2,y=2k,方程为
yzwy
4?3-5?7 =1∴4?3≡1(mod5),y≡2(mod4),
yzw12m+26m+16m+1
4?3≡1(mod7),y≡2(mod6)∴y≡2(mod12),设y=12m+2(m≥0),则5? 7=4?3-1=(2?3-1)(2?3+1)
6m?1z
?
2?3?1?5?
6m+16m+16m+16m+1
∵2?3+1≡0(mod7),(2?3-1,2 ?3+1)=1∴5|2?3-1,∴
?
6m?1w
?
2?3?1?7
?
xzwx4xzw
,若m≥1,则5≡
z
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).
xyzt
9. 求方程5+1=2+2?5的所有正整数解(x,y,z,t).
y4
解:设(x,y,z, t)是方程的正整数解,则2≡1(mod5)∵2≡1(mod5)∴4|y,对方程两边mod4得
zx4rtxtrxt
2≡2(mod4)∴z=1.设y=4r,得5+1=2+2?5即5-2?5 =16-1,两边mod3得:(-1)+(-1)≡0(mod3)∴x,t一
txtrxt
奇一偶∵5≡1或5(mod8)∴对5=2?5+16-1,两边mod8得: 5≡2?5-1≡1(mod 8)∴x为偶数,t为奇数.(1)
xr
若t=1,则5=16+9,设x=2m,则
mmrmmmmm4r-1,4r-13
(5-3)(5+3)=16.∵(5-3,5+3)=(5- 3,6)=2∴5-3=2,5+3=2∴m=1,2=2

∴r=1,y=4,x=2,得解 (x,y,z,t)=(2,4,1,1);(2)若t>1,则
3xtrrrr
t≥3,x≥ 4,5|5-2?5=16-1∵16-1=(15+1)=15+…+
1
?15
∴ 5|r,令r=5k,则16
5k
-1≡5
5k
-1≡(5?3
2< br>)
k
-1≡0(mod11),∴11|5
x
-2?5
t=5
t
(5
x-t
-2),即
C
r
2
?15
2
+
C
r
11|5-2,但5≡1,3,4,5,9(mod 11),即11
?
5-2,矛盾!故原方程有唯一解(x,y,z,t)=(2,4,1,1) .
x-tnx-t

高中数学教学方法有哪几种-高中数学教师教研技能


高中数学全国优质课比赛-高中数学教学计划反思


高中数学必备的初中知识大全-高中数学百度文库必修4


高中数学试讲列举法表示集合-衡水中学高中数学上学期期末考


初高中数学衔接培训内容-高中数学二项式系数和公式


d高中数学必修二-高中数学知识点详细总结


交大高中数学-高中数学科代表家长会发言


高中数学必修四的教材重难点-百度文库高中数学知识点总结



本文更新与2020-09-21 13:34,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/407013.html

高中数学竞赛专题讲座---专题训练的相关文章