高中数学竞赛中数论问题的常用方法

高中数学竞赛中数论问题的常用方法
数论是研究数的性质的一门科学,它与中学数学教 育有密切的联系.数论问题解法灵活,题型丰富,它
是中学数学竞赛试题的源泉之一.下面介绍数论试题 的常用方法.
1.基本原理
为了使用方便,我们将数论中的一些概念和结论摘录如下: < br>我们用
(a
1
,a
2
,...,a
n
)表示整数
a
1
,
a
2
,…,
a
n的最大公约数.用[
a
1
,
a
2
,…,
an
]表示
a
1
,
a
2
,…,
a
n
的
最小公倍数.对于实数
x
,用[
x
]表示不超过< br>x
的最大整数,用{
x
}=
x
-[
x
]表示
x
的小数部分.对于整数
a,b
,若
m|(a?b)
,m?1,
则称
a,b
关于模
m
同余,记为
a?b(mo dm)
.对于正整数
m
,用
?
(m)
表示
{1,2 ,…,
m
}中与
m
互质的整数的个数,并称
?
(m)
为欧拉函数.对于正整数
m
,若整数
r
1
,r
2
,...,r
m
中任何
两个数对模
m
均不同余,则称{
r< br>1
,r
2
,...,r
m
}为模
m
的一个完 全剩余系；若整数
r
1
,r
2
,...,r
?
(m )
中每一个数都
与
m
互质,且其中任何两个数关于模
m
不同 余,则称{
r
1
,r
2
,...,r
?
(m)}为模
m
的简化剩余系.
定理1 设
a,b
的最大公约数为< br>d
,则存在整数
x,y
,使得
d?xa?yb
.
定 理2(1)若
a
i
?b
i
(modm)
,
i?1< br>,2,…,
n
,
x
1
?x
2
(modm)< br>,则
(2)若
a?b(modm)
,
d?(a,b)
,
d|m
,则
?
ax
?
?
bx
i
i1i
n
n
i
2
；
i?1
i?1
abm
?(mod)
；
ddd
ab
(3)若
a?b
,
d?(a,b)
,且
(d,m)?1,则
?(modm)
；
dd
(4)若
a?b
(
modm
i
),
i?1,2,...,n
,M=[
m
1< br>,m
2
,...,m
n
],则
a?b
(
mo dM
).
定理3(1)
x?1?[x]?x?[x]?1
； (2)
[x?y]?[x]?[y]
；
(3)设
p
为素数,则在< br>n!
质因数分解中,
p
的指数为
?
p
k?1
n
k
.
定理4 (1)若{
r
1
,r
2
,...,r
m
}是模
m
的完全剩余系,
(a,m)?1
, 则{
ar
1
?b,ar
2
?b,...,ar
m
? b
}也是模
m
的完全剩余系；
(2)若{
r
1
, r
2
,...,r
?
(m)
}是模
m
的简化剩余系 ,
(a,m)?1
,则{
ar
1
,ar
2
..., ar
?
(m)
}是模
m
的简化剩余系.
定理5(1)若< br>(m,n)?1
,则
?
(mn)?
?
(m)
?
(n)
.
?
k
?
?
2
(2)若
n的标准分解式为
n?p
1
1
p
2
,其中
?1
,
?
2
,...
?
k
为正整数,
p
1
,p
2
,...p
k
为互不相
...p
k

