Check if a positive solution exist of a linear equation with two variables?

Question

Let's say there's an equation

$$a x + b y = c$$

where $a,b,c > 0$ are given. I want to know if positive solutions $x, y >0$ exist for this equation.

Answer 1

Your question refers to the notion of linear diophantine equations.

The simplest LDE would be the one you described above, which takes the form $ax + by = c$. There is a little nice fact here, $ax + by = c$, with $x ,$ $y \in \mathbb{Z}$, has a solution iff $c$ is a multiple of the gcd of $a$ and $b$.

Moreover, there is a theorem which says:

Suppose that $(x, y)$ is a solution to the equation $ax+by=c$, the other solutions all have the form $(x + dm, y − dn)$, where $d \in \mathbb{Z}$, and $m$ and $n$ are the quotients of $a$ and $b$ by the $\gcd (a,b)$, respectively.

The above fact and theorem can be shown by simple $\gcd$ property and Bezout's identity.

This might help you: https://www.math.uwaterloo.ca/~wgilbert/Research/GilbertPathria.pdf

Answer 2

In this case, there are always positive solutions. The reason is that the graph of your equation intersects the axes at the points $(0, c/b)$ and $(c/a,0)$. Then the line segment connecting these points has all positive solution pairs.

Specifically, pick any $x$ such that $0 < x < c/a$. Set $y = \frac{c-ax}{b}$. Then $0 < y < c/b$. The result is a solution with positive $x,y$.

Answer 3

If you are trying to solve the Diophantine equation $$ax+by=c$$ here is what happens.

• This equation has solutions if and only if $gcd(a,b)|c$.

This is a well known fact in number theory.

• If $a,b,c >0$ and $gcd(a,b)|c$ and $c \geq lcm(a,b)$ then, there are always positive solution.

This comes from the fact that we can always find a solution $x$ such that $x \leq \frac{b}{gcd(a,b)}$, which is pretty easy to show.

If $c \leq lcm(a,b)$ there are sometimes positive solutions, sometimes there are not. In this case we cannot say too much without knowing more about $a,b,c$.