How can I find out the natural numbers $x$ and $y$, such that
$$ax - by = c$$
and $x + y$ is minimum? $a, b, c$ are given integers.
example: $a = 2, b = 2, c = -2$.
$$2x - 2y = -2$$
$$ans: (x = 0, y = 1)$$
Also, how can I know when it is impossible? I guess it's when $c$ is not divisible by $LCD(a, b)$. Is it right?
The equation $ax - b y = c$ (where $a$ and $b$ are positive integers and $c$ is an integer) has natural number solutions if and only if $GCD(a,b) \mid c$. Obviously this is necessary as $ax-by$ is divisible by that GCD. To see it is sufficient: if the GCD is $g$, $a x - b y = g$ has integer solutions by Bezout's identity, and you can then multiply by $c/g$ to get a solution of $ax - b y = c$. Note that if $(x,y)$ is an integer solution, so is $(x+kb/g, y+ka/g)$ for any $k$, so for suitable $k$ you'll have a natural number solution. Moreover, these are all the solutions. So to find the natural number solution with the least $x+y$, find $k$ so that $x+kb/g \ge 0$ and $y+ka/g \ge 0$ but $\min(x+(k-1)b/g, y+(k-1)a/g) < 0$.