Climbing the lattice

I have seen a lot of references to Sylvester’s stamp puzzle or problem. Here is a statement and it’s solution.

Fundamentally, it illustrates a property of relatively prime numbers.

For, relatively prime numbers, there exist such that:

. Consequently, any integer can by choosing suitable . The problem constrains the solutions to the first octant. There are is a maximum integer that has no solution in this octant: .

If there stamp denominations are not relatively prime then there are an infinite number of ‘gaps’, hence no finite maximum.

The CDF here is motivated by this puzzle (for denominations 4 and 7).