Is there a test to determine whether the Diophantine equation,
$$ ax + by = z $$
with $a,x,b,y,z$ integers, $a >0, b>0, z>0$, has a solution with $x\geq 0$ and $y\geq 0$?
In general we know that an integer solution exists if $\gcd(a,b)$ divides $z$. Can we tell if a non-negative integer solution exists?
Best Answer
This is very simple for the two-variable case. Without loss of generality suppose $\gcd(a,b) = 1$ (else divide $a,b,z$ by that gcd, which gives an equivalent linear Diophantine equation with $x$ and $y$ exactly identical).
Now, using the Euclidean algorithm you can extract some (possibly negative) solution of $ax + by = z$, say $(x_0, y_0)$. Every other solution necessarily has the form $(x_0 + bn, y_0 - an)$ for some $n \in \mathbb Z$ (this is where we use the co-primality assumption). In other words there is an integer solution for $x$ iff $x \equiv x_0 \pmod b$. If we take $x_1$ to be the smallest positive residue of $x_0$ modulo $b$, and $y_1 := (z - ax_1)/b > 0$, then $(x_1,y_1)$ is a positive solution to $ax+by=z$. Furthermore, it follows easily from monotonicity that this is also necessary: if $y_1 \le 0$ then there is no positive solution, because we'd need to increase $y$ and that would make $x$ nonpositive.