The largest integer that cannot be made from fives and eights

What does the problem mean?

Problem. Find the largest integer that cannot be written as

$$5x+8y,\qquad x,y\in\mathbb Z_{\ge0}.$$

For example, $18=5+5+8$ is representable, whereas $17$ is not. Repetition is allowed, and either count may be zero. The nonnegativity condition is essential: negative numbers of coins or summands are not permitted.

The answer is $\boxed{27}$. We will prove both that $27$ is impossible and that every larger integer is possible.

An elementary method: use five columns

Arrange the positive integers in five columns, so moving down a column adds five.

Once a number in a column is representable, every number below it is representable by adding another five. The multiples of eight give a starting point in each residue class modulo five:

$$0,\quad8,\quad16,\quad24,\quad32.$$

Their residues are $0,3,1,4,2$, so they cover all five columns. These are the smallest representable numbers in their respective columns: using five changes no residue, and the least nonnegative count of eights for each residue is one of $0,1,2,3,4$.

The last unrepresentable numbers before those starting points are, by residue class $0,1,2,3,4$,

$$-5,\quad11,\quad27,\quad3,\quad19.$$

The negative entry simply means every nonnegative multiple of five is already representable. The largest nonnegative obstruction is $27$.

A short alternative using five consecutive values

The five integers immediately after $27$ are all representable:

$$\begin{aligned} 28&=4\cdot5+8,&29&=5+3\cdot8,\\ 30&=6\cdot5,&31&=3\cdot5+2\cdot8,\\ 32&=4\cdot8. \end{aligned}$$

Adding any number of fives proves that every integer at least $28$ is representable.

For $27$, reduction modulo five requires $3y\equiv2\pmod5$, or $y\equiv4\pmod5$. A nonnegative such $y$ is at least four, making $8y\ge32>27$. Thus $27$ is impossible, completing the proof.

The Diophantine viewpoint

Without the restrictions $x,y\ge0$, every integer $m$ can be written as $5x+8y$, because $5(-3)+8(2)=1$. One solution for $m$ is $(-3m,2m)$, and every integer solution is

$$(x,y)=(-3m+8k,\ 2m-5k),\qquad k\in\mathbb Z.$$

The problem asks whether the integer $k$ can be chosen so that both coordinates are nonnegative. This is a bounded-feasibility question, not merely whether a linear integer equation has a solution.

The general parameterization is explained in Diophantine equations.

The general two-denomination formula

Let $a,b>1$ be coprime positive integers. The largest integer not representable as $ax+by$ with nonnegative integers $x,y$ is

$$\boxed{ab-a-b.}$$

Here is a proof, so the formula need not be memorized without its conditions.

The proposed largest obstruction is impossible

Set $N=ab-a-b$. If $N=ax+by$ with $x,y\ge0$, then modulo $a$,

$$by\equiv-b\pmod a.$$

Since $a,b$ are coprime, $y\equiv-1\pmod a$, so $y\ge a-1$. But then

$$by\ge b(a-1)=ab-b>N,$$

contradicting $ax+by=N$ with $ax\ge0$.

Every larger integer is possible

Take $m>N$. The residues of $0,b,2b,\ldots,(a-1)b$ modulo $a$ are all distinct, by coprimality. Choose $y\in\{0,1,\ldots,a-1\}$ with $by\equiv m\pmod a$. Then $x=(m-by)/a$ is an integer, and

$$m-by>N-b(a-1)=-a.$$

Thus $x>-1$, and since $x$ is an integer, $x\ge0$. This constructs a valid representation of every $m>N$.

For $a=5,b=8$, the formula gives $40-5-8=27$. If the denominations are not coprime, infinitely many integers fail divisibility and there is no largest obstruction. If one denomination is one, every nonnegative integer is representable. Those cases must be separated from the theorem.