p-Adic Valuation of a Binomial Coefficient (Kummer's Theorem)

Prime Factorization of Binomial Coefficients

Legendre's formula shows us how to count the power of a prime in a factorial. Now, we introduce an important notation in number theory.

$\nu_p(a)$ is the largest integer $\alpha$ so that $p^\alpha$ divides $a$. That is, if $p^\alpha|a$ but $p^{\alpha+1}\not|a$ then $\alpha=\nu_p(a)$. Here, $a|b$ means that $a$ divides $b$. Usually, we use this notation for primes $p$.

For example, $\nu_3(108)=3$ since $108=3^3\cdot2^2$ and $\nu_5(11)=0$.

It is great if you got them all correct. If you understood the above questions correctly, we can proceed next.

Note that, now we can write the power of prime in factorial as, \begin{eqnarray*} \nu_p(n!) & = & \left\lfloor\frac{n}{p^1}\right\rfloor+ \left\lfloor\frac{n}{p^2}\right\rfloor+ \left\lfloor\frac{n}{p^3}\right\rfloor+\ldots\infty\newline & = & \sum\limits_{i=1}^{\log_p{n}}\left\lfloor\frac{n}{p^i}\right\rfloor \end{eqnarray*} We are ready to write binomial coefficients in terms of this now. Consider the binomial coefficient $\binom nk$. \begin{eqnarray*} \nu_p\left(\binom nk\right) & = & \nu_p\left(\dfrac{n!}{k!(n-k)!}\right)\newline & = & \nu_p(n!)-\nu_p\left(k!(n-k)!\right)\newline & = & \nu_p(n!)-\left(\nu_p(k!)+\nu_p(n-k)!\right)\newline & = & \nu_p(n!)-\nu_p(k!)-\nu_p(n-k)!\newline & = & \left\lfloor\frac{n}{p^1}\right\rfloor+ \left\lfloor\frac{n}{p^2}\right\rfloor \left\lfloor\frac{n}{p^3}\right\rfloor+\ldots\infty\newline & & -\left(\left\lfloor\frac{k}{p^1}\right\rfloor+ \left\lfloor\frac{k}{p^2}\right\rfloor+ \left\lfloor\frac{k}{p^3}\right\rfloor+\ldots\infty\right)\newline & & -\left(\left\lfloor\frac{n-k}{p^1}\right\rfloor+ \left\lfloor\frac{n-k}{p^2}\right\rfloor+ \left\lfloor\frac{n-k}{p^3}\right\rfloor+\ldots\infty\right) \newline & = & \sum\limits_{i\geq1}\left\lfloor\frac{n}{p^i}\right\rfloor-\left\lfloor\frac{k}{p^i}\right\rfloor-\left\lfloor\frac{n-k}{p^i}\right\rfloor\newline & = & \sum\limits_{i=1}^{\log_p{n}} \left\lfloor\frac{n}{p^i}\right\rfloor- \left\lfloor\frac{k}{p^i}\right\rfloor- \left\lfloor\frac{n-k}{p^i}\right\rfloor \end{eqnarray*} In the last line, notice that, it is enough to take just $\log_p{n}$. We don't need to make the expression uglier by taking $\log_p{k}$ or $\log_p{n-k}$ since $\log_p{n}$ is the largest.

The last expressions seem ugly, but understanding them is quite easy. So, try this in problems! We will head for Kummer's theorem later. Or hopefully, someone else will write Kummer's theorem by then already! Have fun. We will also use these properties in Erdos's elementay proof of Bertrand's Theorem. So, make sure you get each of those lines! Cheers.