怎么判断一个二元一次方程有正整数解

怎么判断一个二元一次方程有正整数解

对于
ax + by = gcd(a, b), 由于 gcd(a,b) = gcd(b, a % b) = ...
所以 ax1 + by1 = gcd(a,b) = bx2 + a % b y2 = .... = 1xn + 0yn = gcd(a,b)
至此可以求出xn, 然后反推回去, 就可以得到x1 和 y1 (程序一般直接用递归执行)
于是得到ax1 + by1 = gcd(a,b),那如何得到 ax + by = c的解呢
ax1 + by1 = gcd(a,b) -> a(x1 * c/gcd(a,b)) + b(y1 * c/gcd(a,b)) = c
于是可以求出, 一组 x = x1 * c/gcd(a,b), y = y1 * c/gcd(a,b)
然后你要判断整数解的话, 也是简单, 如果(x,y)是一组解, (x + b/gcd(a,b), y - a/gcd(a,b))也是一组解
(x - b/gcd(a,b), y + a / gcd(a,b))也是一组解
我们可以先求出x是正整数的一组解, 用取模既可
x = (x % b/gcd(a,b) + b/gcd(a,b)) % b/gcd(a,b) //这里保证x >= 0
y = (c - ax) / b, 这样的x已经是最接近0的数,于是不能在减少了
所以
如果y < 0, 那么无正整数解
如果y > 0有正整数解.

二元一次方程？得看这两个式子的情况 不是一元二次方程？ 找对称轴，特殊点，想象一下就可以了