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

Question

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?

Answer 1

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\}$$

Answer 2

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