Thread: Positive Solutions to Linear Diophantine Equation

1. Positive Solutions to Linear Diophantine Equation

I've been looking at the following problem, involving Diophantine equations:

Let $\displaystyle a,b,c\geq 0$ such that $\displaystyle \gcd(a,b)=1$ and $\displaystyle c\geq (a-1)(b-1)$. Show that there exist nonnegative integers $\displaystyle s,t$ so that $\displaystyle as+bt=c$.

I know that the solutions to a linear Diophantine equation are given by $\displaystyle x=x_0+bt, y=y_0-at$, where $\displaystyle (x_0,y_0)$ is a particular solution and $\displaystyle t$ is an integer parameter. If I want these to be positive simultaneously, I need to have $\displaystyle \dfrac{-x_0}{b}\leq t\leq \dfrac{y_0}{a}$. In other words, there needs to be an integer in the interval $\displaystyle \left[\dfrac{-x_0}{b}, \dfrac{y_0}{a}\right]$.

From here, I cannot seem to put bounds on the endpoints of the interval. I would appreciate any insight you may have on the issue.

2. Thanks. I looked into the link provided in the Yahoo answer and was pleasantly surprised to see that the proof given was geometric. I myself spent some time trying to handle the problem geometrically (with a similar approach), but I couldn't get it to work. I should be more careful next time!