Pascal's triangle revisited

Recall $$\left( \begin{array}{c} n \\ k \end{array}\right)={n!\over k!(n-k)!}$$ denotes the combinatorial symbol ``$n$ choose $k$ ''.

If $p$ is any prime then $$p\vert \left( \begin{array}{c} p \\ k \end{array}\right)$$ , for $k=1,2,...,p-1$ . (We saw cases of this in Example 1.2.36 above.) This is because $p$ divides $p!$ but $p$ does not divide $k!$ nor $(p-k)!$ ($k<p$ ).

Let $p^{b_k}$ be the largest power of $p$ that divides $$\left( \begin{array}{c} p \\ k \end{array}\right)$$ , where $b_k=b_k(p)\geq 0$ is an integer. The above reasoning tells us that $b_1=0$ , $b_p=0$ and $b_1>0$ for $0<k<p$ . The exact value of $b_k$ has been known for over 150 years. In 1855, Kummer discovered that $b_k$ is equal to the number of ``carries'' required when adding $k$ and $p-k$ in base $p$ . For a discussion of this and many other remarkable facts about binomial coefficients, see A. Granville's excellent paper [G].