# Reducing a sum of numbers that equals a multiple of lcm

I came across the following problem and I just can't solve it.

Suppose that $x_1,...,x_k \in \Bbb N$ and $c_1,...,c_k \in \Bbb N$ are such that $\sum_{j=1}^k c_j x_j$ is a multiple of $\operatorname{lcm}(x_1,...,x_k)$. Show that there exist integers $0 \leq d_j \leq c_j$ such that $\sum_{j=1}^k d_j x_j =\operatorname{lcm}(x_1,...,x_k)$.

-
Where did you come across it? – Matthew Conroy Nov 1 '13 at 21:43
A problem in commutative algebra seems to boil down to this question. It is about generators in a graded algebra. I wanted to write down that problem initially, but I was able to solve that with a different(perhaps more standard method). But I am still interested in seeing a solution or counter-example of this seemingly indeoendent question. – Hammerhead Nov 2 '13 at 5:06
It might be possible with $| d_j | \le c_j$. – NovaDenizen Dec 8 '13 at 23:14
@NovaDenizen Interesting; do you have a proof of that? – Post No Bulls Dec 9 '13 at 7:01
@Post No Bills nope. – NovaDenizen Dec 10 '13 at 14:48

The lcm of $\{3,4,15,24,30,40,60\}$ is 120.
$$3+4+15+2\times24+30+2\times40+60=2\times120$$
Now suppose $3a+4b+15c+24d+30e+40f+60g=120$ with the appropriate bounds on $a,b,\dots,g$. Looking at it modulo 10, we need $a=b=c=1$, $d=2$, so we get $$30e+40f+60g=50$$ which is impossible.
EDIT: A smaller example. The lcm of $\{1,6,10,15\}$ is 30. $$1+4\times6+2\times10+15=2\times30$$ But no subsum of the left side can give 30; to get a multiple of 5, you need the 1 and all four sixes, which makes 25, so no way to get to 30.