# Non-negative integer solutions of a single Linear Diophantine Equation

Consider the following linear Diophantine Equation::

  ax + by + cz = d  ------------ (1)


for all, a,b,c and d positive integers, and relatively prime, and assume a>b>c without loss of generality.

Can we find a lower bound on d which ensures at least one non-negative solution to this equation?

I know we can solve this problem easily for

     ax+by = c. -------- (2)


c>=ab, ------------(3)

which derives from the fact that the distance between two consecutive solutions of this equation is

     $D = (\sqrt(a^2 + b^2))$  ----------(4)


and c>=ab ensures that the length of line in x-y plane is large enough to include at least one solution).

Since equation (1) is a plane in the xyz coordinate system, and the distance between consecutive solution can be shown to be DD = sqrt(b^2+c^2) (though this may not be smallest distance between solutions). I was thinking that if we can show that an inscribed circle with diameter DD can be enclosed within the triangle formed by x,y and z intercepts of Eq.(1), i.e. (c/a,0,0), (0,c/b,0) and (0,0,c/a), then we have at least one non-negative solution. But the in-circle radius has an inconvenient relationship with the original variables (a,b,c,d), and may not be a monotonic function of d.

Is there a smarter way to do this? and if such a bound exists, can it be extended to higher dimensions?

Thanks.

-

The question of determining the lower bound on $d$ is called the Frobenius problem. For $2$ variables your bound can be improved: every integer starting from $(a-1)(b-1)$ is representable as a non-negative combination. Some general results on this problem are available in this paper, - even on the first page (which is open-access): it is stated that for $a>b>c$ the number $(c-1)(a-1)$ gives a bound. However, it is probably very far from optimal; there are various conjectures and partial results on the asymptotic behaviour of these numbers for big $a,b,c$ (and similarly for larger dimensions). In particular, some conjectures on Frobenius problem were formulated by late Vladimir Arnold in the past decade, see, e.g. this article and this article; some progress has been made in that direction, see e.g. like this paper.

-
@Vladimir In the answer by Pete on another question on MathOverflow mathoverflow.net/questions/19587/… , there seems to be a claim that Sylvester had shown that for the two variable case the Frobenius number is precisely $ab-a-b$ (in your notation) Doesn't that contradict what you saying in the two variable case? – Anirbit Apr 12 '11 at 16:03
Huh? $ab-a-b=(a-1)(b-1)-1$, so these two statements match perfectly. – Vladimir Dotsenko Apr 13 '11 at 22:13
@Vladimir Oh..sorry..I was not accounting for the "-1". The number you quote is the minimum number that is representable and hence the Frobenius number would be one less than that. Okay! – Anirbit Apr 16 '11 at 8:34

There's a whole book on this problem; J L Ramirez Alfonsin, The Diophantine Frobenius Problem, Oxford University Press, 2005.

-

A bunch of various bound for Frobenius number is given in this paper.

Wikipedia article may be helpful as well.

-