Sum of products with bounded coefficients The following lemma is not hard to prove.

Lemma : Let $c_1 \neq c_2 \neq \dots \neq c_r \in [n]$ and $k \in [n]$. If $m_1, m_2, \dots, m_r$ are integers (some of them might be negative) such that $m_1c_1 + m_2c_2 + \dots + m_rc_r = k$, then $\exists$ integers $m&#39;_1, m&#39;_2, \dots,m&#39;_r$ satisfying $m&#39;_1c_1 + m&#39;_2c_2 + \dots + m&#39;_rc_r = k$ such that $|m&#39;_1|+|m&#39;_2|+\dots+|m&#39;_r| \leq poly(n)$. Here $poly(n)$ means $n^c$ for some positive constant $c$.

I am guessing that the above lemma is well known. I am looking for a reference of the above lemma and the best possible bound for $poly(n)$.
An $O(n^2 \log r)$ bound can be obtained by Bézout's lemma:


  Lemma. For every integers $0 &lt; c_i \leq n$, $\gcd(c_1,\ldots,c_r) = \sum_i m_i c_i$ for some integers $m_i$ with $|m_i| \leq n \log r$.


This lemma is obtained by recursively applying Bézout's lemma on two variables and the identity $\gcd(x_1,x_2,x_3) = \gcd(\gcd(x_1,x_2),x_3)$.

Without loss of generality assume that $\gcd(c_1,\ldots,c_r) = 1$ by dividing $\gcd(c_1,\ldots,c_r)$ on both sides of $\sum_i m_i c_i = k$. By Bézout's lemma there exists integers $m_i$ with $|m_i| \leq n \log r$ such that 

$$k \cdot \sum_i m_i c_i = \sum_i (k \cdot m_i) c_i = k \cdot 1 \text,$$

by observing $k = O(n)$ we have the desired $m'_i = k \cdot m_i$ with $|m'_i| = O(n^2 \log r)$.



If you are searching for literature, the keyword is inhomogeneous linear Diophantine  equations, that is the equation $\sum_i m_i c_i = k$ when $k = 0$. For the homogeneous one, one can obtain a linear bound on $|m_i'|$, see e.g. this or this paper. As for the inhomogeneous one, I have not yet found such a result; however this paper seems relevant.