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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: