数学奥赛辅导不定方程.doc

数学奥赛辅导 第四讲
不定方程
知识、方法、技能
不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.不定方程是数论的一个重要课题，也是一个非常困难和复杂的课题.
Ⅰ. 几类不定方程
1．一次不定方程
在不定方程和不定方程组中，最简单的不定方程是整系数方程

通常称之为二元一次不定方程.
一次不定方程解的情况有如下定理.
定理一：二元一次不定方程
为整数.
有整数解的充分必要条件是. ①
【证】必要性 设是①的解，则有.
设
充分性 设且，有.因，则存在，使得
，
于是有
所以是①的解.
显然，当方程①有解时，. 则用去除①的两端有
②
此时，且②与①同解，因此，我们只须讨论时方程①的解.
定理二：若为①之一解，则方程①全部解为
. （t为整数）.
【证】设为①的一解，则有
③
设是①的任一解. 用①式减去③式有
.
因为于是有，即从而有将此结果代入上式得.即方程任一解都可以表示为为整数）.
反之，若是①的解，则容易验证均是①的解. 从而定理得证.
2．沛尔方程
二元二次不定方程本质上归结为（双曲型）方程
④
的研究，其中都是整数，且非平方数，而.方程④的一个特殊情形
　　　　　⑤
最为重要，也最为基础，这称为沛尔方程. 能够证明（本书不予讨论）方程⑤一定有无穷多组正整数解；又设是⑤的正整数解中使最小的解，则⑤的全部正整数解由
⑥
给出.（n=1，2，…）
读者不难由⑥导出满足的线性递推关系
⑦
沛尔方程在数学竞赛中主要用于证明问题有无穷多个解，实际上对具体的d，可用尝试法求出⑤的一组正整数解（因为方程一定有解！），无论是否为基本解，由⑥均给出方程的无穷多组解.
3．勾股方程
这是一个相当特殊的三元二次不定方程，它有鲜明的几何意义，并应用广泛.
这里只讨论勾股方程的正整数解，由方程不难看出，如果，则，从而，这样可在勾股方程的两边约去. 所以我们只需讨论满足的解，此时易知实际上两两互素. 这种两两互素的正整数解称为方程的本原解，也称为本原的勾股数.
将方程模4，并注意，可知一奇一偶，无妨设为偶数，下面的结果给出了勾股方程的全部本原解.
定理三：方程满足，的全部正整数解可表为
，
其中，是满足一奇一偶，且的任意整数.
证明从略.
4．不定方程
这是个四元二次方程，此方程也有不少用处，其全部正整数解极易求出：
设，则，其中，故，
所以. 因此方程的正整数解可表示为
都是正整数，且.反过来，易知上述给出的都是解.
也可采用如下便于记忆的推导：
设是既约分数，即. 由于约分后得出，故，同理
Ⅱ. 不定方程一般的求解方法
1．奇偶分析法；
2．特殊模法；
3．不等式法；
4．换元法.
由于不定方程的种类和形式的多样性，其解法也是多种的，上面仅是常用的一般方法.
赛题精讲
例1：求方程的整数解，其中是质数，是大于1的正整数，并证明你所得到的解是全部解. （第37届美国普特南数学竞赛试题）
【解】由和和的对称性，不妨设，即不妨只考试方程①的整数解，，仍如题设）.
显然，①中不能全为奇质数，且，故中恰有一个等于偶质数2.
（1）若，此时设如果是偶数，则
为正整数）不能被4整除，而能被4整除，①不成立，故只能取奇数值.于是，此时，，故只含素因子2.
设，则
由于与的奇偶性相同，即为奇数，故只能等于1，这样一来，从而方程①，得，这与题设矛盾，故①中不能取值2.
（2）若，则由①得，故只含素因子2.设为奇数),则
,若,则是大于1的奇数,上式不能成立,故,即这时由方程①得

若是奇数，显然上式不成立；若是偶数，则上式右边等于－4+8（－1）－…=－4[1－2（－1）+…]，而[1－2（－1）+…]不是偶数，因而只能等于－1，故显然时此式不成立，于是，进而由得=3，从而方程①的解只能是
综上，考察到对称性，原方程恰有两组解：

例2：试证：当时，不存在个连续自然数，使得它们的平方和是完全平方数.
【证明】设是非负整数.假若结论不成立,即存在使
即
①
记 则
当时，分别由① 和令，代入①得

即
把代入后将分别得到但这是不可能的，故.
当时,由①得 ②
若则由②知,，由于的任意性，所以只能有因此要使成立,只能,于是由③知有,这是不可能的,故同理可证
若,则由②可得,这是不可能的,故综上,命题得证.
【评述】时,有
例3：试求所有的正整数，使方程有正整数解.
(1987年中国国家队选拔考试题)
【解】设为其正整数解,由对称性,不妨设.显然，故但，因而

故
于是

