# Non-negative integer solution for $ax + by = c$ [duplicate]

Show that if positive integers $$a$$ and $$b$$ are relatively prime, then every integer $$c > ab$$ has the form $$ax + by = c$$, where $$x$$ and $$y$$ are non-negative integers.

According to the common way of solving such a Diophantine equation $$ax + by = c$$, if $$x_0$$, $$y_0$$ is already a solution, then the pairs are also a solution: $$x = x_0 + \frac{bn}{d}, y = y_0 - \frac{an}{d},\quad (n\in Z)$$ where $$d$$ is the greatest common divisor of $$a$$ and $$b$$.

However, although a pattern of periodicity is known, it is still not certain there are definite chances that $$x$$ and $$y$$ can be both positive.

## marked as duplicate by YuiTo Cheng, Community♦Jun 1 at 4:12

Your problem is basically a special case of the Coin problem, with the n = 2 section including a proof that just requires the somewhat less restrictive condition of $$c \ge (a-1)(b-1)$$. Adjusted to use your variables, and paraphrased somewhat by myself, it says that for any such $$c$$, as $$a$$ and $$b$$ relatively prime, then all of the integers $$c - jb$$ for $$0 \le j \le a - 1$$ are mutually distinct modulo $$a$$. Thus, there's a unique value of $$j$$, say $$j = k$$, and a non-negative integer $$n$$, such that $$c = na + kb$$. Note that $$n \ge 0$$ because $$na = c - kb \ge (a - 1)(b - 1) - (a - 1)b = -a + 1$$.
• Thanks for your answer! It seems that the average of $x/b$ and $y/a$ can be used to prove that there is a positive combination, while the $c = ab$ is quite a limit. This result can't be further reduced to $(a-1)(b-1)$. – Wenkuei P'ei Apr 18 at 5:46