How do you find the Frobenius number g(a,b)?

Question

How do you prove that the greatest integer that cannot be written as ax+by is (a-1)(b-1)-1?

Answer 1

First of all, you need to assume gcd(a,b)=1. Otherwise, you could not get things that were not multiples of the gcd.

Here's what you need to think of.

You need to think of remainders. If you know mods, this will be easy. If you do not, this might seem a bit convoluted.

Let's do an example with g(5,7) to start. If I can get something that looks like 3+7y, I can get anything bigger than that (ie larger y value).

What's the first thing like that I can get?

10 = 3+7

From that, I can obtain 3+14, 3+21, etc...

So think of it like this:

http://math.colgate.edu/~kellen/interspa...

Does that make sense? Now look at the largest one you can't get. Which one is that? 23 = 35 - 12 = 5×7 - 5 - 7

To explain this thoroughly, you need to realize that you're tracking the orbit of 5, mod 7. Once it gets to 0 (ie 5+5+5+5+5+5+5 = 35 ≡ 0 mod 7) it starts over. But in each row, once you hit something, you can get everything in that row past it (by adding 7 instead of 5).

The question is, which row is the last to get hit (ie what is last step in the orbit of 5 mod 7 before repeating)?

That is obvious. If you start repeating at 35, the last row to get hit is the one with the 30 in it. And what's the number before that? The one you won't be able to obtain in that row? 30-7 = 23.

So you find your "loop point" which is ab. Then you go down to the last row to be hit when you jump by a. That is ab-a. Then you jump back (to the left) in that row, to the previous entry, by subtracting b. that's ab-a-b. You can also simplify:

ab - a - b = (a-1)(b-1)-1