不定方程的解法

基本介绍编辑本段不定方程是数论的一个分支，它有着悠久的历史与丰富的内容。所谓不定方程是指解的范围为整数、正整数、有理数或代数整数的方程或方程组，其未知数的个数通常多于方程的个数。古希腊数学家丢番图于三世纪初就研究过若干这类方程，所以不定方程又称丢番图方程，是数论的重要分支学科，也是历史上最活跃的数学领域之一。不定方程的内容十分丰富，与代数数论、几何数论、集合数论等等都有较为密切的联系。1969年，莫德尔较系统地总结了这方面的研究成果。2发展历史编辑本段不定方程是数论中最古老的分支之一。古希腊的丢番图早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程。Diophantus，古代希腊人，被誉为代数学的鼻祖，流传下来关于他的生平事迹并不多。今天我们称整系数的不定方程为「Diophantus方程」，内容主要是探讨其整数解或有理数解。他有三本著作，其中最有名的是《算术》，当中包含了189个问题及其答案，而许多都是不定方程组（变量的个数大于方程的个数）或不定方程式（两个变数以上）。丢番图只考虑正有理数解，而不定方程通常有无穷多解的。研究不定方程要解决三个问题：①判断何时有解。②有解时决定解的个数。③求出所有的解。中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的《张丘建算经》中的百鸡问题标志中国对不定方程理论有了系统研究。秦九韶的大衍求一术将不定方程与同余理论联系起来。百鸡问题说：“鸡翁一，直钱五，鸡母一，直钱三，鸡雏三，直钱一。百钱买百鸡，问鸡翁、母、雏各几何？”。设x，y，z分别表鸡翁、母、雏的个数，则此问题即为不定方程组的非负整数解x，y，z，这是一个三元不定方程组问题。3常见类型编辑本段⑴求不定方程的解；⑵判定不定方程是否有解；⑶判定不定方程的解的个数（有限个还是无限个）。4方程相关编辑本段4.1一次不定方程二元一次不定方程的一般形式为ax+by=c。其中a，b，c是整数，ab≠0。此方程有整数解的充分必要条件是a、b的最大公约数整除c。若a、b互质，即它们的最大公约数为1，（x0，y0）是所给方程的一个解，则此方程的解可表为{(x=x0-bt，y=y0+at）|t为任意整数}。S（≥2）元一次不定方程的一般形式为a1x1+a2x2+…+asxs=n0a1，…，as，n为整数，且a1…as≠0。此方程有整数解的充分必要条件是a1，…，as的最大公约数整除n。埃拉托塞尼筛法产生的素数普遍公式是一次不定方程公元前300年，古希腊数学家欧几里得就发现了数论的本质是素数，他自己证明了有无穷多个素数，公元前250年古希腊数学家埃拉托塞尼发明了一种筛法：一“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。二后来人们将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1d≤√N”。（《基础数论》13页，U杜德利著，上海科技出版社）..三再将二的内容等价转换：“若自然数N不能被不大于（根号）√N的任何素数整除，则N是一个素数”。见（代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页）。四上面这句话的汉字可以等价转换成为用英文字母表达的公式：N=p1m1+a1=p2m2+a2=......=pkmk+ak。⑴其中p1，p2，.....，pk表示顺序素数2，3，5，，，，，。a≠0。即N不能是2m+0，3m+0，5m+0，...，pkm+0形。若NP（k+1）的平方[注：后面的1，2，3，....，k，（k+1）是脚标，由于打印不出来，凡字母后面的数字或者i与k都是脚标]，则N是一个素数。五可以把（1）等价转换成为用同余式组表示：N≡a1(modp1），N≡a2(modp2），.....，N≡ak(modpk）。⑵例如，29，29不能够被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。29≡1(mod2），29≡2(mod3），29≡4(mod5）。29小于7的平方49，所以29是一个素数。以后平方用“*”表示，即：㎡=m*。由于⑵的模p1，p2，....，pk两两互素，根据孙子定理（中国剩余定理）知，⑵在p1p2.....pk范围内有唯一解。例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，3*）区间的全部素数。k=2时，N=2m+1=3m+1，解得N=7，13，19；N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）区间的全部素数。k=3时，---------------------|5m+1-|-5m+2-|5m+3,|5m+4.|---------------------|---------|----------|--------|---------|n=2m+1=3m+1=|--31----|--7,37-|-13,43|--19----|n=2m+1=3m+2=|-11,41-|-17,47-|--23---|---29---|------------------------------------------------------------求得了（7，7*）区间的全部素数。仿此下去可以求得任意大的数以内的全部素数。4.2多元一次不定方程关于整数多元一次不定方程，可以有矩阵解法、程序设计等相关方法辅助求解。4.3二次不定方程二元二次不定方程本质上可以归结为求二次曲线（即圆锥曲线）的有理点或整点问题。一类特殊的二次不定方程是x^2+y^2=z^2，其正整数解称商高数或勾股数或毕达哥拉斯数，中国《周髀算经》中有“勾广三，股修四，经隅五”之说，已经知道(3，4，5）是一个解。刘徽在注《九章算术》中又给出了（5，12，13），（8，15，17），(7，24，25），（20，21，29）几组勾股数。它的全部正整数解已在16世纪前得到。这类方程本质上就是求椭圆上的有理点。另一类特殊的二次不定方程是所谓佩尔方程x2－Dy2=1，D是非平方的正整数。利用连分数理论知此方程永远有解。这类方程就是求双曲线上的有理点。最后一类就是平方剩余问题，即求x^2-py=q的整数解，用高斯的同余理论来描述，就是求x^2≡q(modp)的剩余类解。高斯发现的著名二次互反律给出了次方程是否有解的判定方法。这类方程就相当于求抛物线上的整点。圆锥曲线对应的不定方程求解可以看做椭圆曲线算术性质的一种特例。4.4高次不定方程对高于二次的不定方程，相当复杂。当n2时，x^n+y^n=z^n没有非平凡的整数解，即著名的费马大定理，历经3个世纪，已由英国数学家安德鲁·维尔斯证明完全可以成立。有一些高次方程同样无解：4.5多元高次不定方程多元高次不定方程没有一般的解法，任何一种解法都只能解决一些特殊的不定方程，如利用二次域来讨论一些特殊的不定方程的整数解．常用的解法⑴代数恒等变形：如因式分解、配方、换元等；⑵不等式估算法：利用不等式等方法，确定出方程中某些变量的范围，进而求解；⑶同余法：对等式两边取特殊的模（如奇偶分析），缩小变量的范围或性质，得出不定方程的整数解或判定其无解；⑷构造法：构造出符合要求的特解，或构造一个求解的递推式，证明方程有无穷多解；⑸无穷递推法。4.6特殊求解方法一二元一次不定方程（组）定义1.形如ax+by=c(a，b，c∈Z，a，b不同时为零）的方程称为二元一次不定方程。定理1.方程ax+by=c有解的充要是(a,b)|c；定理2.若（a,b)=1，且x_0，y_0为ax+by=c的一个解，则方程的一切解都可以表示成|||||定理3.n元一次不定方程a_1x_1+a_2x_2+…+a_nx_n=c，（a_1，a_2，…a_n，c∈N）有解的充要条件是：（a_1，a_2，…a_n)|c.方法与技巧：1．解二元一次不定方程通常先判定方程有无解。若有解，可先求ax+by=c一个特解，从而写出通解。当不定方程系数不大时，有时可以通过观察法求得其解，即引入变量，逐渐减小系数，直到容易得其特解为止；2．解n元一次不定方程a_1x_1+a_2x_2+…+a_nx_n=c时，可先顺次求出(a_1，a_2)=d_2，（d_2，a_3)=d_3，…，（d_(n-1），a_n)=d_n.若c不能被d_n整除，则方程无解；若c可以被d_n整除，则方程有解，作方程组：|||||求出最后一个方程的一切解，然后把t_(n-1)的每一个值代入倒数第二个方程，求出它的一切解，这样下去即可得方程的一切解。3．m个n元一次不定方程组成的方程组，其中mn，可以消去m-1个未知数，从而消去了m-1个不定方程，将方程组转化为一个n-m+1元的一次不定方程。二高次不定方程（组）及其解法1．因式分解法：对方程的一边进行因式分解，另一边作质因式分解，然后对比两边，转而求解若干个方程组；2．同余法：如果不定方程F(x_1，x_2，…，x_n)=0有整数解，则对于任意m∈N，其整数解(x_1，x_2，…，x_n)满足F(x_1，x_2，…，x_n)≡0(modm），利用这一条件，同余可以作为探究不定方程整数解的一块试金石；3．不等式估计法：利用不等式工具确定不定方程中某些字母的范围，再分别求解；4．无限递降法：若关于正整数n的命题P(n)对某些正整数成立，设n_0是使P(n)成立的最小正整数，可以推出：存在正整数n，使得n_1n_0成立，适合证明不定方程无正整数解。方法与技巧：1．因式分解法是不定方程中最基本的方法，其理论基础是整数的唯一分解定理，分解法作为解题的一种手段，没有因定的程序可循，应具体的例子中才能有深刻地体会；2．同余法主要用于证明方程无解或导出有解的必要条件，为进一步求解或求证作准备。同余的关键是选择适当的模，它需要经过多次尝试；3．不等式估计法主要针对方程有整数解，则必然有实数解，当方程的实数解为一个有界集，则着眼于一个有限范围内的整数解至多有有限个，逐一检验，求出全部解；若方程的实数解是无界的，则着眼于整数，利用整数的各种性质产生适用的不等式；4．无限递降法论证的核心是设法构造出方程的新解，使得它比已选择的解“严格地小”，由此产生矛盾。三特殊的不定方程1．利用分解法求不定方程ax+by=cxy(abc≠0）整数解的基本思路：将ax+by=cxy转化为(x-a)(cy-b)=ab后，若ab可分解为ab=a_1b_1=a_2b_2=…=a_ib_i∈Z，则解的一般形式为，||||再取舍得其整数解；2．定义2：形如的x^2+y^2=z^2的方程叫做勾股数方程，这里x，y，z为正整数。对于方程x^2+y^2=z^2，如果(x，y)=d，则d^2|z^2，从而只需讨论(x，y)=1的情形，此时易知x，y，z两两互素，这种两两互素的正整数组叫方程的本原解。定理3.勾股数方程满足条件2|y的一切解可表示为：||其中ab0，（a，b)=1，且a，b为一奇一偶。推论：勾股数方程的全部正整数解（x，y的顺序不加区别）可表示为：||其中ab0是互质的奇偶性不同的一对正整数，d是一个整数。勾股数不定方程的整数解的问题主要依据定理来解决。3．定义3.方程x^2-dy^2=±1，±4(x，y∈Z，正整数d不是平方数）是x^2-dy^2=c的一种特殊情况，称为沛尔（Pell）方程。这种二元二次方程比较复杂，它们本质上归结为双曲线方程x^2-dy^2=c的研究，其中c，d都是整数，d0且非平方数，而c≠0。它主要用于证明问题有无数多个整数解。对于具体的d可用尝试法求出一组成正整数解。如果上述pell方程有正整数解（x，y），则称使x+yd^0.5的最小的正整数解为它的最小解。定理4.Pell方程x^2-dy^2=1(x，y∈Z，正整数d不是平方数）必有正整数解，且若设它的最小解为（x_1，y_1），则它的全部解可以表示成：||||上面的公式也可以写成以下几种形式：||定理5.Pell方程x^2-dy^2=-1(x，y∈Z，正整数d不是平方数）要么无正整数解，要么有无穷多组正整数解，且在后一种情况下，设它的最小解为（