2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ When you say "almost every" do you mean "all but finitely many"? $\endgroup$ – orlp Feb 28 '18 at 12:20
  • 2
    $\begingroup$ 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$). $\endgroup$ – lulu Feb 28 '18 at 12:20
  • 1
    $\begingroup$ Consider Bézout's identity for three integers and work from there. Otherwise, if you wish to avoid using that, read the above comment. $\endgroup$ – Stone Feb 28 '18 at 12:21
  • 1
    $\begingroup$ Just a note: This is related to the existence of Frobenius Numbers. $\endgroup$ – Henricus V. Feb 28 '18 at 13:01
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – janusz Feb 28 '18 at 13:51
  • $\begingroup$ @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\}$. $\endgroup$ – orlp Feb 28 '18 at 13:54
2
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.