竞赛中的数论问题的思考方法
一. 条件的增设
对于一道数论命题，我们往往要首先排除字母取零值或字母取相等值等“平凡”的情况，这样，利用字母的对称性等条件，往往可以就字母间的大小顺序、整除性、互素性等增置新的条件，从而便于运用各种数论特有手段。 1. 大小顺序条件
与实数范围不同，若整数x，y有大小顺序x 22222例1. （IMO-22）设m，n是不大于1981的自然数，(n?nm?m)?1，试求m?n的最大值。 解：易知当m=n时,m?n?2不是最大值。于是不访设n>m,而令n=m+u1，n>u1≥1，得(m?mu1? 2222(m2?mu1?u1)2?1。同理，又可令m= u1+ u2，m>u2≥1。如此继续下去将得uk+1= uk=1，而ui?1?ui?ui?1，i≤k。 故uk?1,uk,?,u2,u1,m,n是不大于1981的裴波那契数，故m=987，n=1597。 222例2. （匈牙利—1965）怎样的整数a，b，c满足不等式a?b?c?3?ab?3b?2c? @ 解：若直接移项配方，得(a?)?3(?1)?(c?1)?1?0。因为所求的都是整数，所以原不等 222式可以改写为：a?b?c?4?ab?3b?2c，变形为：(a?)?3(?1)?(c?1)?0，从而只 222b22b222b2b2有a=1，b=2，c=1。 2. 整除性条件 对于整数x，y而言，我们可以讨论其整除关系：若x|y，则可令y=tx；若x?y，则可令y=tx+r，0 ?k?结合，就可有更多的特性。 例3. 试证两相继自然数的平方之间不存在自然数a 22 解：在假定了n?a?b?c?d?(n?1)之后，可设 ?n?cdp??,(p,q)?1。（显然p>q）由p，abqp的范围进行估qq的互素性易知必有q|a，q|b。这样，由b>a即得b?a?q。（有了三个不等式，就可对 1q?1pdd(n?1)22计），从而1??。于是将导致矛盾的结果：(n?q)?0。这里，因????2qqqba?qn?q为a，b被q整除，我们由b>a得到的不仅是b≥a+1，而是更强的条件b≥a+q。 k例4. （IMO-25）设奇数a，b，c，d满足0 2222(b?c) 解：不难证明k，m的大小关系k>m。[(a?d)?4ad?(d?a)?4bc?(d?a)?4bc?(c?b)? kmkmkm?(c?b)2?(b?c)2。所以2?2。]d?2?a,c?2?b，代入ad=bc中，有 a(2?a)?b(2?b) （1）， mk22mk22mk?ma)?(b?a)(b?a) 由（1）可得b?2?a?2?b?a。即2b?2a?b?a，2(b?2（2） 已知a，b都是奇数，所以a+b，a-b都是偶数，又(a?b)?(a?b)?2a是奇数的2倍，故b+a，b-a中 ?b?a?2m?1e?b?a?2m?1e必有一个不是4的倍数。由（2）必有?或?。其中，e，f为正整数，且 ?b?a?2f?b?a?2fmef?b?a?2k?m是奇数。[(a?b)?(a?b)?2ef，与（2）比较可得]由于k>m，故ef?b?2a?b?a? 2} k?m2a?b?a?2f。从而e=1，f?b?a?2?b?a?2m?1。考虑前一情况，有?由第二式可得 k?mb?a?2f?2(b?a?2)?b?a?2k?1?ma，故 2m?1?2k?1?ma，所以奇数a=1。对于后一情况，可作类似的讨论。 显然，上述解题思路中有两个技巧：一是用放缩法证明k 的条件。 例5. 设r(n)为n分别除以1，2，┅，n所得的余数之和。证明存在无穷多个正整数n，使得r(n)?r(n?1)。 nn?n??n? 解：把n除以k的余数记为rk，则有rk?n???k。故可得r(n)r的表达式r(n)??rk??(n? k)?n2???k??k?k?1k?1n?1nn?1?n?1??n??n?22?n??n?1?。则 krk??(n???k)?n????k。由此易得r(n?1)?(n?1)???r(n)?r(n?1)?(n?1)?(???????kkk??????kk?1k?1k?1k?1???k?nn?1?n??n?1??n??n?1??1,k|n?n??n?1? ，因此，等价于。注意到r(n)?r(n?1)1)?(n?1)??(????)k(n?1)?(?)k??????????|n?k????k???0,k?k?1?k??k?k?1?k??k?n?1??n?1??1,k|nln?2，因此题中的条件等价于n的所有真因子之和等于n-1。显然，取(l为正整数)，则n??????|n??k??0,k?的所有真因子之和为n-1，而这样的n有无穷多个。 例6. 试证对于任给的m个整数a1,a2,?,am，必有s,j(1?s?j?m)，使得m|(as?as?1???aj) ] 解：令bi?a1?a2???ai（i?1,2,?,m）。若b1,b2,?,bm中有一个数被m整除，则结论成立。否则，各bi均不能被m整除，此时可设bi?mqi?ri(1?ri?m?1)。这样，m个余数r1,r2,?,rm只 能从1至m-1这m-1个数中取值，由抽屉原理知，必有k,j(1?k?j?m)，使得rk?rj，于是 bj?bk?m(qj?qk)，故m|(bj?bk)?(ak?1?ak?2???aj)取s?k?1即得到结论。 3. 互素性的条件 当（a，b）=d>1时，我们总是作如下考虑：令a?a1d,件的增置往往对解题有很大作用。 例7. （波兰64—65）设整数a，b满足2a?a?3b?b，试证a?b及2a?2b?1都是完全平方数。 解：2a?a?3b?b变形可得：(a?b)(2a?2b?1)?b，故只要能证一个，则另一个必是。我们在排除了字母取零或相等的情况后，可设a,b?0,222b?b1d，则必有(a1,b1)?1。这种互素条 22a?b,(a,b)?d。这时令a?a1d,b?b1d， 22?a1?b1?3db12。显然有d|(a1?b1)。另一方面又a1?b1?3db12? 2da1(a1,b1)?1，从而方程变为2da1??2d(222b1?3db12?2da1??2d(a1?b12)?db12，有(a1?b1)|db1。注意到(a1?b1,b1)?(a1,b1)?1，于是有(a1?b1)|d。 这样就有d?|a1?b1|。至此已十分容易获得命题的结论了。这里，由a1与b1互素导出a1—b1与b1互素，是证明(a1?b1)|d的关键。 二. 从特殊到一般 例8. （IMO-18）试求和为1978的正整数之积的最大值。 《 解：我们可通过减少加法运算的次数来选择特例，例如考虑求正整数a1,a2,?,an, 满足a1?a2?? ?an?10,a1?a2???an?10,n?10,使a1a2?an最大。显然，最特殊且最简单的正整数是1。例如取a1=1，这里由 a1a2?an?a2?an?(a2?1)?an知乘积不是最大的值。对于某些正整数取2的情况，注意到2+2=4， 2×2=4；2+2+2=6=3+3，2×2×2<3×3。我们发现诸ai中不能取多于两个2。对于ai=5，有2+3=5，2×3>5。因此不如把一个5拆成2与3的和，从而使乘积变大，对于6，7等有类似的结论。这样，我们已大致可确定诸ai只应取2或3，且2的个数不超过两个。依此估计，由1978=658×3+2+2，即可猜测最大的积为 22?3658。 例9. （IMO—31备选题）设a，b是给定的正整数，现有一机器人沿着一个有n级的楼梯上下升降，每上升一次恰好上升a级，每下降一次恰好下降b级。为使机器人经过若干次上升下降后，可以从地面升到楼梯顶，然后再返回地面，问n的最小值是多少？ 解：为了探讨解法和结论，不妨设a?b。我们分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等。 三. 讨论极端情况 由于整数集具有最大（小）整数原理这一特性，我们往往可以从某种条件下有最大（小）元素出发进行讨论。例如，可考虑：（1）数列中具有某种特点的极端项；（2）数的最小因数；（3）数的分解式中某素数的最高次幂；（4）未知数的最小正整数值；（5）一组正整数解和的最小值。使用这种方法的实例很多。 2例10. （IMO—28）设n>2，f(x)?x?x?n，这里x为整数。若当0?x?n时，f(x)都是素数，试3证对任何0≤x≤n-2，f(x)也都是素数。 ； 解：设命题结论不成立，我们就可取使 f(x)为合数的最小整数 y?min{x;0?x?n?2,f(x)为合数 f(x)为合数}。我们通过y2?y?n的最小素因数p的讨论，将可证明0?y?n，从而产生矛盾。 3a2?b2例11. （IMO—29）设正整数a，b使ab+1整除a?b，试证是完全平方数。 ab?122a2?b222 解：记k?，则正整数k应使方程a?kab?b?k?0 （1），关于未知数a，b有正整 ab?1数解。显然ab>0，否则由ab≤-1就可以从（1）导出k<0。设a0，b0是（1）的使a0+ b0最小的一组正整数解，不妨设a0≥b0。固定k与b0，由（1）有???kb0?a0?a02??b0?k?a0a0(2)(3)?是整数。若k，由（2）知a02??0。注意到a0??0。这就表明a0?b0?0，故a0?，b0也是不是完全平方数，则k?b0，故由（3）知a0??b0?a0?b0。这是矛盾的。故k是完全平方数。 ??a0，故a0（1）的一组正整数解。易证a0四. 缩小取值范围 讨论并缩小变数或式子的取值范围，是解决数论命题常用的方法之一。对数论中有关整数的命题而言，这种方法有着特殊的作用：如能将取值范围确定在一有限区间内，我们就可以用有限个整数逐一进行检验。 通过取某些数为模来排除不合要求的剩余类是缩小取值范围的一个重要方法。 例12. （IMO—30备选题）设正整数a，b，c，d，m，n满足a?b?c?d其中a，b，c，d的最大者为n，试求m与n的值。 ( 2222?1989，a?b?c?d?m2， 2 解：由条件不难看出m是奇数。同时可对a+b+c+d的取值范围作出一个估计，而在此范围内可成为m2的数是不多的。事实上，由柯西不等式得a?b?c?d?21989?90。[(a?121111111b?c?d)2?(? ??)(222444422121111b2?c2?dd)?(???)(a2?b2?c2?d2)]，因而m只能从1，3，5，7，9这五个数中选取.再由(a?b?c?d)?a? 24444 ?d)2?a2?b2?c2?d2知只能有m=7或9。因而只要证明m2?49，即可确定m2?81，进而n2?25。这里，我 们主要是利用已知的重要不等式来确定取值范围。 例13. （IMO—19）设a，b是正整数，a?b除以a+b时，商为q，余数为r。试求所有的数偶a与b， 2使得q?r?1997。 22a2?b2?45。但q取得较小值时，由q2?r?1997 解：由q?r?1997，可得估计q≤44。于是 a?b222就使r增大，进而由r a2?b2?46使得q减小。这种q与a+b之间的制约关系表明q不能太小。依此思路，我们将可由q≤43导出 a?b的矛盾，从而确定了q=44。据此很容易求出a与b了。 五. 构造法 构造法常用来作存在性的证明。我们熟知有欧几里德关于素数个数无限性的证明就是一个典型的例子。另一个重要的例子是关于“存在n个相继自然数都是合数”的证明：对任意的n，令N=(n+1)!，则相继的自然数N+2，N+3，…，N+n+1 （*）,是n个合数。我们还可以举出许多例子，如（1）试证存在无限多个正整数a，使得对每一个自然数n，数n?a都是合数。（2）试证存在无限多个正整数n，使6n-1与6n+1同为合数。（3）试证对任何自然数n>3，必存在素数p，满足n 我们要强调指出前面（*）中的n个数的构造是极有启发性的。首先，其中N的选择还是有迹可寻的：由“n个相继自然数”立即可联想到取N+1，N+2，…，N+n。但N+1不能判定是否为合数，因而应取消，于是立即联想到（*）。为了保证各数是合数，就应要求N同时含有因数2，3，…，n，n+1。这样的构造还为我们提供了解决另一些命题的线索。例如，为证“存在n个相继的自然数，其中仅有一个素数”这一结论，可从数列（1）出发进行分析：设p为大于N+1的最小素数，可以证明：p-n+1，…，p-1，p；除最后一个数p外，都是合数。 例14. （IMO—30）试证对于任何正整数n，存在n个相继的自然数，它们都不是素数的整数幂。 解：我们取N=(2(n+1))!+1，考虑N+j，1≤j≤n。若N+j=(2(n+1))!+j+1=p，则显然有(j+1)|(N+j)， rr?1rr?1|(2(n?1))!。|pm。因而必有j+1=p,1≤r≤m，从而p另一方面，由j+1≤n+1知p|(n?1)!，故pmr?1|(N?j)?(2(n?1))!?j?1。这是与j?1?pr矛盾的，从而证明了命题。最后还应指出，同于是p2一命题的构造方法可以有多种，如例13中也可令N?((n?1)!)?1。
相关推荐：
loading