# Sylvester's Problem

James Joseph Sylvester was one the greatest British mathematicians of the 19th century. He was known for his absentmindedness and poor memory; on one occasion he even denied the truth of one of his own theorems. Still, he never forgot his origins. E.g., he was precluded from obtaining a Cambridge degree because it required to state his allegiance to the Church of England which he - being Jewish - refused to do.

In 1884 Sylvester submitted to the *Educational Times* the following problem:

A man possess a large quantity of stamps of only two denominations:

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

A man possess a large quantity of stamps of only two denominations:

### 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

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

f_{0} = {0 + 0, 0 + q, 0 + 2q, 0 + 3q, ...}

f_{1} = {p + 0, p + q, p + 2q, p + 3q, ...}

f_{2} = {2p + 0, 2p + q, 2p + 2q, 2p + 3q, ...}

f_{3} = {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.,

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

First off, A(p, q) does not belong to the union of the sequences. If it were, we would have

On the other hand, all sequences f_{k} start at or below

Returning to Sylvester's problem which corresponds to, say, p = 5 and q = 17, the answer is

**Note**: A more formal proof could be found in [Petcović, pp. 60-64]. The book also delves into the *McNuggets problem*, which is to determine the largest number of nuggets that cannot be delivered using McDonald's standard boxes of 6, 9 and 20 nuggets. Problems of this kind are known as *Frobenius number* (corresponding to the parameters of the problem.) Sylvester's

### References

- M. S. Petcović,
*Famous Puzzles of Great Mathematicians*, American Mathematical Society, 2009 - A. Levitin and M. Levitin,
*Algorithmic Puzzles*, Oxford University Press, 2012

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

64494914 |