Home > Mathematica, Mathematics > Climbing the lattice

## 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, $p,q$ relatively prime numbers, there exist $a, b \in \mathbf{Z}$ such that:

$a p +b q =1$. Consequently, any integer can by choosing suitable $a, b$. The problem constrains the solutions to the first octant. There are is a maximum integer that has no solution in this octant: $pq -p-q$.

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).