# Find largest $k$ such that the diophantine equation $ax+by=k$ does not have nonnegative solution.

It is given that $a$ and $b$ are coprime positive integers. My question is, what is the largest integer $k$ such that the diophantine equation $ax+by=k$ does not have any solution where $x$ and $y$ are nonnegative integers ?

This $k$ is called the Frobenius number and equals $ab-a-b$ (http://en.wikipedia.org/wiki/Frobenius_number#n_.3D_2).

Let $$a,b$$ be positive integers with $$\gcd(a,b)=1$$. Let $$S=\langle a,b \rangle=\{ax+by: x, y \in {\mathbb Z}_{\ge 0}$$ denote the numerical semigroup generated by $$a,b$$. Then the gap set of $$S$$,

$$G(S) = {\mathbb Z}_{\ge 0} \setminus S$$

is a finite set. The largest element in $$G(S)$$ is denoted by $$F(S)$$, and called the Frobenius number of $$S$$.

It is well known that $$F(S)=ab-a-b$$. Here is a quick and self-contained proof.

If $$ab-a-b \in S$$, then $$ab-a-b=ax+by$$ with $$x,y \in {\mathbb Z}_{\ge 0}$$. But then $$a(x+1)=b(a-1-y)$$, so that $$b \mid (x+1)$$ since $$\gcd(a,b)=1$$. Analogously, $$a \mid (y+1)$$ since $$\gcd(a,b)=1$$.

Since $$x,y \ge 0$$, $$x \ge b-1$$ and $$y \ge a-1$$. But then $$ax+by \ge a(b-1)+b(a-1)>ab-a-b$$. Thus, $$ab-a-b \in G(S)$$.

We now show that $$n>ab-a-b$$ implies $$n \notin G(S)$$.

Since $$\gcd(a,b)=1$$, there exist $$r,s \in \mathbb Z$$ such that $$n=ar+bs$$. Note that the transformations $$r \mapsto r \pm b$$, $$s \mapsto s \mp a$$ lead to another pair of solutions to $$ax+by=n$$. So if $$r \notin \{0,1,2,\ldots,b-1\}$$, by repeated simultaneous applications of this pair of transformations, we can ensure $$r \in \{0,1,2,\ldots,b-1\}$$. So now assume $$n=ar_0+bs_0$$ with $$0 \le r_0. Then

$$s_0 = \dfrac{n-ar_0}{b} > \dfrac{ab-a-b-ar_0}{b} = \dfrac{a(b-1-r_0)-b}{b} \ge \dfrac{-b}{b} = -1.$$

Thus, $$s_0 \ge 0$$, and so $$n \in S$$. $$\blacksquare$$