易知（否则，若，则上式端不小于4，右端不大于3，矛盾），这样上式转化为此式只有时才能成立.当注意到，即因此，只能是或时不合）.把所得的解代入原方程就可得或1.
例4：在无限方格纸（方格的边长为1）上仅可沿网格线作划分，求证：对于任一整数，可以划分出这样的矩形，它的面积大于，而从其中不可能再分出面积等于的矩形. (1985年第19届全苏数学竞赛试题)
【证明】设某一矩形边长为不失一般性,设.由题意，、应满足：
但由于知,于是只要证明不等式组：
①
有正整数解就可以了.
由于对任一正整数，必定有，所以可分下面四种情形讨论：
（1）当时，①有解
（2）当时，①有解
（3）当时，①有解
（4）当时，①有解
例5：求方程的所有整数解.
(1986年第12届全国数学竞赛试题)
【解】因为
若令则原方程可化为
由此可看出且是3原倍数.设其中是正整数，则，于是且是3的倍数.设（其中，则再由知.此时，，故可由方程组
解得原方程的整数解
例6．求方程的所有正整数解.
(1983年加拿大数学竞赛题)
【解】由对称性,不妨设.显然，于是
即于是由知，
（1）时，
（2）时，无解；
（3）时，无解；
（4）时，无解；
于是原方程只有一组正整数解：，
【评述】建立“递推关系”也是解竞赛题的一种常用技巧.对于不定方程,如果能建立未知数的某种递推关系,并且再知一组简单解(相当于递推数列中的初始值),那么,就可以通过递推关系得到所有解,请看例7.
例7：确定的最大值.其中、为整数，且满足：
、 ①
（第22届IMO试题）
【解】只需找到适合①的最大、，由可得因、为不大于1981的正整数，因此有，当且仅当时等号成立.
显然是①的一组解.当时，，且有（递推关系）：

于是，若（）是①的一组解，那么（）也是①的一组解.由于，则可从（）出发，递降得到（1，1）.反之,亦成立.即由解（1，1）出发，利用从（）→（）可得到满足的全部解.即
（1，1）→（1，2）→（2，3）→（3，5）→（5，8）→（13，21）→（21，34）→（34，35）→（55，89）→（89，144）→（144，233）→（233，377）→（377，610）→（610，987）→（987，1579）.
因此,所求的的最大值为
例8：证明：有无穷多个正整数使得是完全平方数.
【证明】因方程 ① 有正整数解，因此有无穷多组正整数解.任取一组解则
将上式两边同乘以，得故所以是一个平方数，即取得出无穷多个符合要求的
例9：设为正整数，证明：不是素数.
【证明】由,得出其中都是正整数.
因此不是素数.
例10：证明：不定方程 ①
仅有一组正整数解及
【证明】首先，将①模化简，得故是奇数.将①分解为
易知必须是偶数，否则上式两边的奇偶性不同，类似地，将①变形为
可见也是偶数.
现在记则由①得 ②
因是偶数，故与的最大公约数是2，又显然有，由这些及②推出，必须
这意味着故，即，所以及
【评述】方程①是著名的卡特郎（Catalan）猜想的特殊情形.卡特郎猜想32与23是仅有的一对差为1的正整数方幕,即不定方程 ③
只有一组正整数解及
例11：证明：不定方程 ①
没有正整数解.
【证明】采用反证法，设①有正整数解，我们在所有这样的解中选 取一组使最小的解.论证的想法是由此构造出另一组解，使得，由于已选择为最小，这就导出矛盾.
首先,此时必有,因设而,则由①知，即所以）也是①的一组正整数解，但，这和的选取相违.
将①改写为
由于，故于是是一组本源的勾股数.由定理三知，存在整数一奇一偶，使得（不妨设为偶数）
②
由及知，是奇数，是偶数.再应用上述定理，存在整数一奇一偶，使得 .
由②得到即
因易知两两互素，上式表明它们的积是整数的平方，故存在正整数使得从而
于是我们得出了①的一组正整数解但和的最小性矛盾.
【评述1】由例10立即推出,费马方程当时没有正整数解.
【评述2】例11的证明方法,称为无穷递推法,这是费马首先提出的一个重要方法.
采用无穷递降法证明不定方程无正整数解（满足某种限制的解）的主要步骤是：从相反的结论出发，假设存在一组正整数解，设法造出这个方程的另一个正整数解，而新的解比原来的解“严格地小”.这里所谓严格的小，是指某一个与解有关的，取正整数的量严格递减.如上述过程可以无限地进行下去，则由于严格递减的正整数列只有有限多项，两者产生矛盾.
有一些不定方程需要应用稍深入的同余知识：二次剩余（或称平方剩余）.这里只介绍一个最基本、最常用的结果：
引理 设是型的素数，则 ③
没有整数解.
换句话说,对于素数的素因子或者是2，或者
证明颇简单.假定有满足③，则 故但 ，于是由费马小定理知，进而即，得，这不可能.
例12：设是型的素数，是正整数且若可以表示为两个素数的平方和，即存在整数使得 ① 则中的幂次是偶数.
【证明】首先证明均被整除.假设不然，可设 ，则有整数，使以乘①的两边，再模，得出（注意到）

因，这与引理矛盾，故设则我们证明，即中的幂次是偶数.
记则都是整数，且 由①得
假设，则由上述相同的论证表明，导出矛盾，这就证明了本题的断言.
【评述】例12的论证表明：如设是型的素数，若有整数使得 则均被整除.
例13：证明：方程 ①
没有整数解.
【证明】首先,若是偶数，将①模4得，此不可能.若是奇数，当时，由①得，仍不可能.故，于是，仍不可能.故，于是，因此必有一个型的素因子，将①变形为
①
并模，得.由例12评述可知，必有即，这不可能.故方程①没有整数解.
【评述1】上面的论证中，先用同余导出了（有解的）某些必要条件，目的是为了使①的右边产生型的素因子，以应用引理或例12评述中的事实.
【评述2】任一个的整数必有型的素因子.这一简单的结论在这一类论证中最为有用.
12 / 12