数学奥赛辅导不定方程.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）=412（1）+，而12（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