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

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

• Yes.$\phantom{}$ Jan 2, 2019 at 23:49
• Consider just the case $k=2,a_1=3,a_2=7$ for clarity. Can you see that the coefficient of $x^n$ in $$(1+x^3+x^6+x^9+\ldots)(1+x^7+x^{14}+x^{21}+\ldots)$$ is exactly the number of ways for writing $n$ as $3A+7B$? Jan 2, 2019 at 23:51
• Well, by geometric series $(1+x^3+x^6+\ldots)=\frac{1}{1-x^3}$ and $(1+x^7+x^{14}+\ldots)=\frac{1}{1-x^7}$. Jan 2, 2019 at 23:53
• The meromorphic function $\frac{1}{(1-x^3)(1-x^7)}$ has a double pole at $x=1$ but the other singularities are all simple poles. Any simple pole provides a bounded contribution, since the coefficients of $\frac{1}{1-x\xi}$ have unit modulus for $\xi\in S^1$, hence the magnitude of the representation function is linear, since $[x^n]\frac{1}{(1-x)^2}=\Theta(n)$. Jan 2, 2019 at 23:55
• Linear and with a bounded perturbation implies strictly positive from some point on - the hidden constant in $\Theta$ is not really important, but it can be derived from stars and bars. Jan 2, 2019 at 23:56

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

• How do you get the coefficients all integers though? I see that $k=\sum c_ia_i$ where each $c_i$ is rational....
– Mike
Jan 4, 2019 at 18:08
• *nonegative rational
– Mike
Jan 4, 2019 at 18:16
• @Mike: It's a generalization of Bézout's identity. (How would they become non-integral?) Jan 4, 2019 at 18:45
• Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ]
– Mike
Jan 4, 2019 at 18:48
• @Mike: Your "direct way" seems to look a lot longer than mine, though. Jan 4, 2019 at 18:52

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.

• Editted for clarity. Caught a crucial typo!
– Mike
Jan 4, 2019 at 18:38