Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|cite|improve this question
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
up vote 2 down vote accepted

The lcm of $\{3,4,15,24,30,40,60\}$ is 120.


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.

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.