同的素数,则
?
(n)?n(1?
111
)(1? )...(1?)
.
p
1
p
2
p
k
对于 以上结论的证明,有兴趣的读者可查阅初等数论教材.
2 方法解读
对于数论试题,除直接 运用数论的基本原理外,常用的基本方法还有因式(因数)分解法,配对法,分组
法,估值法,同余方法 ,构造法,调整法,数学归纳法与反证法.下面分别予以说明
2.1基本原理的应用
例1 设正整数
a
,
b
,
c
的最大公约数为1,并且
ab
?c
(1),证明:
(a?b)
是一个完全平方数.
a?b证:设
(a,b)?d
,
a?a
1
d
,
b?b
1
d
,其中
(a
1
,b
1
)?1
.由于
(a,b,c)?1
,故有
(d,c)?1
.由(1)得
a
1
b
1
d?a
1
c?b
1
c
(2)
由(2)知,
a
1
|b
1
c
,又
(a
1
,b
1
)?1
,∴
a
1
|c.同理可证
b
1
|c
,从而有
a
1
b
1
|c
,设
c?a
1
b
1
k
,
k
为正整
数,代入(2)得
d?k(a
1
?b
1
)< br> (3)
由(3)知
k|d
,又
k|c
,
?
k|( d,c)?1
,
?
k?1
. ∴
d?a
1
?b1
.∴
a?b?d(a
1
?b
1
)?d
.故成 立.
例2 设
n
为大于1的奇数,
k
1
,
k2
,…,
k
n
为给定的整数.对于{
1,2,...,n
}的排列
P?(a
1
,a
2
,...,a
n
)< br>,
记
s(P)?
2
?
ka
,试证存在{
1 ,2,...,n
}的两个不同的排列B、C,使得
n!|s(B)?s(C)
. < br>ii
i?1
n
证:假设对于任意两个不同的排列B、C,均有
n!不整除
s(B)?S(C)
.令X为{
1,2,...,n
}的所有排列 构
成的集合,则{
s(P)|P?X
}为模
n!
的一个完全剩余系 ,从而有
P?X
n
?
s(P)?
?
i?
i?1n!
(1?n!)n!
(modn!)
(1)
2
n!(n?1)
n
k
i
(2) 又
?
?
s(P)?
?
(
?
k< br>i
a
i
)
=
?
2
P?XP?Xi?1
i?1
(1?n!)n!n!(n?1)
n
?k
i
?0(modn !)
. 而
n
为大于1的奇数,所以由(1),(2)得
?
22i?1
又
(1?n!,n!)?1
,所以
2.2 因式(数)分解 数论中许多问题直接与因式(数)分解相关联,如合数问题,整除问题等常常是要证明某种分解式的存
在.数的标准分解式本身就是一种特定形式的因数分解.在不定方程的求解与一些代数式的求值中,因式
(数)分解能帮助我们确定某些变量的取值范围,寻找到解题的方法.
n!
?0(modn !)
,矛盾.故,存在B、C
?X
,B
?
C,使得
n!|s (B)?s(C)
.
2

