例5. 设)(n r 为n 分别除以1,2,┅,n 所得的余数之和。证明存在无穷多个正整数n ,使得)1()(-=n r n r 。
解:把n 除以k 的余数记为k r ,则有k k n n r k ??????-=。故可得)(n r r 的表达式∑∑===??????-==n k n k k n k k n n r n r 21
1)()( ∑∑==??????-=??????-=n k n
k k k k n n k k n n r 121)(。由此易得∑-=??????---=-1121)1()1(n k k k n n n r 。则∑-=??????--??????--=--111()1()1()(n k k n k n n n r n r ∑-=??????--??????--=1
1)1()1()1n k k k n k n n ,因此,)1()(-=n r n r 等价于∑-=??????--??????=-11)1()1(n k k k n k n n 。注意到???/=??????--??????n k n k k n k n |,0|,11 ???/
=??????--???n k n k k n |,0|,11,因此题中的条件等价于n 的所有真因子之和等于n -1。显然,取l n 2=(l 为正整数),则n 的所有真因子之和为n -1,而这样的n 有无穷多个。
例6. 试证对于任给的m 个整数m a a a ,,,21 ,必有)1(,m j s j s ≤<≤,使得)(|1j s s a a a m ++++ ]
解:令i i a a a b +++= 21(m i ,,2,1 =)。若m b b b ,,,21 中有一个数被m 整除,则结论成立。否则,各i b 均不能被m 整除,此时可设)11(-≤≤+=m r r mq b i i i i 。这样,m 个余数m r r r ,,,21 只能从1至m -1这m -1个数中取值,由抽屉原理知,必有)1(,m j k j k ≤<≤,使得j k r r =,于是
)(k j k j q q m b b -=-,故)()(|21j k k k j a a a b b m +++=-++ 取1+=k s 即得到结论。
3. 互素性的条件
当(a ,b )=d >1时,我们总是作如下考虑:令d b b d a a 11,
==,则必有1),(11=b a 。这种互素条件的增置往往对解题有很大作用。
例7. (波兰64—65)设整数a ,b 满足b b a a +=+2232,试证b a -及122++b a 都是完全平方数。
解:b b a a +=+2232变形可得:2)122)((b b a b a =++-,故只要能证一个,则另一个必是。我们在排除了字母取零或相等的情况后,可设d b a b a b a =≠≠),(,,0,。这时令d b b d a a 11,==,
1),(11=b a ,从而方程变为21112132db b a da =-+。显然有)(|11b a d -。另一方面又212111(
223d da db b a -=-=- 21212121211)(223db b a d da db b +--=-=,有2111|)(db b a -。注意到1),(),(11111==-b a b b a ,于是有d b a |)(11-。这样就有||11b a d -=。至此已十分容易获得命题的结论了。这里,由a 1与b 1互素导出a 1—b 1与b 1互素,是证明d b a |)(11-的关键。
二. 从特殊到一般
例8. (IMO-18)试求和为1978的正整数之积的最大值。
《
解:我们可通过减少加法运算的次数来选择特例,例如考虑求正整数,,,,21n a a a 满足,
1021=+++a a a n ,10,1021≤=+++n a a a n 使n a a a 21最大。显然,最特殊且最简单的正整数是1。例如取a 1=1,这里由
n n n a a a a a a a )1(2221+<=知乘积不是最大的值。对于某些正整数取2的情况,注意到2+2=4,2×2=4;2+2+2=6=3+3,2×2×2<3×3。我们发现诸a i 中不能取多于两个2。对于a i =5,有2+3=5,2×3>5。因此不如把一个5拆成2与3的和,从而使乘积变大,对于6,7等有类似的结论。这样,我们已大致可确定诸a i 只应取2或3,且2的个数不超过两个。依此估计,由1978=658×3+2+2,即可猜测最大的积为658232?。
例9. (IMO —31备选题)设a ,b 是给定的正整数,现有一机器人沿着一个有n 级的楼梯上下升降,每上升一次恰好上升a 级,每下降一次恰好下降b 级。为使机器人经过若干次上升下降后,可以从地面升到楼梯顶,然后再返回地面,问n 的最小值是多少?
解:为了探讨解法和结论,不妨设b a ≥。我们分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)一组正整数解和的最小值。使用这种方法的实例很多。
例10. (IMO —28)设n >2,n x x x f ++=2)(,这里x 为整数。若当3
0n x ≤≤时,f (x )都是素数,试证对任何0≤x ≤n -2,f (x )也都是素数。
;
解:设命题结论不成立,我们就可取使f (x )为合数的最小整数)(,20;m in{为合数x f n x x y -≤≤=
})(为合数x f 。我们通过n y y ++2的最小素因数p 的讨论,将可证明3
0n y ≤≤,从而产生矛盾。 例11. (IMO —29)设正整数a ,b 使ab +1整除2
2b a +,试证12
2++ab b a 是完全平方数。 解:记1
22++=ab b a k ,则正整数k 应使方程022=-+-k b kab a (1),关于未知数a ,b 有正整数解。显然ab >0,否则由ab ≤-1就可以从(1)导出k <0。设a 0,b 0是(1)的使a 0+ b 0最小的一组正整数解,不妨设a 0≥b 0。固定k 与b 0,由(1)有???-='='+)3()2(200000
0k b a a kb a a ,由(2)知0
a '是整数。若k 不是完全平方数,则20
b k ≠,故由(3)知00
≠'a 。注意到000>'b a ,故00>'a 。这就表明0a ',0b 也是(1)的一组正整数解。易证00
a a <',故0000
b a b a +<+'。这是矛盾的。故k 是完全平方数。 四. 缩小取值范围
讨论并缩小变数或式子的取值范围,是解决数论命题常用的方法之一。对数论中有关整数的命题而言,这种方法有着特殊的作用:如能将取值范围确定在一有限区间内,我们就可以用有限个整数逐一进行检验。
通过取某些数为模来排除不合要求的剩余类是缩小取值范围的一个重要方法。
例12. (IMO —30备选题)设正整数a ,b ,c ,d ,m ,n 满足19892222=+++d
c b a ,2m
d c b a =+++,其中a ,b ,c ,d 的最大者为2n ,试求m 与n 的值。
(
解:由条件不难看出m 是奇数。同时可对a +b +c +d 的取值范围作出一个估计,而在此范围内可成为2m 的数是不多的。事实上,由柯西不等式得9019892<≤+++d c b a 。[)(4
1414141()21212121
(2d c b a +++≤+++ ))(4
1414141()2122222d c b a d ++++++≤],因而m 只能从1,3,5,7,9这五个数中选取.再由2222)(d c b a d c b a +++>+++
22222)d c b a d +++>+知只能有m =7或9。因而只要证明492≠m ,即可确定812=m ,进而252=n 。这里,我
们主要是利用已知的重要不等式来确定取值范围。
例13. (IMO —19)设a ,b 是正整数,2
2b a +除以a +b 时,商为q ,余数为r 。试求所有的数偶a 与b ,
使得19972=+r q 。 解:由19972
=+r q ,可得估计q ≤44。于是452
2<++b a b a 。但q 取得较小值时,由19972=+r q 就使r 增大,进而由r 使得q 减小。这种q 与a +b 之间的制约关系表明q 不能太小。依此思路,我们将可由q ≤43导出462
2≥++b
a b a 的矛盾,从而确定了q =44。据此很容易求出a 与b 了。
五. 构造法
构造法常用来作存在性的证明。我们熟知有欧几里德关于素数个数无限性的证明就是一个典型的例子。另一个重要的例子是关于“存在n 个相继自然数都是合数”的证明:对任意的n ,令N =(n +1)!,则相继的自然数N +2,N +3,…,N +n +1 (*),是n 个合数。我们还可以举出许多例子,如(1)试证存在无限多个正整数a ,使得对每一个自然数n ,数a n +2都是合数。(2)试证存在无限多个正整数n ,使6n -1与6n +1同为合数。(3)试证对任何自然数n >3,必存在素数p ,满足n
1≥+=k k n ,就证明了(2);取p 为n !-1的最小素因数,也可证明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=m
p ,则显然有(j +1)|(N +j ),
因而必有j +1=r p ,1≤r ≤m ,从而m r p p |1+。另一方面,由j +1≤n +1知)!1(|+n p r ,故))!1(2(|1++n p r 。于是1))!1(2()(|1+=+-++j n j N p
r 。这是与r p j =+1矛盾的,从而证明了命题。最后还应指出,同一命题的构造方法可以有多种,如例13中也可令1))!1((2++=n N 。