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

Question

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 ?

Answer 1

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

Answer 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<b$. 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$