高中数学竞赛中数论问题的常用方法
数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法.
1.基本原理
为了使用方便,我们将数论中的一些概念和结论摘录如下:
我们用表示整数,,…,的最大公约数.用[,,…,]表示,,…,的
最小公倍数.对于实数,用[]表示不超过的最大整数,用{}=-[]表示的小数部分.对于整数,若,则称关于模同余,记为.对于正整数,用表示{1,2,…,}中与互质的整数的个数,并称为欧拉函数.对于正整数,若整数中任何两个数对模均不同余,则称{}为模的一个完全剩余系；若整数中每一个数都与互质,且其中任何两个数关于模不同余,则称{}为模的简化剩余系.
定理1设的最大公约数为,则存在整数,使得.
定理2(1)若,,2,…,,,则；
(2)若,,,则；
(3)若,,且,则；
(4)若(),,M=[],则().
定理3(1)；(2)；
(3)设为素数,则在质因数分解中,的指数为.
定理4(1)若{}是模的完全剩余系,,则{}也是模的完全剩余系；
(2)若{}是模的简化剩余系,,则{}是模的简化剩余系.
定理5(1)若,则.
(2)若的标准分解式为,其中为正整数,为互不相同的素数,则.
对于以上结论的证明,有兴趣的读者可查阅初等数论教材.
2方法解读
对于数论试题,除直接运用数论的基本原理外,常用的基本方法还有因式(因数)分解法,配对法,分组法,估值法,同余方法,构造法,调整法,数学归纳法与反证法.下面分别予以说明
2.1基本原理的应用
例1设正整数,,的最大公约数为1,并且(1),证明:是一个完全平方数.
证:设,,,其中.由于,故有.由(1)得
(2)
由(2)知,,又,∴.同理可证,从而有,设,为正整数,代入(2)得(3)
由(3)知,又,,.∴.∴.故成立.
例2设为大于1的奇数,,,…,为给定的整数.对于{}的排列,
记,试证存在{}的两个不同的排列B、C,使得.
证:假设对于任意两个不同的排列B、C,均有不整除.令X为{}的所有排列构
成的集合,则{}为模的一个完全剩余系,从而有(1)
又=(2)
而为大于1的奇数,所以由(1),(2)得.
又,所以,矛盾.故,存在B、C,BC,使得.
2.2因式(数)分解
数论中许多问题直接与因式(数)分解相关联,如合数问题,整除问题等常常是要证明某种分解式的存在.数的标准分解式本身就是一种特定形式的因数分解.在不定方程的求解与一些代数式的求值中,因式(数)分解能帮助我们确定某些变量的取值范围,寻找到解题的方法.
求三个素数,使得它们的积为和的5倍.
解:易知,,中必有一个为5,不妨设,则有,从而有.
因为与均为正整数,不妨设,则有或,从而知,.故所求的三个素数为2,5,7.
2.3配对
例4设为正奇数,证明:整除.
分析因为.故需证,注意到当为奇数时,可因式分解,因此可将中的个数两两配对.
证=,
而当为奇数时,,从而知(1)
又=,
∴(2)
由(1)(2)知,,故结论成立.
2.4分组
例5(1990年高中联赛试题)设,,且具有下列性质:
(1)对任何,；(2).
试证:中的奇数的个数是4的倍数,且中所有数的平方和是一定数.
证:对于,令,.,则中恰含中的一个元素.设中有个奇数,,…,,有个偶数,这里=.由题设知,10080==+
=2+=.
∴(1)
由于为偶数,所以,又,所以,,即是4的倍数.
==+
=+
=+(2)
将(1)代入(2)得=1349380.
2.5估值
例6令表示前个质数之和,即,,,…,证明:对任意的正整数,区间[]中包含有一个完全平方数.
分析:设质数从小到大依次为…,要结论成立,只要存在正整数,使得,只要,只要,只要,只要,只要(1)
证:直接验证易知[],[],[],[]中都含有1个完全平方数.当时,我们证明:(1)式成立.为此,令,
则=.
当时,为奇数,故,=,
故当时,数列为递增数列.由于
==32>
所以当时,.故当时(1)式成立.
求出不定方程(1)的全部正整数解.
解当时,易得；当时,(1)式左边为偶数,故右边也是偶数,所以为奇数.当时,由,得.当时,由,得.
当且为奇数时,,,故,即,因此,所以.
另一方面,由二项式定理知=A(+.
其中A为整数,所以,故,因此,故有.
这说明当时,方程(1)无解,故方程(1)的解为,,.
2.6同余
例8证明能被1984整除.
证993==,
∴.∴.
用1,2,3,4,5,6,7组成的无重复数字的7位数,证明:这些7位数中没有一个是另一个的倍数.
证:若有两个7位数,,使得(1)
由于,均是由1,2,...,7所排成,故由(1)得,
∴,即,这与矛盾,故结论成立.
2.7构造
例10若一个正整数的标准分解中,每个素约数的幂次都大于1,则称它为幂数,证明:存在无穷多个互不相同的正整数,它们及它们中任意多个不同数的和都不是幂数.
证:将全体素数从小到大依次记为,,,,….
令,,当时,,下证:,,…,,…合题意.
事实上,,但,所以不是幂数.又对于,
==,
其中A为正整数.因为,所以在的标准分解中的幂次为1,因而不是幂数.
例11设中质数的个数为,为正整数且,求证必有个连续正整数,
其中恰有个质数.
证:令,并令为中质数的个数,则易知
,.对于,显然有,
所以对于,必存在一个,使得,从而中的个连续整数满足要求.
2.8数学归纳法
例12设是正整数,求证:.
证:令.因为,所以,假设,那么对于,因为,所以要证,只需证,即只需证明.为此,令.显然有,假设,
由于,因此,由归纳法原理知对一切,有,从而有,再由归纳法原理知,对于正整数,有.
2.9反证法
例13试证方程(1)无正整数解.
分析:若()为(1)的一组解,则为偶数,令,则,从而知为偶数,再令,代入得,故为偶数,再令,代入得,因此也是方程(1)的解.这样由方程(1)的一组正整数解必可得到另一组正整数解,且.因此,若开始取得的正整数解使得达到最小,则这种下降不可能进行.
证:反证法.若方程(1)存在正整数解,设是使得达到最小的正整数解,那么依分析的过程知必可得到方程(1)的一组正整数解,且,这与达到最小相矛盾,这个矛盾表明方程(1)无正整数解.
习题
1．设,,为整数,证明是整数.
2．设,为整数,证明:.
3.设是大于3的奇数,证明可将集合的元素分成两组,每组个元素,使得两组数的和模同余.
第2页共6页
|
|
