数论的方法和技巧 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除以I1～I9的余数分别是1～8及0；10，11也非所求．但12以后的试算就变得复杂，甚至不可能，停止．回顾我们试算的结果，可以作出猜想：
，N*
证明：
(i)对r的归纳法可证明，但（留给读者）
(ii)用反证法证明I1，I2，…，In是mod n的完全剩余类．
若有，使(mod ，则由，及(10, 知
即存在正整数，使．令k为最小的这种数，设，
∵，（规定I0=0），又，
∴
于是，有，，
由(i)知．但，故．此与矛盾．
例8 证明：存在无穷多个自然数n，使得，．
试验，显然，，∴从2开始试算．
，
，，
且
再往下试验，
，，
如果再继续试验就麻烦了，不妨思考以上成立的两个数2和6．
6可以写成
经检验，
这是因为，，而

于是
因
又有，
由以上试验可以猜想出，当且时，
，且
下面我们证明这个结论，这就把讨论存在性问题转化为一个结论确定的论证性问题．
证明：显然，，
假设存在N，使得且
由可知，，
由可知，存在N，使得
其中，
，N
于是
对此式两边同乘以2，有
由于，，则，t为奇数．
，N
即有
于是，当，，，时，必有
且
因此，由可生成，，，…等等．如此下去，可以得到无穷多个符合题目要求的自然数n．

6．构造法
首先指出的是，构造的思索过程，实如同摸着石头过河，走一步看一步，通过不断的修正“凑”出符合要求的对象．
（1）按归纳方式构造
例9 证明，对任意N，，存在一个由n个整数构成的集合，使得对中的任意两个不同的数a，b，均有．
证明：我们对n采用归纳的构造
当时，取{1，2}即可
设时，存在含k个元素的集合{a1，a2，…，ak}
满足条件，即对任意，均有
令A=a1…ak，考虑如下的个数
A，A+a1，A+a2，…，A+ak
构成集合，则容易验证满足题中的条件．
【评注】上述归纳的关键是令A=a1…ak，选集合{A，A+a1，A+a2，…，A+ak}
例10 对任意，证明，存在n个不同的正整数a1，a2，a3，…，an使得
，i，j=1，2，…，n)
证明：用归纳方式构造
当时，取a1=1，a2=2，即可
假设已有n个正整数a1<a2<…<an！符合要求，则个数
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，q，r，a满足，且r是素数，p，q互素．证明：p，q中有一个是完全平方数；（2）是否存在素数p，使得是完全平方数．
解：（1）设，，，其中pi, qj, ah均为素数，且(pi, qj)=1，则有

由于r是素数，则p，q中不被r整除的那个数一定是完全平方数．
（2）设
当时，则，不可能，
当时，设，由于，所以，设，则有，
即
由于p是素数，，，由（1）可知或
若，则．由于，则，而，矛盾．
若，则，于是，，且，，所以，有，
若，则，矛盾．
若，则，，，，于是，，不是完全平方数．因此，不存在正整数p，使得是完全平方数．
10