Gabeland

Here’s a random proof I came up with, and I already had it written up so I thought I may as well post it here.

Assume A and B are coprime.

Lemma 1: AB is the smallest number you can express as a sum of A’s and B’s in two different ways.
Proof: Suppose there was another one that was smaller. Define C to be the smallest such number. Now, the two ways you can express C cannot both have A in it. If they did, you could remove A from each to get a smaller one. The same logic applies to B. Therefore, the two ways to describe C must be one with only As and one with only Bs. And the smallest number you can do that with is lcm(A,B) = AB, because A and B are coprime.

Lemma 2: You cannot express AB-A-B as a sum of A’s and B’s.
Proof: Suppose you could. Add an extra B to it. That gives you a way to express AB-A with at least one B. Now, you can also express AB-A with (B-1) A’s. Those two ways must be different, because one has a B and the other one doesn’t. but AB-A < AB, so by Lemma 1, it can’t be expressed in two different ways. By contradiction, AB-A-B can’t be expressed at all.

Lemma 3: There exists 0≤x<B and 0≤y<A such that xA = yB+1.
Proof: By the Chinese Remainder Theorem, there is exactly one N (mod AB) where N mod A = 0 and N mod B = 1. The resulting N is a multiple of A (say, xA) and one more than a multiple of B (say, yB+1).
(For the rest of this proof, x and y refer to these exact solutions. Also, note that (B-x)A+1 = (A-y)B.)

Lemma 4: If a sum of A’s and B’s adding to C has at least (B-x) A’s or at least y B’s, then you can express C+1 as a sum of A’s and B’s.
Proof: If there’s at least (B-x) A’s, you can replace (B-x) of the A’s with (A-y) B’s to add 1 to the total. Likewise, if there’s at least y B’s, you can replace y of them with x A’s to add 1.
Corollary: If C has at least x A’s or at least (A-y) B’s, you can express C-1 as a sum of A’s and B’s. Similar logic, just the other way around.

Lemma 5: if C > AB-A-B-1 can be expressed as a sum of A’s and B’s, then C+1 can be expressed as a sum of A’s and B’s.
Proof: The replacement in Lemma 4 requires (B-x) A’s or y B’s. Therefore, the maximum number where you can’t do one of those replacements is (B-x-1)A + (y-1)B = AB-xA-1 + yB-B = AB-A-B-1. So if C is greater than AB-A-B-1, it must have at least one of the requirements.
Corollary: if C > AB-A-B+1 can be expressed as a sum of A’s and B’s, then C-1 can be expressed as a sum of As and Bs. Similar logic, just the other way.

Theorem: AB-A-B is the largest number that cannot be expressed as a sum of A’s and B’s.
Proof: We know that AB-A-B cannot be expressed by Lemma 2, and we know that AB can be expressed as either B A’s or A B’s. For each number C where AB-A-B < C < AB, we can repeatedly subtract 1 down to it by the corollary to Lemma 5. Likewise, for every number C > AB, we can repeatedly add 1 up to it by Lemma 5. Therefore, every number greater than AB-A-B can be expressed as a sum of A’s and B’s, making AB-A-B the largest one that can’t.