A quick, cool result to distract you from finals

If you are like me, you’ve probably got lots to do for final exams and things of the like as the semester (trimester, quarter, whatever your school uses) comes to a close. In an effort to take a bit of break, I would like to present you with a cute little result I came across in my studies. It’s a nice little number theory fact with a cute combinatorial proof. I found the result in Hatcher’s book on algebraic topology, and I’ll present an adapted version of his proof (though I’m sure it’s in many other books).

First we need to remember a little about $p$ -adic representations of integers. If $n$ is any integer (technically we should assume $n\geq0$ , it doesn’t really matter), and if $p$ is a prime number, then $n$ can be written (uniquely) as $n=\sum_{l} n_lp^l$ , where $0\leq n_l<p$ are integers. This is easy to prove using the fundamental theorem of arithmetic and the division algorithm. Without further adieu I give you the following

Proposition: Let $p$ be a prime number and $n,k\in\mathbb{N}$ . Then

$\binom{n}{k}=\prod_l\binom{n_l}{k_l}\mod p$

where $n=\sum_l n_lp^l$ and $k=\sum_l k_lp^l$ are the $p$ -adic representations of $n$ and $k$ .
Proof: Recall that in the polynomial ring $\mathbb{Z_p}[x]$ , we have the identity $(1+x)^{p^j}=1+x^{p^j}$ . Working modulo $p$ , we have

$(1+x)^n=(1+x)^{n_0}(1+x^p)^{n_1}(1+x^{p^2})^{n_2}\dots$

$=\left(1+\binom{n_0}{1}x+\binom{n_0}{2}x^2+\dots+\binom{n_0}{p-1}x^{p-1}\right)\times$

$\left(1+\binom{n_1}{1}x^p+\binom{n_1}{2}x^{2p}+\dots+\binom{n_1}{p-1}x^{(p-1)p}\right)\times\dots$

On one hand, we know that the coefficient of $x^k$ in this expansion is $\binom{n}{k}$ . On the other hand, if we expand the product on the right, it’s easy to see that no two terms in the product will have the same power of $x^j$ . Thus, to compute the coefficient of $x^k$ in the expansion, we need to choose $x^{l_i}$ from each factor so that $\sum_i l_i=k$ . But we also know that in the $i$ ‘th factor, we have terms of the for $j_ip^i$ . In other words, we simply pick $l_i$ so that $\sum_l j_lp^l=k$ , which is exactly the $p$ -adic representation of $k$ . The coefficient on each of these terms if precisely $\binom{n_i}{k_i}$ , and so taking the product gives the result.

And that’s it! I hope you enjoyed it, and now I’ve got to get back to work!

About Ryan

I'm a software developer at Hudl where I work on awesome software. Before that, I was a grad student in mathematics, interested in probability theory as well as analysis, more on the side of functional analysis and less on the side of PDEs. Apart from that I'm pretty lame. Though I do enjoy watching football, playing golf, and playing the trumpet.

View all posts by Ryan →

This entry was posted in Asides, Combinatorics. Bookmark the permalink.