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

定理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……代入求解，但是这种方法显然比较费时费力，而更省时的方法，为了缩小尝试范围，可以寻找未知数的数字特征。