How to show that $\gcd(a_1,a_2,\cdots,a_k) = 1$ implies that there exist a non-negative solution to $\sum_{i=1}^{n}a_ix_i = n$ for large $n.$

Question

I was reading about the Coin-problem and I am unable to fully understand the following argument:

On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of $\{ a_1, a_2, …, a_n \}$ is bounded according to Schur's theorem, and therefore the Frobenius number exists.

Here the author is arguing for the existence of a non-negative solution to the linear Diophantine equation (LDE) $$\sum_{i=1}^{k}a_ix_i =n \text{}$$ for large enough $n.$ Now I tried to understand the proof of the Schur theorem here enter link description here (Page 98), but I am not sure that I understand it fully. In particular, I don't understand why the generating function associated with the sequence $h_n$ that counts the number of solutions to the LDE is $$H(x)= \prod_{i=1}^{k}\left(\frac{1}{1-x^{a_i}}\right).$$

Once we have $H(x)$ we can deduce that $$h_n\sim \frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}$$ as $n\to \infty.$ How does this exactly show that for large enough $n,$ $h_n>0?$ Is it because the $\frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}>0?$

Answer 1

A simple approach to the title:

Thanks to Bezout, there is some (not necessarily) integer combination of the $a_i$s that makes $1$. Add a large enough multiple of $a_1$ to each coefficient to make it non-negative and call the sum $k$; we have $k\equiv 1 \pmod{a_1}$.

Now any number $\ge ka_1$ is a non-negative combination of the $a_i$s. Namely, let $n$ be the desired number, and let $m=n\bmod a_1$. Then $mk$ is a positive combination, and we can add some multiple of $a_1$ to make it $n$ instead, since $mk\equiv n\pmod{a_1}$ and $mk<n$ because $m<a_1$.

Answer 2

We first do this for $k =2$.

LEt us assume WLOG that $a_1 < a_2$. If gcd$(a_1,a_2)=1$ then $a_2 \mod a_1 \in \left(\mathbb{Z}/a_1 \mathbb{Z}\right)^{\times}$. So there exists a multiplicative inverse $m_2 \in \left(\mathbb{Z}/a_1 \mathbb{Z}\right)^{\times}$ of $a_2$; or equivalently, there exists a nonegative integer $m_2 < a_1$ such that $m_2 \times a_2 \equiv_{a_1} 1$. This implies the following: There exists integers $m_2$ and $m_1$; $|m_2| < a_1$ and so $|m_1| \leq a_2+1$ such that $m_2a_2 = 1 + m_1a_1$, or equivalently, $m_2a_2-m_1a_1 = 1$.

So let $y$ be a sufficiently large integer, and let $k \in \{0,1,\ldots, a_1-1\}$ be such that $Na_1 + k = y$. Then $Na_1 +k(m_2a_2-m_1a_1) = y$, and $N-km_1$ is positive if $N > km_1$, where $k < a_1$ and $m_1 \leq a_2+1$. This will hold if $y$ is at least $a_1(a_1+1)(a_2+1)$. This completes the case for $k=2$.

Having established this for $k=2$ we now use induction to show this holds for general $k$. In particular, let $\{a_1,a_2,\ldots, a_{k+1}\}$ be a set of positive integers where the greatest common divisor is 1. We show using induction on $k$ that every integer $Y$ can be expressed $Y = \sum_{i=1}^{k+1} M_ia_i$. To this end, let $c =$gcd$(a_k,a_{k+1})$. Then by induction, for any sufficiently large integer $y$, there are nonegative integers $M_k$ and $M_{k+1}$ such that $M_ka_k+M_{k+1}a_{k+1} = cy$. So pick $y$ sufficiently large such that gcd$(a_1,\ldots, a_{k-1}, cy) = 1$; indeed any $y$ sufficiently large satisfying gcd$(a_1,\ldots, a_{k-1}, y) = 1$ will do [make sure you see why], and there is indeed such a positive integer $y$ [make sure you see why].

Then by the inductive hypothesis for any sufficiently large integer $Y$ there exist nonegative integers $M_1,\ldots, M_{k-1}, M_y$ such that $cyM_y + \sum_{i=1}^{k-1} M_ia_i = Y$, as $cy$ itself satisfies $cy = M_ka_k+M_{k+1}a_{k+1}$ the result follows.

---

ETA: HOWEVER, we do note that, setting $A = \max \{a_1,\ldots, a_k\}$ that we may assume WLOG that $k \leq 1+\log A$. Or more precisely, there is a subset $S$ of $\{1,\ldots, k\}$ of cardinality $\log A$ such that gcd$\{a_i; i \in S\}$ is 1. Then it would suffice to show that every significantly large number $Y$ can be written $Y=\sum_{i \in S} M_ia_i$ where each $M_i$ is a nonnegative integer.

Indeed, each $a_i$ can be written as a product of at most $\log A$ primes. So we build a set $a_{i_1},a_{i_2},a_{i_l}; l \leq 1+\log A$ such that gcd$\{a_{i_1},\ldots, a_{i_l}\} = 1$. Let us assume that using induction, that gcd$\{a_{i_1},\ldots, a_{i_j}\}$ is a composite number that has at most $\log A -j+1$ prime factors $p_1\ldots p_{\log A-j}$. Then there exists an $a_i$ such that at least one of $p_1,\ldots, p_{\log A-j+1}$ doesn't divide $a_i$. Then gcd$\{a_{i_1},\ldots, a_{i_j}, a_i\}$ is a composite number that has at most $\log A -j$ prime factors.