Existence of Natural Solutions to Linear Diophantine Equation If you have a Linear Diophantine Equation, $ax + by = c$, such that $a, b, c$ are constants is there an efficient way to check that there exists some pair $X, Y \in \mathbb N$? 
I recognize that I could find every integer solution and then check for every pair if $(X, Y)$ are natural numbers, but this is very indirect and inefficient; I was wondering if there is a more direct and efficient manner to determine the existence of such a solution.
 A: Perhaps the following might be useful.
Let $a, b > 0$ be coprime integers. Then for all
$$
c \ge (a-1)(b-1)
$$
there are $x, y \ge 0$ such that
$$
a x + b y = c.
$$
(The inequality is best possible, in the sense that $c = (a-1)(b-1) -1$ cannot be expressed in this form.)
I have a proof (which is very simple and straightforward indeed) written up in some notes in Italian, but can translate it if needed.

Euclid's algorithm yields positive integers $u, v$ such that
  \begin{equation*}
    a u - b v = 1,
  \end{equation*}
  where we may have had to swap the roles of $a$ and $b$. The solutions of
  \begin{equation*}
    a x + b y = c
  \end{equation*}
  are of the form
  \begin{equation*}
    a (c u - b t) + b (a t - c v) = c,
  \end{equation*}
  for some integer $t$. We ask ourselves, when is there a $t$
such that
  \begin{equation*}
    c u - b t > -1,
    \qquad
    a t - c v > -1,
  \end{equation*}
that is
\begin{equation*}\tag{ineq}
    \frac{c u}{b} + \frac{1}{b} >  t > \frac{c v}{a} - \frac{1}{a}.
  \end{equation*}
  A sufficient condition for such a $t$ to exist is that the difference between the two bounds in (ineq) is strictly larger than $1$, so that there is an integer in between. In fact one has
    \begin{equation*}
  \frac{c u}{b} + \frac{1}{b} - (\frac{c v}{a} - \frac{1}{a})
  =
  c \cdot \frac{a u - b v}{a b} + \frac{1}{b} + \frac{1}{a}
=
\frac{c}{ab} + \frac{1}{b} + \frac{1}{a}
  \ge
  1 + \frac{1}{ab} > 1,
  \end{equation*}
 as $a u - b v = 1$, and $c \ge (a - 1) (b - 1) = ab - a - b + 1$, so that
$$
\frac{c}{ab} \ge 1 - \frac{1}{b} - \frac{1}{a} + \frac{1}{ab}.
$$
