Let and be relatively prime positive integers. Prove that every sufficiently large integer can be expressed as a linear combination where and are nonnegative. That is, prove that there is an integer such that whenever , such a linear combination exists. More specifically, prove that cannot be expressed in this way but that every integer greater than can. (So, every “postage” greater than can be obtained using only stamps of denominations and .)

We begin with a lemma.

Lemma: Let and be positive integers with . Then there exist integers and such that and . Moreover, if , . Proof: A solution exists since and are relatively prime by Bezout’s Identity. By this previous exercise, all solutions have the form where is a particular solution and . In particular, we may choose so that is a least residue mod . Finally, if since otherwise has a solution in the integers, a contradiction.

Now we wish to show that has no nonnegative solutions . Suppose to the contrary that such a solution exists. Rearranging, we see that . Since , , and are positive, . Thus . On the other hand, reducing the equation mod , we have mod . Since , mod . Thus we have . Similarly, . But then , so that . This is a contradiction since and are both positive; thus no such solution exists.

Note that if , then for all we have . Similarly if . Thus we may assume from now on that . We now proceed by induction to show that for all , there exist nonnegative and such that .

For the base case, we show that has a solution in the nonnegative integers. By the lemma, since we have for some integers and with . Note that . We wish to show that and are nonnegative. First, since , we have , so that . Now suppose . Then , and thus . Then , so that , a contradiction. Thus , as desired.

For the inductive step, suppose that for some we have with . Also write as in the base case. Now , and . If , then is a nonnegative linear combination of and . Suppose then that . Note the following.

Now since , we have . Thus . Thus , and we have . Moreover, since , we have , and since , . Thus is a nonnegative linear combination of and .

Note that our algorithm is constructive. As an example, consider and . Then , and we have and . That is, and . Since , we write , and so forth.