二元一次不定方程的解法

Question

如题所述

Answer 1

定理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 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/uniqueleion/article/details/81280156