Proving the linear diophantine equation has at least one positive solution

Question

How would I prove that if $(a,b)|c$ and if $ab<0$, then $ax+by=c$ has at least one solution with $x$ and $y$ positive?

Answer 1

Without loss of generality, let $a > 0$.

Let $h=(a,b)$, $a=hm$, $b=hn$, $c=hp$.

Firstly, solve the equation $ax+by=h$, i.e. $mx+ny=1$:

Consider the set $S=\{m, 2m, 3m, \cdots, nm\}$.

• It has $n$ elements.
• If two elements from the set have the same remainder when divided by $n$, let one be $im$ and one be $jm$. Then, $im-jm$ is divisible by $n$. However, since $m$ and $n$ are co-prime, $i-j$ must be divisible by $n$. However, $-n < i-j < n$, so $i-j$ must be zero, i.e. the two elements must be equal.
• There are only $n$ possible remainders when any number is divided by $n$.
• Therefore, the remainders of the element of $S$ when divided by $n$ must span the whole set of $n$ possible remainders.
• Therefore, there must be $x$ with $x m \equiv 1 \pmod n$, i.e. $mx + ny = 1$ for some $y$.

Now, $m(xp) + n(yp) = p$, i.e. $a(xp) + b(yp) = c$.

---

Note: this is essentially Bézout's lemma. Also, for a more efficient way of solving $mx+ny=1$, see extended Euclidean algorithm.