# Stamp problem

1. Feb 8, 2005

this is quite a classic problem i think but im having difficulty finishing it off. If we have two stamps of positive values a and b, (greater than 1), what values can be expressed as a linear combination of these 2 stamps. If the stamps have a highest common factor greater than 1, then there are infinitely many 'bad' numbers. But if the numbers are coprime, after a certain point, all numbers are possible. For instance, with 5 and 8, in the list of possible numbers, you eventually get 28,29,30,31,32, therefore by adding 5's every other number is possible.
Can anyone help me prove the fact the if you have a and b, with a<b, then eventually you get 'a' consecutive numbers in the list of possibles. (therefore making all subsequent numbers possible).
Any other angle welcome!

2. Feb 8, 2005

think the upper limit of not-possible numbers may be ab-a-b on the basis of a number of examples

3. Feb 9, 2005

### robert Ihnot

I presume you mean for A and B to be non-negative. Since we have, in the example given, the case of 5(-3) + 8(2) =1, we see that every integer is possible.

In the example given: 5A+8B =30, and 5A+8B=32, the first case demands that 5 divide B and the second that 8 divides A. So those cases are only solved in non-negative terms with a zero for A or B. Assuming A less than B, to get A successive values, one of them will be divisible by A giving us a zero coefficient for B.

So I wonder if that was how you are seeing the problem?

Last edited: Feb 9, 2005
4. Feb 9, 2005

yes, a and b must be non-negative, as must the numbers of each i.e. cant have negative numbers of stamps.

5. Feb 10, 2005

### robert Ihnot

Well, here is a start: Let B = A+1. Look at series of A terms: (A+1) + A(A-1)=A^2+1; 2(A+1)+A(A-2)=A^2+2...........A(A+1) + A(A-A) =A^2+A.

This series fulfillls the necessary requirements and starts at (A+1) +A(A-1) =A^2+1.