# Show that almost every natural number can be written as non-negative combination of $6, \ 10, \ 15$

Show that almost every natural number can be written as non-negative combination of $6, \ 10, \ 15$.

Non-negative combination means numbers like $6\cdot k\ +10\cdot l \ + 15\cdot m$, where $k,l,m \in \mathbb{N}$.

And more generally. For $n$ natural numbers $a_k, \ k \in \{1,2, ..., n\}$ with the property

$gcd(a_1,a_2, ..., a_n) = 1$ same statement as above follows.

Any hints?

I was writing down some of these combinations for $6,10,15$, but how can we prove it formally?

• When you say "almost every" do you mean "all but finitely many"? – orlp Feb 28 '18 at 12:20
• Hint: once you get each possible residue class $\pmod 6$ (or any of them, but $6$ is smallest) then you get every larger number (just by adding multiples of $6$). – lulu Feb 28 '18 at 12:20
• Consider Bézout's identity for three integers and work from there. Otherwise, if you wish to avoid using that, read the above comment. – Stone Feb 28 '18 at 12:21
• Just a note: This is related to the existence of Frobenius Numbers. – Henricus V. Feb 28 '18 at 13:01

I give explicit solutions for six $r$:

\begin{align*} 0 &: &0 \\ 25 &: &10 + 15 \\ 20 &: &2\cdot10 \\ 15 &: &15 \\ 10 &: &10 \\ 35 &: &2\cdot 10 + 15 \\ \end{align*}

Now note that any integer $n \geq 35$ can be written as $6k + r$ due to the fact that $\{0, 25, 20, 15, 10, 35\} \equiv \{0, 1,2,3,4,5\} \mod 6.$

Using some mental arithmetic for the numbers $n < 35$ we find that the only numbers which have no solutions are:

$$\{1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 14, 17, 19, 23, 29\}$$

• Okay, for three given numbers it is simple to count and justify that above is correct. What about given a_1, ... , a_n? How do we proceed in this case? I mean, the construction of residues. – janusz Feb 28 '18 at 13:51
• @janusz Programatically it's trivial for any finite $a_1, \dots, a_n$. Just choose the smallest as your modulus and loop over every combination of $c_1a_1 + \dots + c_na_n \bmod m$ for $c_k \in \{0,\dots,m-1\}$. – orlp Feb 28 '18 at 13:54

A few hints:

• if $n=6k+10l+15m$ and $m>1$, then $n+1=6(k+1)+10(l+1)+15(m-1)$;
• $6\times4+1=10+15$;
• $10\times2+1=6+15$.