MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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'_1, m'_2, \dots,m'_r$ satisfying $m'_1c_1 + m'_2c_2 + \dots + m'_rc_r = k$ such that $|m'_1|+|m'_2|+\dots+|m'_r| \leq poly(n)$. Here $poly(n)$ means $O(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)$.

share|cite|improve this question
You should be able to prove c <= 2. More specifically, I am having a hard time imagining a size-minimal case where any m' has size larger than n. Use literature on Bezout's theorem and the Euclidean algorithm if you need something to cite. Gerhard "Ask Me About System Design" Paseman, 2011.03.09 – Gerhard Paseman Mar 10 '11 at 4:20
Also, there are cases where r=3 and at least one m' is \Omega(n), so I will be surprised if you find c < 1. Gerhard "Ask Me About System Design" Paseman, 2011.03.09 – Gerhard Paseman Mar 10 '11 at 4:25
I assume you're looking for a $poly(n)$ that's uniform over all choices of $c_1,\dots,c_r$ (perhaps with $r$ fixed). Otherwise you can just write $g=\gcd\{c_1,\dots,c_r\}$, fix a solution to $m_1c_1+\cdots+m_rc_r=g$, and then scale by the integer $k/g$. – Greg Martin Mar 11 '11 at 22:10

These papers may not deal with exactly this question, but with very closely related ones, and are probably worth a look:

Borosh, Flahive, Rubin, Treybig, A sharp bound for solutions of linear Diophantine equations, Proc. Amer. Math. Soc. 105 (1989), no. 4, 844–846, MR0955458 (89i:15022).

Borosh, Flahive, Treybig, Small solutions of linear Diophantine equations, Discrete Math. 58 (1986), no. 3, 215–220, MR0831816 (87e:11029).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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