# Number theory - gcd and linear diophantine equations

1. Aug 15, 2009

### reb659

1. The problem statement, all variables and given/known data

Suppose that gcd(a, b) = 1 with a, b > 0, and let x0, y0 be any integer solution to the equation ax + by = c. Find a necessary and sufficient condition, possibly depending on a, b, c, x0, y0 that the equation have a solution with x > 0 and y > 0.

2. Relevant equations

3. The attempt at a solution
I'm pretty lost. Can anyone point me in the right direction?

2. Aug 16, 2009

### VKint

Well, if one of $$x_0$$ or $$y_0$$ is negative, then you have to look for another solution $$(x_1, y_1)$$ with $$x_1, y_1 > 0$$. By subtracting equations, you get $$a(x_1 - x_0) + b(y_1 - y_0) = 0$$. Can you see why this equation implies that $$x_1 - x_0 = kb$$ and $$y_1 - y_0 = -ka$$ for some integer $$k$$? Once you do, your problem is reduced to a search for a value of $$k$$ such that $$x_0 + kb > 0$$ and $$y_0 - ka > 0$$. You should be able to take it from here.