# Positive Solutions to Linear Diophantine Equation

• Aug 3rd 2010, 11:24 PM
roninpro
Positive Solutions to Linear Diophantine Equation
I've been looking at the following problem, involving Diophantine equations:

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

I know that the solutions to a linear Diophantine equation are given by $x=x_0+bt, y=y_0-at$, where $(x_0,y_0)$ is a particular solution and $t$ is an integer parameter. If I want these to be positive simultaneously, I need to have $\dfrac{-x_0}{b}\leq t\leq \dfrac{y_0}{a}$. In other words, there needs to be an integer in the interval $\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.
• Aug 4th 2010, 12:11 AM
chiph588@
• Aug 4th 2010, 12:22 AM
roninpro
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!