例3 求三个素数,使得它们的积为和的5倍.
解:易知
a
,
b
,
c
中必有一个为5,不妨设
c?5
,则有
ab?a?b?5
,从而 有
(a?1)(b?1)?6
.
因为
a?1
与
b?1均为正整数,不妨设
a?b
,则有
?
求的三个素数为2,5,7.
2.3 配对
?
a?1?1
?
a?1?2
或
?< br>,从而知
a?2
,
b?7
.故所
?
b?1?6
?
b?1?3
例4 设
k
为正奇数,证明:
1?2?3 ?...?n
整除
1?2?...?n
.
分析 因为
1 ?2?3?...?n?
kkk
n(n?1)
kkk
.故需证
n(n ?1)|2(1?2?...?n)
,注意到当
k
为奇数
2
kkk< br>kk
时,
x?y
可因式分解,因此可将
2(1?2?...?n)中的
2n
个数两两配对.
kkkkkkkkkk
证 ?
2(1?2?...?n)
=
[1?(n?1)]?[2?(n?2)]?.. .?[(n?1)?1]?2n
,
而当
k
为奇数时,
a?b|a? b
,从而知
n|21?2?...?n
又
?
21?2?. ..?n
kk
kk
?
kkk
?
(1)
?
kkk
?
=
[1
k
?n
k]?[2
k
?(n?1)
k
]?...?[n
k
?1< br>k
]
,
∴
(n?1)|2(1?2?...?n)
(2)
由(1)(2)知,
n(n?1)|2(1?2?...?n)
,故结论成立.
2.4 分组
例5 (1990年高中联赛试题)设
E?{1,2,...,200 }
,
G?{a
1
,a
2
,...,a
100
}
?E
,且
G
具有下列性质:
(1)对任何
1?i?j ?100
,
a
i
?a
j
?201
；(2)
kkk
k
?
a
i?1
100
i
?10080
.
试证:
G
中的奇数的个数是4的倍数,且
G
中所有数的平方和 是一定数.
证:对于
1?i?100
,令
?
i
?2i?1
,
?
i
?201?
?
i
.
E
i< br>?{
?
i
,
?
i
}
,则
G
中恰含
E
i
中的一个元素.设
G
100}
.由中有
k
个奇数
?
i
1
,
?
i
2
,…,
?
i
k
,有
s
个偶数
?
j
1,
?
j
2
,...,
?
j
s
,这里< br>{i
1
,i
2
,...,i
k
,j
1
,j
2
,...,j
s
}
=
{1,2,...,
题设知,10080=
?
?
t?1
k
i
t
?
?
?
j
r
r?1
s
s
?
k
?< br>?
?
(201?
?
i
t
)?
?
?< br>j
r
=
?
201?2
?
?
i
t+
?
?
?
i
t
?
?
?
jr
?

t?1r?1t?1t?1
r?1
?
t?1?
kskk
k
=
201k?
2
?
?
t?1
k
i
t
+
(2?4?6?...?2 00)
=
201k?2
?
?
t?1
i
t
? 10100
.
∴
201k?2
?
?
t?1k
i
t
??20
(1)

由于
?
i
t
为偶数,所以
4|2< br>100
i?1
ks
?
?
t?1
k
k
i
t
,又
4|20
,所以
4|201k
,
?
4|k
,即
k
是4的倍数.
skkks
?
a
2
i
?
?
?
?
?
?
=
?
( 201?
?
i
t
)?
?
?
=
?
2 01?2?201
?
?
i
t
+
(
?
??
?
?
j
2
r
)

t?1
2
i
t
r?1
2
j
r
2
t?1r?1
2
j
r
2
t?1t?1t?1
2
i
t
r ?1
=
201k?2?201
k
2
?
?
t?1t
k
i
t
+
(2?4?6?...?200)

2222
=
201(201k?2
?
?
i
)
+< br>4?
t?1
100
i?1
100(100?1)(200?1)
(2)
6
100?101?201
=1349380.
6
将(1)代入(2)得
2.5估值
?
a
i
2
?201?(?20)?4?
例6 令
a
n
表示前
n
个质数之和,即
a
1
?2
,< br>a
2
?2?3?5
,
a
3
?2?3?5?10
,…,证明:对任意的正
整数
n
,区间[
a
n
,a
n?1
]中包含有一个完全平方数.
2
分析:设质数从小到大依次为
p< br>1
,p
2
,...,p
k
…,要结论成立,只要存在正整数< br>m
,使得
a
n
?m?a
n?1
,
只要
a
n
?m?a
n?1
,只要
a
n?1
?a
n
?1
,只要
a
n?1
?a
n
?1?2a
n
,只要
p
n?1
?1?2a
n
,只要
(pn?1
?1)
2
?4a
n
?4(p
1
?p2
?...?p
k
)
(1)
证:直接验证易知[
a
1,
,a
2
],[
a2
,a
3
],[
a
3
,a
4
],[< br>a
4
,a
5
]中都含有1个完全平方数.当
n?5
时 ,我们
2
证明:(1)式成立.为此,令
f(n?1)?(p
n?1
?1)?4(p
1
?p
2
?...?p
k
)
, < br>22
则
f(n?1)?f(n)?(p
n?1
?1)?(p
n
?1)?4p
n
=
(p
n?1
?p
n
)( p
n?1
?p
n
?2)?4p
n
.
当
n ?2
时,
p
n
为奇数,故
p
n?1
?p
n
?2
,
f(n?1)?f(n)?2(p
n?1
?p
n?2?2p
n
)
=
2(p
n?1
?p
n
?2)
?0
,
故当
n?2
时,数列
f(n)
为递增数列.由于
2
2

f(5)?(p
5
?1)?4(p
1
?p
2
?p
3
?p
4
)
=(11?1)?4(2?3?5?7)
=32>
0

所以当
n? 5
时,
f(n)?f(5)?0
.故当
n?5
时(1)式成立.
例7 求出不定方程
(n?1)!?n?1
(1)的全部正整数解.
解 当
n?2
时,易得
k?1
；当
n?2
时,(1)式左边为偶 数,故右边也是偶数,所以
n
为奇数.当
n?3
时,由
2!?3?1
,得
k?1
.当
n?5
时,由
4!?5?1
,得< br>k?2
.
kk
k

当
n?5
且为奇数 时,
n?1n?1n?1
?n?3
,
?2
,故
2?|(n? 2)!
,即
(n?1)|(n?2)!
,因此
222
(n?1)2
|(n?1)!
,所以
(n?1)
2
|(n
k
?1)
.
另一方面,由二项式定理知
n?1?((n?1)?1)?1
= A(
n?1)
+
k(n?1)
.
其中A为整数,所以
(n ?1)|k(n?1)
,故
(n?1)|k
,因此
k?n?1
,故有
n?1?n
这说明当
n?5
时,方程(1)无解,故方程(1)的解为
(n,k)?(2,1)
,
(3,1)
,
(5,2)
.
2.6同余
例8 证明
993
证
?< br>993
∴
993
993
993
2kn?1
kk2?1?(n?1)!
.
993
?991
991
能被1984整除.
?(?991)
993
=
(?991)
2
(?991)
991
=
(495?1984?1)(?991)
991
?(?991)
991
(mo d1984)
,
?991
991
?(?991)
991
? 991
991
?0(mod1984)
.∴
1984|993
993
?991
991
.
例9 用1,2,3,4,5,6,7组成的无重复数字的7位数,证明:这些7位数中没有一个是另一个的倍数.
证:若有两个7位数
a
,
b
,使得
a?kb
(1)
由于
a
,
b
均是由1,2,...,7所排成,故
2?k?7
由(1)得
a?kb(mod9)
,
∴
1?k?1(m od9)
,即
k?1(mod9)
,这与
2?k?9
矛盾,故结论成 立.
2.7构造
例10 若一个正整数的标准分解中,每个素约数的幂次都大于1 ,则称它为幂数,证明:存在无穷多个互
不相同的正整数,它们及它们中任意多个不同数的和都不是幂数 .
证:将全体素数从小到大依次记为
p
1
,
p
2
,
...
,
p
n
,….
222
令
a1
?p
1
,
a
2
?p
1
p
2
,当
n?2
时,
a
n
?a
n?1
p
n?1
p
n
?p
1
p
2
...p
n?1
p
n
,下证:
a
1
,
a
2
,…,
a
n
,…合题意.
2
2
事实上,
?
p< br>n
|a
n
,但
p
n
?
|
a
n
,所以
a
n
不是幂数.又对于
1?i
1
?i2
???i
k
,

a
i
1
?a
i
2
???a
i
k
?a
i
1
(1 ?
a
i
2
a
i
1
???
a
ik
a
i
1
2
)
=
a
i
1(1?Ap
i
1
)
=
p
1
2
p
2
?p
i
2
p
i
1
(1?Ap
i
1
)
,
1
?1
其中A为正整数.因为
(p
i< br>1
,1?Ap
i
1
)?1
,所以
p
i
1
在
(a
i
1
?a
i
2
???a
i
k
)
的标准分解中的幂次为1,因
而不是幂数.
}
中 质数的个数为
a
,
n
为正整数且
1?n?a
,求证必有2011
个连续正整数, 例11 设
{1,2,3,?,2011
其中恰有
n
个质数.
证:令
A
k
?{k,k?1,k?2,?,k?2010}
,并令
f(k)
为
A
k
中质数的个数,则易知

f(1)?a
,
f(2012!?2)?0
. 对于
k?1,2,?,(2012!?1)
,显然有
|f(k?1)?f(k)|?1
,
所以对于
0?n?a
,必存在一个
k
0
,使得
f( k
0
)?n
,从而
A
k
0
中的
2011< br>个连续整数满足要求.
2.8 数学归纳法
例12 设
n
是正整数,求证:
512|3
证:令
f(n)?3
2n
2n
?32n
2
?24n?1
.
?32n
2
?24n?1.因为
f(1)?0
,所以
512|f(1)
,假设
512|f (n)
,那么对于
n?1
,
2n
因为
f(n?1)?f(n )?8(3?8n?1)
,所以要证
512|f(n?1)
,只需证
512| 8(3
2n
?8n?1)
,即只需证明
64|(3
2n
?8 n?1)
.为此,令
g(n)?3
2n
?8n?1
.显然有
64|g(1)?0
,假设
64|g(n)
,
由于
g(n?1)? g(n)?8(9?1)?64(9
切
n
,有
64|3
2n
nn?1
?9
n?2
???1)
,因此
64|g(n?1)
,由归纳法原理知对一
?8n?1
,从而有
512|f(n?1)
,再由归纳 法原理知,对于正整数
n
,有
512|f(n)
.
2.9 反证法
例13 试证方程
x?2y?4z?0
(1)无正整数解.
分析:若(
x,y,z
)为(1)的一组解,则
x
为偶数,令
x?2 x
1
,则
4x
1
?y?2z?0
,从而知
y
为偶数,
再令
y?2y
1
,代入得
2x
1
?4y
1
?z?0
,故
z
为偶数,再令
z?2z
1
,代入得
x
1
?2y
1
?4z
1
?0
, 因此
333333
333
333
(x
1
,y
1,z
1
)
也是方程(1)的解.这样由方程(1)的一组正整数解
(x, y,z)
必可得到另一组正整数解
(x
1
,y
1
,z
1
)
,且
x
1
?x
.因此,若开始取得的正整数解使得< br>x
达到最小,则这种下降不可能进行.
证:反证法. 若方程(1)存在正整数解,设
(x
0
,y
0
,z
0
)
是使得
x
达到最小的正整数解,那么依分析的过
程知必可得到方程(1)的一组正整数解
(x< br>1
,y
1
,z
1
)
,且
x
1
?x
0
,这与
x
0
达到最小相矛盾,这个矛盾表明方程
( 1)无正整数解.
习题
1．设
m?n?1
,
m
,
n
为整数,证明
2．设
a
,
b
为整数,证明:
( n!)|b
n?1
(m,n)
n
C
m
是整数.
m
a(a?b)(a?2b)?(a?(n?1)b)
.
3.设
n
是大于3的奇数,证明可将集合
{1,2,3,?,n?1}
的元素分成两组,每组< br>和模
n
同余.
n?1
个元素,使得两组数的
2