Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

In section 4 of the article by Afred van der Poorten's A Proof That Euler Missed ... the following inequality is used:

$$\nu_{p}\displaystyle\binom{n}{m}\leq\left\lfloor\dfrac{\ln n}{\ln p}\right\rfloor-\nu_{p}(m)\qquad(\ast)$$

(In the original denoted $\text{ord}$ $_{p}(\cdot)$ instead of $\nu_p(\cdot)$).

where $\nu_{p}(k)$ is the $p$-adic valuation of $k\in\mathbb{Q}$, i. e. the exponent of the prime $p$ in the prime factorization of $k$. I know some properties of the foor function and that


$$\nu_{p}(a\cdot b)=\nu_{p}(a)\cdot \nu_{p}(b)$$


$$\nu_{p}(n!)=\displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{n}{p^{i}}\right\rfloor $$

but I didn't convince myself on the correct argument I should use to prove $(\ast )$.

Question: How can this inequality be proven?

share|cite|improve this question
up vote 6 down vote accepted

Since $\nu_p(n!)=\sum_i\lfloor n/p^i\rfloor$, $\nu_p\binom nm=\sum_i(\lfloor n/p^i\rfloor-\lfloor m/p^i\rfloor-\lfloor (n-m)/p^i\rfloor)$. Observe that each summand is $\le 1$, and for $i>\left\lfloor\frac{\ln n}{\ln p}\right\rfloor$ it's clearly $0$. That gives $v_{p}\binom{n}{m}\le \left\lfloor\frac{\ln n}{\ln p}\right\rfloor$.

Finally observe that for $i\le\nu_p(m)$ $\lfloor m/p^i\rfloor=m/p^i$, so ($\lfloor m/p^i\rfloor+\lfloor x/p^i\rfloor=\lfloor(m+x)/p^i\rfloor$ and) the corresponding summand is also $0$. That gives the inequality in question.

share|cite|improve this answer
Thanks! Very simple your explanation. – Américo Tavares Aug 19 '10 at 14:00

Theorem (Kummer): $\nu_p {n \choose m}$ is the number of carries it takes to add $m$ and $n-m$ in base $p$.

Now note that $\lfloor \frac{\ln n}{\ln p} \rfloor$ is the maximum possible number of carries and the last $\nu_p(m)$ digits of $m$ cannot be associated to any carries.

Kummer's theorem itself is not hard to prove; it more or less follows from the last identity you list.

share|cite|improve this answer
Thanks as well! To follow your proof I feel I need to learn more advanced concepts. I will try to do so. – Américo Tavares Aug 19 '10 at 20:16

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.