数论的方法和技巧 04数论中的存在性问题.doc

数论中的存在性问题知识要点与基本方法在数论问题中回答满足一些条件的某对象存在或不存在的问题我们称之为数论存在性问题它与其它数学存在性问题在理论上是一样的，区别是，其内容是数论知识方面的基本方法:解决数论存在性问题没有什么死的方法，也没有什么固定的程式，所用知识是普遍的，采取的方法也是灵活多样的但由于数论存在性问题是数学竞赛中难度较大的，并且又是常见的题型，因此，对其解决的方法我们给出大致的归纳如下：1反证法2数学归纳法3按模分类4高斯函数5试验，猜想，证明6构造法（1）按归纳方式构造（2）用阶乘构造（3）用非十进制记数构造7数论知识的综合运用赛题精讲1关于反证法例1 已知n是已确定的正整数，是使满足的整数r与满足的整数k对应的函数，且当时，恒有证明：存在整数，使恒成立【分析】 因n的大小不知道，函数f的对应关系情况复杂，故很难确定符合条件的m，不妨用反证法证明：若对任何的m，均有，则由和，可知于是，即，又故，同理可得，这与矛盾故，存在整数，使2关于数学归纳法例2 在黑板上依次写出数a1=1，a2，a3，法则如下：如果为自然数且未写出过，则写，否则就写，证明：所有出现在该序列中的完全平方数都是由写在它前面的那个数加3得到的【分析】 关键是根据在黑板上写数的法则，归纳证明：时，继而，考虑平方数被5除的余数特征证明：首先用归纳法证明如下断言：“当时，由1到n的所有自然数全都被写出，且，而对于任何，都必有”当n=5时，依据法则有.假定当时，由1到5m的所有整数均已被写出，且于是，按下来的5个数就只能是，如此即完成了归纳过程进而考虑到平方数被5除的余数只能是4、1和0，又显然出现在序列中的被5除余4，1和0的数，都是通过写在它前面的那个数加3得到的，因此命题得证例3 证明：存在无穷多个合数n，使得是n的倍数证明：只要x与y为不相等的整数，k为自然数，则要证可被n整除，注意到n为合数，可知，只要 则当视，时，就有可被整除于是要成立，只要下面用归纳法证明：对一切自然数t，数都可被整数当时，结论显然假设对时结论成立，则当时，有 前一因子可被2整数，后一因子由归纳假设可知可被整除当时，可被整除从而对一切自然数t，数可被整除存在无穷多个合数n，使得是n的倍数【评注】 注意到，则显然n为合数因此：3关于按模分类按模分类可以实现“大”向“小”，“多”向“少”，“无限”向“有限”，“无序”向“有序”，“不定”向“确定”的转化例4 非常数的正整数无穷数列an满足递推关系或，n=1，2，求证：数列an中至少有一项为合数【分析】本题关键是考察an的取值情况，an的取值由a1确定，但a2可有2个取值，a3可有4个取值，an可有个取值，因此，无法确定an用什么办法可把不定的递推关系转化成确定的递推关系呢？我们相到了“模”因an均为奇数，故按mod 2分类不行，可考虑mod 3证明：由于an是递增数列，不妨设（否则去掉前面若干项即可）(i)若(mod 3)，则，得证(ii)若(mod 3)，a1为质数（若a1为合数已得证）对，有(mod 3)，得证，对，有(mod 3)，从而，对，有(mod 3)，得证，对，有(mod 3)，从而，或者得证，或者(mod 3)若都有(mod 3)则于是，从而应用费马小定理，得(mod a1)于是为合数，得证(iii)若(mod 3)，可类似于(ii)进行讨论4关于高斯函数的应用叫高斯函数，记号x表示不超过x的最大整数如，等等含有记号x的数学问题，一方面因为它是整数，所以经常与数论问题联系在一起，再则x满足不等式，因而借助于不等式又容易使问题得到解决数论问题中有一类是与高斯函数有关的存在性问题，解决是应抓住高斯函数的特殊性解题下面的例子还得注意归纳法的应用例5 设非负整数列a1, a2, , a1999，对于任意的整数i, j，且，有，证明：存在实数x，使得对于n=1，2，1999，有分析与证明：本题是证明存在x，使，根据高斯函数定义，应有 即这个不等式应对n=1，2，1999都成立于是，x应该同时属于1999个区间, ，可以想象出来，如果x存在，则x应为的最大者我们取 这样，只要证明对一切1，2，1999，都有即可，也就是（2）我们采用数学归纳法证明这个不等式当时，式（2）成立设m, n均小于k时，式（2）成立当m, n中较大的一个为k时，有两种情况：（I）n=k，此时设，由已知有由归纳假设，则故式（2）成立（II）m=k，设，由题设，有这最后一步是由归纳假设于是，式（2）成立以上我们证明了式（2）成立，从而，对一连串区, 中，只要x取的最大者，就能满足题目要求例6 证明：对任一个自然数，存在一个无理数，使得对每一个自然数m，(mod k)【分析】 如何考虑结论(mod k)呢？这相当于(mod k)，但是带有取整记号不便于思考应注意到一个事实，如果，则于是，问题转化为是否存在这样的无理数r和，使得能被k整除同时又知道这样一个事实，若与B都是整数，且与rs都能被k整除时，对正整数m，也能被k整除这样，问题又转化为是否存在这样的无理数r和，使得与rs都是整数且能被k整除这使我们想到韦达定理证明：首先证明，当与rs为整数，且能够被k整除时，对所有正整数m，也是整数，且能被k整除设，其中k是正整数，p, q是整数，则即是整数，且能被k整除假设，都是整数且能被k整除，由于则是整数，且能被k整除于是，用数学归纳法完成了证明下面只需证明，存在这样的r和s，其中r是无理数，s满足，和rs是整数，且能被k整除，为此，考虑方程如果r, s存在，且，则必须满足不等式组 即 显然，对任一自然数，这样的整数q, p是存在的为使r是无理数，只要不是完全平方数即可为此选择，则当时，与矛盾，不符合题目要求当时，若是完全平方数，设，则，有由于与具有相同的奇偶性，所以不存在两个不同的偶数之积为4即不是完全平方数从而不是完全平方数，这时r就是无理数此时，则(mod k)5关于试验，猜想，证明的存在性问题例7 记求证：存在无穷多个正整数n，使I1，I2，In除以n给出互不相同的余数试验：In：1，11，111，1111，2不符合；3除以I1，I2，I3的余数分别是1，2，0；4，5，6，7，8均不符合；9除以I1I9的余数分别是18及0；10，11也非所求但12以后的试算就变得复杂，甚至不可能，停止回顾我们试算的结果，可以作出猜想：，N*证明：(i)对r的归纳法可证明，但（留给读者）(ii)用反证法证明I1，I2，In是mod n的完全剩余类若有，使(mod ，则由，及(10, 知即存在正整数，使令k为最小的这种数，设，（规定I0=0），又，于是，有，由(i)知但，故此与矛盾例8 证明：存在无穷多个自然数n，使得，试验，显然，从2开始试算，且再往下试验，如果再继续试验就麻烦了，不妨思考以上成立的两个数2和66可以写成经检验，这是因为，而于是因又有，由以上试验可以猜想出，当且时，且下面我们证明这个结论，这就把讨论存在性问题转化为一个结论确定的论证性问题证明：显然，假设存在N，使得且由可知，由可知，存在N，使得其中，N于是对此式两边同乘以2，有由于，则，t为奇数，N即有于是，当，时，必有且因此，由可生成，等等如此下去，可以得到无穷多个符合题目要求的自然数n6构造法首先指出的是，构造的思索过程，实如同摸着石头过河，走一步看一步，通过不断的修正“凑”出符合要求的对象（1）按归纳方式构造例9 证明，对任意N，存在一个由n个整数构成的集合，使得对中的任意两个不同的数a，b，均有证明：我们对n采用归纳的构造当时，取1，2即可设时，存在含k个元素的集合a1，a2，ak满足条件，即对任意，均有令A=a1ak，考虑如下的个数A，A+a1，A+a2，A+ak构成集合，则容易验证满足题中的条件【评注】上述归纳的关键是令A=a1ak，选集合A，A+a1，A+a2，A+ak例10 对任意，证明，存在n个不同的正整数a1，a2，a3，an使得 ，i，j=1，2，n)证明：用归纳方式构造当时，取a1=1，a2=2，即可假设已有n个正整数a1a2an！符合要求，则个数an！，an！+a1，an！+a2，an！+an符合要求事实上 (i=1，2，n)又不妨设，(i, j=1，2，n)，则（归纳假设），且，所以N+（2）用阶乘构造例11 证明：可把正整数集N+分拆成两个子集A，B，使得A中任3个数都不成等差数列，而且不存在由B中无穷多个数构成的等差数列证明：令N+，若B中含有首项为a1，公差为d的无限长等差数列，则此数列中的一项与所设矛盾，故B中不会无穷多项组成的等差数列又对任意正整数，有所以，A中任3数不成等差数列（3）采用非十进制记数构造例12 证明：可以用4种颜色对正整数1，2，2000染色，使它不会有由7个同色数组成的等差数列证明：问题等价于把集合1，2，2000分折成4个非空子集M1，M2，M3，M4，使得，因为，所以，中的每个数都可以表示成至多4位的7进制数(abcd)7这里a，b，c，d(0, 1, 2, , 6)设，i=1，2，3，4对任意，由于每个7进制正整数末3位数上至少有1，2，3，4中的一个数字未出现，例如x的末3位数中未出现4，则，所以，下证：集合Ai(i=1, 2, 3, 4)中不含由7项构成的等差数列反设某个Ai中含有由7项构成的等差数列：a, a+d, , a+6d(a为首项，d为公差)若，仿上可得到这个等差数列中必有一项，它的7进制表示中从右数的第三位数字为i，矛盾若，则，矛盾综上证得集合Ai(i=1, 2, 3, 4)中任意7个数不成等差数列，最后，令，得到符合要求的分拆7关于数论知识的综合运用例13 确定是否存在满足下列条件的正整数n，n恰好能够被2000个互不相同的质数整除，且能够被n整除【分析】 本题是数学归纳法，整除知识，代数变形的综合运用由于题目中所要确定的n，是恰好可被2000个互不相互的质数整除，故可考虑用数学归纳法证明一个更一般的命题证明：先证明一个引理引理 对于每一个整数，存在一个质数p满足，但p不能整除.证：假设对某个，引理不成立，则的每一个质因子都要整除，而恒等式说明能够整除的唯一质数是3，换言之，是3的方幂，又从假设有3整除，即是3的倍数，也是3的倍数，于是能够被3整除，但不能被9整除，故得恰等于3另一方面，由知，矛盾，从而引理得证按下来证明一个更一般的命题：“对于每一个自然数k，一定存在一个自然数n满足 ，且n恰好能够被k个互不相同的质数整除”当时，即可使命题成立假设当，时，命题成立当时，因为，n可以写成，)的形式，则n必为奇数，且利用恒等式 可知 根据上面引理，存在一个奇质数p满足但p不能整除，于是，自然数，即满足命题对于的要求，归纳法完成例14 （1）正整数p