The Frobenius coin problem for two coins
Statement
Let be coprime positive integers. Prove that cannot be written as with integers , but every integer can.
Hint
Given , choose the representation in which . When is ?
Show solutionHide solution
Solution
Normalising. Since , is invertible modulo , so for each integer there is a unique with . Put . Every integer solution of is for .
Criterion. is representable with iff . Indeed, a representation needs , which forces , and then must be , so . Conversely gives the representation .
The number . We need , so , i.e. . Then . Not representable.
Larger . If , then since ,
so , and being an integer, .
Example. For , the largest amount that cannot be paid is .
Lesson. Reduce one variable modulo the other coefficient to get a canonical representative, then the sign of the other variable decides everything.