Sylvester's Problem

A man possess a large quantity of stamps of only two denominations: 5-cent stamps and 17-cent stamps. What is the largest (finite) amount of cents which the man cannot make up with a combination of these stamps?

Solution

Let's do something more general and solve the following problem:

Let p and q be two mutually prime integers greater than 1. What is the largest number that could not be expressed as a linear combination ap + bq, with non-negative integers a and b?

To solve the latter, form a family of arithmetic sequences:

f₀ = {0 + 0, 0 + q, 0 + 2q, 0 + 3q, ...}
f₁ = {p + 0, p + q, p + 2q, p + 3q, ...}
f₂ = {2p + 0, 2p + q, 2p + 2q, 2p + 3q, ...}
f₃ = {3p + 0, 3p + q, 3p + 2q, 3p + 3q, ...}
...
f_q-1 = {(q-1)p + 0, (q-1)p + q, (q-1)p + 2q, (q-1)p + 3q, ...}.

There is no need in the "next" progression f_qp as it would be a subsequence of the very first sequence. Other than that, the above q sequences have no common terms.

The terms in f_k, 0 ≤ k < q have the property of sharing a residue modulo q, viz., kp (mod q). Since q and p are mutually prime, the set {kp (mod q): 0 ≤ k < q} of all such residues coincides with the segment of integers {k: 0 ≤ k < q}. This is a crucial observation.

Indeed, had the sequences started with the corresponding residues, their union would have covered the entire set of non-zero integers. Since each f_k started with a number kp which is not less than kp (mod q), the union of all the sequences has gaps at the beginning. The question is to find the largest number missing from that union. I am going to show that A(p, q) = (q - 1)p - q = pq - p - q is that number.

First off, A(p, q) does not belong to the union of the sequences. If it were, we would have A(p, q) = ap + bq, with 0 < a ≤ q-1 and 0 < b. But then q(p - 1 + b) = (a + 1)p would hold, implying (since p and q are mutually prime) that (a + 1)|q, so that (a + 1) = q. We thus would have A(p, q) = ap + bq > (q - 1)p which is false.

On the other hand, all sequences f_k start at or below (q - 1)p. Some may start above A(p, q) = (q - 1)p - q, some may start below that. Since their terms increase by q, sequences of the latter kind are abound to have a term between A(p, q) and (q - 1)p. It follows that any integer between these two numbers belongs to the union of the sequences. But once the union of the arithmetic sequences with q as the common difference, contains an integer segment of length q, it contains all the integers above that segment.