# Existence of Natural Solutions to Linear Diophantine Equation [duplicate]

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.

## marked as duplicate by Dietrich Burde, Daniel W. Farlow, Shailesh, E. Joseph, user223391 Oct 31 '16 at 0:21

• Sorry, this was not the correct one, there is also one for positive solutions, e.g., Bill's answer here. – Dietrich Burde Oct 30 '16 at 17:25
• The other question is very relevant, but I think this one is asking whether there exists a natural number solution, not asking to find any explicit solutions or whether there exist integer solutions. – 6005 Oct 30 '16 at 17:26
• Yes, just proving the existence of a natural number solution – BlurryZombie Oct 30 '16 at 17:37
• if the gcd of a and b does not divide c then there is no solution. – Brandon Thomas Van Over Oct 30 '16 at 17:52
• True, yet there are cases where it proves there is an integer solution but this doesn't necessarily entail that there is a natural solution. – BlurryZombie Oct 30 '16 at 17:57

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.)
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}.$$