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

This question already has an answer here:

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

## marked as duplicate by Jyrki Lahtonen, Cameron Buie, Sasha, Vedran Šego, user67258 Sep 26 '13 at 15:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Hint: $4$ and $7$ are coprime. – Dan Rust Sep 26 '13 at 14:39
• If you can write $n = i(n)\cdot 4 + j(n)\cdot 7$, then $n+4 = \bigl(i(n)+1\bigr)\cdot 4 + j(n)\cdot 7$, so you need only check $18,19,20,21$. (But of course there's some nice theory to be learned if you do it abstractly.) – Daniel Fischer Sep 26 '13 at 14:39
• In an other instance of the same problem a general answer is given. See for example robjohn's answer there. – Jyrki Lahtonen Sep 26 '13 at 14:54

## 1 Answer

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

• – lhf Sep 26 '13 at 18:04