Math Makes Me Happy!

If x and y are relatively prime positive integers, what is the greatest value z such that there do not exist integers A and B (>=0) to make the equation Ax + By = z true?

Explanation: I think the explanation of this status will perhaps be more disturbing than the actual message. Then again, if you're a returning visitor to this blog, you probably already know how disturbed I am.

There is a game I play on Facebook in which (among other things) you have an allotment of energy with which to do jobs. The jobs each have an energy cost associated with them. So, let's say you have 20 energy and there are jobs that require 1 energy, 5 energy, and 6 energy. You can do 20 of the first job, or 4 of the second job, or 3 of the third job (with 2 energy left over, perhaps to do the first job twice as well). That part is pretty simple.

There is also a feature called an "energy boost" which will automatically refill your energy AND gives you 25% more on top of that. Because the energy boost refills your energy for free, it is beneficial to use all of your energy up before you apply the energy boost. For example, if you have 4 energy points left (with a max of 20) and you apply the energy boost, you end up with 25 energy points, with a net gain of 21 points. If you use the 4 energy points before applying the energy boost, you go from 0 to 25, netting you 25 points. The less energy you have, the more you benefit from the energy boost.

From this logic arose some interesting situations. If I have an energy boost available and I still have 137 out of 150 possible energy points, how do I break down the jobs I can do such that I end up with 0 energy. It's not as easy to compute when your jobs take 5, 8, 13, 22, and 27 energy. So I started to wonder...

Can I know without a doubt that, if my energy total is high enough, it is possible to get down to 0 before I start to do my jobs? I figured I'd start with the case where only two jobs are available. Clearly, the job costs have to be relatively prime. If they weren't, 4 and 6 for example, then number that isn't a multiple of their shared factor (odd numbers in this case) would leave a remainder.

I started to do the math and found a neat little formula that tells me without a doubt that if an energy total is above a certain level, I am guaranteed to be able to zero out my energy using relatively prime job costs. I'm not sure why it works yet, but I know I found the solution.

Can you find an answer? Can you tell me why it works? I'm almost certain there's a fundamental theorem in number theory lying around which covers this, but I haven't the time to look it up right now. Do you think Euler had to interrupt his work to change diapers? I think not.