Every $n > 17$ is a non-negative integer combination of $4$ and $7$. [duplicate]

Prove that every integer greater than $17$ is a non-negative integer combination of $4$ and $7$. In other words, for all natural numbers $n$, $n$ greater or equal to $17$, there exists non-negative integers $i(n)$, $j(n)$ such that $$n = i(n)4 + j(n)7.$$

Solution 1:

In general this is the Frobenius problem, whose solution is

Given two coprime natural numbers $a$ and $b$, all natural numbers greater than $ab-a-b$ can be expressed as a linear combination $ax+by$ with $a,b \in \mathbb N$.

In your example, $17=4\cdot7-4-7$.

It is easy to see that every natural numbers greater than $ab$ can be expressed as required (*). In your example, this leaves the numbers $18,\dots 27$, which can be done manually.

(*) The solutions of the equation $z=ax+by$ for a given $z$ are given by $x=zu+bt$ and $y=zv-at$, where $t$ is any integer and $u,v$ is any solution of $au+bv=1$. We have $x,y\ge0$ iff $t\ge-zu/b$ and $t\le zv/a$. One way to ensure there is an integer $t$ in that interval is for it to have length at least $1$ and this leads to $z\ge ab$ when you use that $au+bv=1$.