求不定方程 ax+by=c 的正整数解或非负整数解的方法

luyuanhong

elimqiu

给定非零整数 a, b, 存在互素的整数 s, t 使得 as + bt = d, 其中 d 是 a 与 b 的最大公约数，也是可以表成 ax + by 形式的最小正整数。
我们知道 d 可以通过辗转相除法得到，而这个过程又可以用来计算 s, t.
如果 c 不是 d 的倍数，那么 ax + by  = c 无解。 否则有整数 k 使得 c = kd, 于是方程
ax + by = c 的通解是 (x, y) = (ks + m b/d, kt- m a/d). 其中 m 是任意整数。