Efficiently find integer solution to ax + by = c

Question

Consider an equation of the form $ax + by = c$, where $a$, $b$, and $c$ are nonnegative integers. I'd like to efficiently determine whether there exists a nonnegative integer solution for $x, y$ that satisfies the equation. Does an algorithm faster than brute force exist for solving this?

If it matters:

• I'll be repeatedly using this algorithm with different values of a and b, but c is a constant.
• I don't actually care about finding the solutions, just whether such solutions exist.
• $a$ and $b$ differ from each other by at most a factor of two, whereas $c$ is much bigger than either $a$ or $b$.

Answer 1

Let $D=gcd(a,b)$.

If there is a solution $(x,y)$ then

$$D|ax \text{ and } D|by \;\implies D|c$$

thus necessarily, $ D$ should divide $ c$. If not, there will be no solution.

If $D=1$, then by Bezout identity,

there exist $(u,v)$ which we can find by Euclide's Extended Algorithm, such that

$$au+bv=1$$ and $$a(uc) + b(vc)=c$$