A similar question was asked in this post, but I would hope for a bit of an improvement over the current answer. Indeed, for simplicity, let me consider positive integers $a_1,...,a_k$ which are relatively prime, then I want to prove that for any integer $n \ge n_0$ where $n_0 = a_1 \cdots a_k$ is the product, there are nonnegative integers $x_1,...,x_k$ such that $$ x_1 a_1+\cdots+x_k a_k=n $$
In the previous post, such an answer was given for sufficiently large $n$, but I think it may be possible to reduce the lower bound in $n$ to $n_0$. However, I'm not quite sure to do this.
Current Thoughts. Let me first consider the case where $k=2$, so we only have relatively prime $a_1,a_2$. Let $n\ge n_0$ so that it can be written as $n=a_1 q+ r$ where $r$ is the remainder and $q \ge a_2$. Now if we consider the set $S=\{a_2, 2a_2,...,a_1a_2\}$, we see that there are $a_1$ elements, and each element has a different remainder with respect to $a_1$. Since there can only be $a_1$ remainders when dividing by $a_1$, there must exists unique $1\le x_2 \le a_1$ such that $x_2 a_2 =y_1 a_1 +r$, i.e., has remainder $r$ and $y_1 \le a_2$. Therefore, if we take $x_1=(q-y_1)\ge 0$, then the statement follows.
Now I think the argument can be extended via induction. But I'm not quite sure how to do it, as I'm not quite familiar with number theory. A ny help would be appreciated, but hopefully it can be proven using very rudimentary number theory.