浅谈不定方程的解法毕业论文

多元一次不定方程的解法：n元一次不定方程就是形如∑aixi = C的不定方程，与二元一次方程最大的区别是，系数增多，未知数增多。求取变得更复杂。但事实上，多元一次方程可以通过消元法来变换成已经完美解决的二元一次方程。举例: 3x+4y+6z  = 7，为了将3元变2元，这里我们做一个假设，设4y+6z=w，由不定方程的性质可知 2 | w,即w是2的倍数，由此我们不妨假设4y+6z=2w，将2w回代到方程中即得3x+2w=7。解此不定方程得x = 1 , w = 2。再将w = 2 回代得到4y+6z=4，解此不定方程，得y = 2, z = 2，自此满足方程的一组特解为(1 , -2 , 2)。使用消元法可以很轻松地求得一组满足方程的特解，通解就没有那么容易了。还是刚才的例子，我们知道X = 1 + 2n,w = 2 - 3n 是 3x + 2w = 7的通解。把w = 2 - 3n 代入到 4y + 6z = 2w(1) 中，得 4y + 6z = 4 - 6n 。我们知道 4 y + 6 z = 2 (2)的特解为 y'0 = -1 ,z'0 = 1。由于(2)式两边乘以 w即得(1)，所以y0 = -w ,z0 = w，由特解马上可以得到通解y  = - 2 + 3n + 3n' , z = 2 - 3n -  2n'所以此不定方程的通解为 X = 1 + 2n , y = - 2 + 3n + 3n' , Z = 2 - 3n - 2n' , n , n'为任意整数。由此可见，此不定方程的通解可以通过取向量N = (n,n')不同的值来得到。不失一般性地，可以通过上述的办法构造成一个形如Xn = ∑λiti + q 的通项式。（相关的结论请参看相关的论文这里不再赘述）

定理1:现有不定方程a * x + b * y = c，a,b,c均为整数，若d=GCD(a,b)(GCD表示取a,b的最大公约数),d|c(d整除c)，那么二元一次不定方程必定有解，且有无数解。

例子:3x + 4y = 5（随便定的）有解，因为1= GCD(3,4) ,1 | 5。易知当x=-5，y=5时，即得整数解。

这定理相关的数学证明就参看数论相关的资料，这里只阐述结论。（下同）

定理2:若不定方程a * x + b * y = c有整数解，则通解的形式必定为X=x0 + b/d * n, Y = y0 - a/d * n。其中x0,y0为不定方程的一个整数解。

引用上面的例子，易知其通解为X=-5+4n,Y = 5+3n。n为整数

定理1给出不定方程解的一个判定方法，而定理2则给出了不定方程通解的形式。

虽然上述结论，已经似乎很完美，但事实上还有一个重要的地方没有解决，就是如何快速求解不定方程。暴力破解当然不可取，因为这会极其浪费计算机资源。而且当a和b足够大时，几乎是求解不了。事实上解不定方程，有一个强劲的解法，叫扩展欧几里德算法，也叫辗转相除法，使用欧几里德算法，时间复杂度为O(logN)的。而即使优化过的暴力法也至少需要O(n)。

————————————————

版权声明：本文为CSDN博主「天蒙光」的原创文章，遵循CC BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：

解不定方程的步骤是：移项，合并同类项，把未知数系数化为1。

在解不定方程之前，首先不得不提到的就是普通方程，相信普通方程大家都比较熟悉。例如，经常遇到的一元一次方程2x+5=140，1个未知数给1个式子，通过移项可以解出x的值。又例如二元一次方程组，2个未知数对应2个式子，通过代入消元法或加减消元法可以将方程的解求出来。

特殊情况

假如给一个方程2x+3y=5，2个未知数1个方程，如果想去求解这个方程，就会发现解是不固定的，可以是x=1，y=1；或者x=，y=；又或者x=4，y=-1，对于这类未知数个数大于独立方程个数的方程，称其为不定方程。既然不定方程在实数范围内有无穷多个解，那该怎么求解。

一般情况下，在考试里求解不定方程是有限定条件的。通常都会把所求未知数限定在正整数范围内，这样不定方程由原来的无穷多个解就变成有限个解了。通过题干要求，当发现x和y都在正整数范围内，那最先想到的解法就是从x=1，x=2……代入求解，但是这种方法显然比较费时费力，而更省时的方法，为了缩小尝试范围，可以寻找未知数的数字特征。