Prove that for $a, b \in \Bbb N^*$ we have : $$a {a+b \choose b} | LCM(b+1, ..., b+a)$$

Is there a simple proof of this result that doesn't involve computing an integral? I know a trick exploiting $\int_{0}^{1} {x^n(1-x)^mdx}$ but I am looking for a more "obvious" proof.


1 Answer 1


First note that $$a\binom{a+b}{b}=\frac{(a+b)!}{(a-1)!b!}$$

To prove that $a {a+b \choose b} | LCM(b+1, ..., b+a)$ it is enough to prove that for each prime $p$ we have $$p^n | LCM(b+1, ..., b+a)$$ where $n$ is the power of $p$ in $a\binom{a+b}{b}$.

We know by Legendre formula that $$n=\sum_{k}\lfloor \frac{a+b}{p^k} \rfloor -\lfloor \frac{b}{p^k} \rfloor-\lfloor \frac{a-1}{p^k} \rfloor$$

Now for each $k$ we have $$\lfloor \frac{b}{p^k} \rfloor+\lfloor \frac{a-1}{p^k} \rfloor \leq \frac{b}{p^k} + \frac{a-1}{p^k} \leq \frac{a+b}{p^k} $$

We also have $$\frac{a}{p^k} \leq \lfloor \frac{a-1}{p^k} \rfloor +1\\ \frac{b}{p^k} <\lfloor \frac{b}{p^k} \rfloor +1$$

Combining, we get $$\lfloor \frac{b}{p^k} \rfloor+\lfloor \frac{a-1}{p^k} \rfloor \leq \frac{a+b}{p^k} < \lfloor \frac{b}{p^k} \rfloor+\lfloor \frac{a-1}{p^k} \rfloor +2$$ which implies $$\lfloor \frac{a+b}{p^k} \rfloor -\lfloor \frac{b}{p^k} \rfloor-\lfloor \frac{a-1}{p^k} \rfloor \in \{ 0,1 \} $$

Now, let $K_0$ be the largest $k$ such that $$\lfloor \frac{a+b}{p^k} \rfloor -\lfloor \frac{b}{p^k} \rfloor-\lfloor \frac{a-1}{p^k} \rfloor =1 $$

Show that this implies that $p^{K_0}$ has a multiple between $b+1$ and $b+a$.

This shows that $p^{K_0}$ divides $LCM(b+1,..,b+a)$. Now, since all terms in the sum are 0 or 1, it follows that $n \leq K_0$ and hence $p^n | p^{K_0}$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .