我们现在还有一个问题：x,y是不是确定的？答案：不是。如果x,y符合要求，那么x+bk,y-ak也符合要求。不确定的原因在于这一句：“当b=0时，我们取x=1,y=0。”实际上y可以取任何正整数。
不定方程ax+by=c
解二元一次不定方程。看起来扩展Euclid算法是不定方程的一种特殊情况，实际上呢，不定方程却是用Euclid算法解的。
对 于不定方程ax+by=c，设gcd(a,b)=d，如果ax+by=c有解，则d|c（这也是许多奥数题的切入点）。所以一旦d不是c的约数，那么 ax+by=c一定无解。当d|c时，先求出ax'+by'=d=gcd(a,b)的x'和y'，则x=x'*c/d，y=y'*c/d。由上一段可知， 只要ax+by=c有一个解，它就有无数个解。
Euclid算法还可以求解同余方程ax≡b(mod m)。这其实和不定方程ax+my=b没有区别。（不定方程和同余方程一般都有范围限制，这其实也很容易解决，就不说了）
评论