A package requires 1.61 in postage. There is only 5 cent and 8 cent stamps. What is the smallest number of stamps that would total $1.61?
Since we need to deal with integers and cents, lets use c for the number of cents.
This means the stamps are 5c and 8c (5 cents and 8 cents).
There are two ways to solve this, and both require us to use trial and error.
We need 161c.
If we only got 20 8c stamps, that would be 20*8c = 160c, and that's 1c short of 161,
and 1 is not a multiple of 5.
If we only got 19 8c stamps, that would be 19*8c = 152c, and 161c - 152c = 9c,
and 9 is not a multiple of 5.
If we only got 18 8c stamps, that would be 18*8c = 144c, and that's 17c short,
and 17 is not a multiple of 5.
If we only got 17 8c stamps, that would be 17*8c = 136c, and that's 25c short,
and 25 is a multiple of 5.
Now 25/5 = 5, so this means we would get 17 8c stamps and 5 5c stamps.
The total cost would be 17*8c + 5*5c = 136c + 25c = 161c = 161c = $1.61.
Now since 161 is odd, it is known we need an odd number of 5c stamps, for the number of 8c stamps will give us an even number of cents. Only 1 5c stamp leaves 161c - 5c = 156c, and that is not divisible by 8c (156c/8c = 19.5, but the answer needs to be an integer).
The next odd number after 1 is 3. If we got 3 5c stamps, that would be 3*5c = 15c,
and 161c - 15c is 146c, and that is not divisible by 8, for 146/8 = 18.25.
The next odd after 3 is 5. If we got 5 5c stamps, that would be 5*5c = 25c, and 161c - 25c is 136c.
136 is divisible by 8c since 136 / 8 = 17. This approach leads to 17 8c stamps and 5 5c stamps as well.
Perhaps I could have said we need to solve 5A + 8B = 161 where A and B are integers,
but doing that would be easiest to do by either method given above.