## least one solution of ax+by=c

I was wondering if someone could help me with a proof.

If ab<0 (can we assume that either a or b is negative then?) and d(gcd of a and b)│c, there there is at least one solution of ax+by=c with x and y positive.
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor
 I haven't read it yet but "ax+by=c => gcd(a,b)|c ?", is most certainly relevant to your question. Here is my attempt, which to be honest is a complete overkill since it resorts to a more advanced theorem!:), but it was pretty much the first thing that came into my head. First we note that if we have one solution to the equation, say (x,y), then (x+nb, y+na) is also a solution. Therefore if we can find one solution, we can always, from this solution, construct another solution for which both coordinates are positive. With the aim of finding a single solution, we note that it is clear that the problem is equivalent to (where I have redefined the meaning of the variables a,b,c): $$ax - by = c$$ For a>0, b>0, and where a and b are coprime [I have divided both sides of the equation by the gcd(a,b), and then redefined the variables (e.g. c now represents the result of this division on the rhs etc..likewise for a,b)]. It is also clear that if we can find a solution to the equation : $$ax - by = 1$$ (where a>0, b>0, and where a and b are coprime), then we can immediately find a solution to the equation above (simply by multiplying both sides of the equation by c). We proceed by noting that from a generalisation of fermat's little theorem, and given the coprimality of a and b : $$\exists\ p\ s.t.\ a^p = 1 (mod\ b)$$ In particular p is given by Euler's totient function : $$p=\phi(b)$$. Therefore : $$a^p = Nb + 1\ for\ some\ integer\ N$$ So that $$a^p - N b = 1$$ Therefore the solution to : $$ax - by = 1$$ (where a>0, b>0, and where a and b are coprime) is given by : $$(x,y) = (a^{p-1}, N)$$ where x, y are both integers, and therefore we have achieved the desired result