Pascal's triangle revisited

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

If $ p$ is any prime then \begin{displaymath}p\vert \left( \begin{array}{c} p \ k \end{array}\right)\end{displaymath}, 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 \begin{displaymath}\left( \begin{array}{c} p \ k \end{array}\right)\end{displaymath}, 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].

David Joyner 2007-09-03