数学竞赛数论问题.doc

高中数学竞赛中数论问题的常用方法数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法.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 因式(数)分解数论中许多问题直接与因式(数)分解相关联,如合数问题,整除问题等常常是要证明某种分解式的存在.数的标准分解式本身就是一种特定形式的因数分解.在不定方程的求解与一些代数式的求值中,因式(数)分解能帮助我们确定某些变量的取值范围,寻找到解题的方法.例3 求三个素数,使得它们的积为和的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)式成立.例7 求出不定方程 (1)的全部正整数解.解 当时,易得；当时,(1)式左边为偶数,故右边也是偶数,所以为奇数.当时,由,得.当时,由,得.当且为奇数时,故,即,因此,所以.另一方面,由二项式定理知=A(+.其中A为整数,所以,故,因此,故有.这说明当时,方程(1)无解,故方程(1)的解为,.2.6同余 例8 证明能被1984整除. 证 993=,.例9 用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)存在正整数解,设是使得达到最小的正整数解,那么依分析的过程