高中数学竞赛专题讲座---竞赛中的数论问题

1竞赛中的数论问题的思考方法一.条件的增设对于一道数论命题，我们往往要首先排除字母取零值或字母取相等值等“平凡”的情况，这样，利用字母的对称性等条件，往往可以就字母间的大小顺序、整除性、互素性等增置新的条件，从而便于运用各种数论特有手段。1.大小顺序条件与实数范围不同，若整数x，y有大小顺序xy，则必有y≥x+1，也可以写成y=x+t，其中整数t≥1。例1.（IMO-22）设m，n是不大于1981的自然数，1)(222mnmn，试求22nm的最大值。解：易知当m=n时,222nm不是最大值。于是不访设nm,而令n=m+u1，nu1≥1，得2(m1mu1)(22112umum。同理，又可令m=u1+u2，mu2≥1。如此继续下去将得uk+1=uk=1，而11iiiuuu，i≤k。故nmuuuukk,,,,,,121是不大于1981的裴波那契数，故m=987，n=1597。例2.（匈牙利—1965）怎样的整数a，b，c满足不等式?233222cbabcba解：若直接移项配方，得01)1()12(3)2(222cbba。因为所求的都是整数，所以原不等式可以改写为：cbabcba234222，变形为：0)1()12(3)2(222cbba，从而只有a=1，b=2，c=1。2.整除性条件对于整数x，y而言，我们可以讨论其整除关系：若x|y，则可令y=tx；若x∤y，则可令y=tx+r，0r≤|x|-1。这里字母t，r都是整数。进一步，若aq|，bq|且ab，则qab。结合高斯函数，设n除以k，余数为r，则有rkknn。还可以运用抽屉原理，为同余增设一些条件。整除性与大小顺序结合，就可有更多的特性。例3.试证两相继自然数的平方之间不存在自然数abcd，使得ad=bc.解：在假定了22)1(ndcban之后，可设1),(,qpqpbdac。（显然pq）由p，q的互素性易知必有q|a，q|b。这样，由ba即得qab。（有了三个不等式，就可对qp的范围进行估计），从而qnnqadbdqpqqq22)1(111。于是将导致矛盾的结果：0)(2qn。这里，因为a，b被q整除，我们由ba得到的不仅是b≥a+1，而是更强的条件b≥a+q。例4.（IMO-25）设奇数a，b，c，d满足0abcd，ad=bc，若mkcbda2,2，这里k，m是整数，试证a=1。2解：不难证明k，m的大小关系km。[22)(4)(adadda222)()(4)(4cbbcbcadbc222)()(4)(4cbbcbcadbc。所以mk22。]bcadmk2,2，代入ad=bc中，有)2()2(bbaamk（1），由（1）可得2222ababkm。即2222ababkm，))(()2(2abababmkm（2）已知a，b都是奇数，所以a+b，a-b都是偶数，又ababa2)()(是奇数的2倍，故b+a，b-a中必有一个不是4的倍数。由（2）必有fabeabm221或fabeabm221。其中，e，f为正整数，且mkabef2是奇数。[efbabam2)()(，与（2）比较可得]由于km，故fababef22fababef22。从而e=1，mkabf2。考虑前一情况，有)2(2221mkmabfabab由第二式可得aabmk12，故amkm1122，所以奇数a=1。对于后一情况，可作类似的讨论。显然，上述解题思路中有两个技巧：一是用放缩法证明km；第二个是（2）式的分解，然后运用整除的条件。例5.设)(nr为n分别除以1，2，┅，n所得的余数之和。证明存在无穷多个正整数n，使得)1()(nrnr。解：把n除以k的余数记为kr，则有kknnrk。故可得)(nrr的表达式nknknkkkknnkknnrnr1211)()(nknknkkkknnkknnrnr1211)()(。由此易得1121)1()1(nkkknnnr。则11)1()1()1()(nkkknknnnrnr11)1()1()1()(nkkknknnnrnr，因此，)1()(nrnr等价于11)1()1(nkkknknn。注意到nknkknkn|,0|,11nknkknkn|,0|,11，因此题中的条件等价于n的所有真因子之和等于n-1。显然，取ln2(l为正整数)，则n的所有真因子之和为n-1，而这样的n有无穷多个。例6.试证对于任给的m个整数maaa,,,21，必有)1(,mjsjs，使得)(|1jssaaam解：令iiaaab21（mi,,2,1）。若mbbb,,,21中有一个数被m整除，则结论成立。否则，各ib均不能被m整除，此时可设)11(mrrmqbiiii。这样，m个余数mrrr,,,21只能从1至m-1这m-1个数中取值，由抽屉原理知，必有)1(,mjkjk，使得jkrr，于是)(kjkjqqmbb，故)()(|21jkkkjaaabbm取1ks即得到结论。3.互素性的条件3当（a，b）=d1时，我们总是作如下考虑：令dbbdaa11,，则必有1),(11ba。这种互素条件的增置往往对解题有很大作用。例7.（波兰64—65）设整数a，b满足bbaa2232，试证ba及122ba都是完全平方数。解：bbaa2232变形可得：2)122)((bbaba，故只要能证一个，则另一个必是。我们在排除了字母取零或相等的情况后，可设dbababa),(,,0,。这时令dbbdaa11,，1),(11ba，从而方程变为21112132dbbada。显然有)(|11bad。另一方面又212121212111)(223dbbaddadbba212121212111)(223dbbaddadbba，有2111|)(dbba。注意到1),(),(11111babba，于是有dba|)(11。这样就有||11bad。至此已十分容易获得命题的结论了。这里，由a1与b1互素导出a1—b1与b1互素，是证明dba|)(11的关键。二.从特殊到一般例8.（IMO-18）试求和为1978的正整数之积的最大值。解：我们可通过减少加法运算的次数来选择特例，例如考虑求正整数,,,,21naaa满足,10,1021naaan,10,1021naaan使naaa21最大。显然，最特殊且最简单的正整数是1。例如取a1=1，这里由nnnaaaaaaa)1(2221知乘积不是最大的值。对于某些正整数取2的情况，注意到2+2=4，2×2=4；2+2+2=6=3+3，2×2×23×3。我们发现诸ai中不能取多于两个2。对于ai=5，有2+3=5，2×35。因此不如把一个5拆成2与3的和，从而使乘积变大，对于6，7等有类似的结论。这样，我们已大致可确定诸ai只应取2或3，且2的个数不超过两个。依此估计，由1978=658×3+2+2，即可猜测最大的积为658232。例9.（IMO—31备选题）设a，b是给定的正整数，现有一机器人沿着一个有n级的楼梯上下升降，每上升一次恰好上升a级，每下降一次恰好下降b级。为使机器人经过若干次上升下降后，可以从地面升到楼梯顶，然后再返回地面，问n的最小值是多少？解：为了探讨解法和结论，不妨设ba。我们分b|a与a∤b两种情况进行讨论。对于b|a的情况结论是显而易见的：可令a=sb,机器人上升一次，然后再连续下降s次即达到要求，故n=a.现考虑a∤b。例如，特例a=5，b=3。这时机器人先上升一次达到第五级，为使n最小，机器人就不应再上升，而是尽量下降。下降1次至第2级。此时，再上升一次到第2+5=7级，然后再一降两次到第1级，又上升至1+5=6级，再下降二次至0级，从而机器人已完成了上升下降的全过程，故n=7。又取特例a=7，b=4。依上述方法可得n=10。通过特例，我们可作如下猜测：若a∤b，且（a，b）=1，则n=a+b-1。实际上，依照上述试验的思路，这一猜想是可以被证明的。数论中还有很多命题是通过选取某一特殊的数作为模来讨论和解决的。这种数往往是根据命题的一些因素（如项的系数、字母的指数、式的形状等），通过试用来选择和确定的，最简单的是mod2，即奇偶分析法。其次是模3，4，5，8等。三.讨论极端情况4由于整数集具有最大（小）整数原理这一特性，我们往往可以从某种条件下有最大（小）元素出发进行讨论。例如，可考虑：（1）数列中具有某种特点的极端项；（2）数的最小因数；（3）数的分解式中某素数的最高次幂；（4）未知数的最小正整数值；（5）一组正整数解和的最小值。使用这种方法的实例很多。例10.（IMO—28）设n2，nxxxf2)(，这里x为整数。若当30nx时，f(x)都是素数，试证对任何0≤x≤n-2，f(x)也都是素数。解：设命题结论不成立，我们就可取使f(x)为合数的最小整数})(,20;min{为合数xfnxxy})(,20;min{为合数xfnxxy。我们通过nyy2的最小素因数p的讨论，将可证明30ny，从而产生矛盾。例11.（IMO—29）设正整数a，b使ab+1整除22ba，试证122abba是完全平方数。解：记122abbak，则正整数k应使方程022kbkaba（1），关于未知数a，b有正整数解。显然ab0，否则由ab≤-1就可以从（1）导出k0。设a0，b0是（1）的使a0+b0最小的一组正整数解，不妨设a0≥b0。固定k与b0，由（1）有)3()2(2000000kbaakbaa，由（2）知0a是整数。若k不是完全平方数，则20bk，故由（3）知00a。注意到000ba，故00a。这就表明0a，0b也是（1）的一组正整数解。易证00aa，故0000baba。这是矛盾的。故k是完全平方数。四.缩小取值范围讨论并缩小变数或式子的取值范围，是解决数论命题常用的方法之一。对数论中有关整数的命题而言，这种方法有着特殊的作用：如能将取值范围确定在一有限区间内，我们就可以用有限个整数逐一进行检验。通过取某些数为模来排除不合要求的剩余类是缩小取值范围的一个重要方法。例12.（IMO—30备选题）设正整数a，b，c，d，m，n满足19892222dcba，2mdcba，其中a，b，c，d的最大者为2n，试求m与n的值。解：由条件不难看出m是奇数。同时可对a+b+c+d的取值范围作出一个估计，而在此范围内可成为2m的数是不多的。事实上，由柯西不等式得9019892dcba。[))(41414141()21212121(22222dcbadcba))(41414141()21212121(22222dcbadcba]，因而m只能从1，3，5，7，9这五个数中选取.再由22222)(dcbadcba22222)(dcbadcba知只能有m=7或9。因而