## Solve the Postage Stamp Problem in two denominations over the integers

Let $a$ and $b$ be relatively prime positive integers. Prove that every sufficiently large integer $N$ can be expressed as a linear combination $ax + by = N$ where $x$ and $y$ are nonnegative. That is, prove that there is an integer $N_0$ such that whenever $N \geq N_0$, such a linear combination exists. More specifically, prove that $ab - a - b$ cannot be expressed in this way but that every integer greater than $ab-a-b$ can. (So, every “postage” greater than $ab-a-b$ can be obtained using only stamps of denominations $a$ and $b$.)

We begin with a lemma.

Lemma: Let $a$ and $b$ be positive integers with $\mathsf{gcd}(a,b) = 1$. Then there exist integers $x$ and $y$ such that $ax + by = 1$ and $0 \leq x < b$. Moreover, if $b > 1$, $x \neq 0$. Proof: A solution $(x,y)$ exists since $a$ and $b$ are relatively prime by Bezout’s Identity. By this previous exercise, all solutions $(x,y)$ have the form $(x_0 + mb, y_0 - ma)$ where $(x_0,y_0)$ is a particular solution and $m \in \mathbb{Z}$. In particular, we may choose $(x_0,y_0)$ so that $x_0$ is a least residue mod $b$. Finally, $x_0 \neq 0$ if $b \neq 1$ since otherwise $y_0b = 1$ has a solution in the integers, a contradiction. $\square$

Now we wish to show that $ax+by = ab-a-b$ has no nonnegative solutions $(x,y)$. Suppose to the contrary that such a solution exists. Rearranging, we see that $a(x-b) = -(a+b)$. Since $b$, $y$, and $a$ are positive, $x-b < 0$. Thus $x < b$. On the other hand, reducing the equation $ax + by = ab-a-b$ mod $b$, we have $ax \equiv -a$ mod $b$. Since $\mathsf{gcd}(a,b) = 1$, $x \equiv -1$ mod $b$. Thus we have $x = b-1$. Similarly, $y = a-1$. But then $ab-a-b = a(b-1) + b(a-1) = 2ab-a-b$, so that $ab= 0$. This is a contradiction since $a$ and $b$ are both positive; thus no such solution $(x,y)$ exists.

Note that if $a = 1$, then for all $N \geq ab-a-b+1$ we have $aN + b0 = N$. Similarly if $b=1$. Thus we may assume from now on that $a,b \geq 2$. We now proceed by induction to show that for all $N \geq ab-a-b+1$, there exist nonnegative $x$ and $y$ such that $ax+by=N$.

For the base case, we show that $ax+by = N_0 = ab-a-b+1$ has a solution $(x,y)$ in the nonnegative integers. By the lemma, since $b \neq 1$ we have $ax_0+by_0 = 1$ for some integers $x_0$ and $y_0$ with $0 < x_0 < b$. Note that $a(x_0-1) + b(y_0+a-1) = ab-a-b+1$. We wish to show that $x_0-1$ and $y_0+a-1$ are nonnegative. First, since $x_0 > 0$, we have $x_0 \geq 1$, so that $x_0-1 \geq 0$. Now suppose $y_0+a-1 < 0$. Then $y_0+a \leq 0$, and thus $y_0 \leq -a$. Then $by_0 \leq -ab$, so that $1 = ax_0+by_0 \leq ax_0-ab = a(x_0-b) < 0$, a contradiction. Thus $y_0+a-1 \geq 0$, as desired.

For the inductive step, suppose that for some $N \geq ab-a-b+1$ we have $ax+by=N$ with $x,y \geq 0$. Also write $ax_0 + by_0 = 1$ as in the base case. Now $a(x+x_0) + b(y+y_0) = N+1$, and $x+x_0 > 0$. If $y+y_0 \geq 0$, then $a(x+x_0) + b(y+y_0) = N+1$ is a nonnegative linear combination of $a$ and $b$. Suppose then that $y+y_0 < 0$. Note the following.

 $ab-a-b+1$ < $N+1$ $ab-a-b+1-b(y+y_0)$ < $N+1 - b(y-y_0)$ $ab-a-b+1 - b(y+y_0)$ < $a(x+x_0)$ $b-1-\dfrac{b}{a} + \dfrac{1}{a} - \dfrac{b}{a}(y+y_0)$ < $x+x_0$ (since $a > 1$) $b-1+\dfrac{1}{a} - \dfrac{b}{a}(y+y_0+1)$ < $x+x_0$

Now since $y+y_0 < 0$, we have $y+y_0+1 \leq 0$. Thus $\dfrac{b}{a}(y+y_0+1) \leq 0$. Thus $b-1+\frac{1}{a} < x+x_0$, and we have $b \leq x+x_0$. Moreover, since $0 \leq a+y_0-1$, we have $y+1 \leq a+y_0+y$, and since $y \geq 0$, $0 \leq a+y_0+y$. Thus $a(x+x_0-b) + b(y+y_0+a) = N+1$ is a nonnegative linear combination of $a$ and $b$.

Note that our algorithm is constructive. As an example, consider $a = 8$ and $b = 5$. Then $ab-a-b+1 = 28$, and we have $(4)5 + (1)8 = 28$ and $(5)5 + (-3)8 = 1$. That is, $x_0 = 5$ and $y_0 = -3$. Since $1+(-3) = -2 < 0$, we write $(4+5-8)5 + (1-3+5)8 = (1)5 + (3)8 = 29$, and so forth.