Combinations modulo a prime

My officemate Chris Scaduto and I are slowly working through Richard Stanley's Enumerative Combinatorics Vol. 1. One of the many interesting problems in this book asks to prove the following identity:

• $\binom{pa}{pb}\equiv \binom{a}{b} (\mathrm{mod}\, p)$ for any prime $p$ and $a,b \in \mathbb{N}_+$.

We found a pretty simple proof based on Wilson's theorem that $(p-1)!\equiv -1 (\mathrm{mod}\, p)$, but we were really surprised by the elegant combinatorial proof in the solutions section.

Later Chris found a similar problem from a math contest, and used it for the algebra course he's TAing:

• $\binom{a}{p}\equiv \lfloor \frac{a}{p} \rfloor (\mathrm{mod}\, p)$ for any prime $p$ and $a \in \mathbb{N}_+$.

He thought this was unexpected because of the appearance of the floor function. We noticed this could be proven by the same elegant combinatorial argument as in Stanley's book, and in fact we easily obtain the following generalization of both problems:

• $\binom{a}{pb}\equiv \binom{\lfloor \frac{a}{p}\rfloor }{b} (\mathrm{mod}\, p)$ for any prime $p$ and $a \in \mathbb{N}_+$.

Proof: We will count the number of ways to choose a subset of $pb$ elements from $a$ objects. First, divide the $a$ objects into $p$ rows of $k=\lfloor \frac{a}{p}\rfloor$ objects:

• $x_{1,1}, x_{1,2},\ldots,x_{1,k}$
• $x_{2,1}, x_{2,2},\ldots,x_{2,k}$
• $\cdots$
• $x_{p,1}, x_{p,2},\ldots,x_{p,k}$

with a leftover pile for the remainder. Imagine the rows are stacked on top of each other. 

First, let us count the number of subsets so that for each column, either every object is chosen or none is. Let us call such a subset smooth. The leftover pile contains fewer than $p$ elements so a smooth subset cannot contain any elements from the leftover pile (since its intersection with the $p$ rows has size a multiple of $p$). Therefore these subsets are obtained by choosing a subset of $b$ elements from a single row and then just copying this choice for every row: there are $\binom{\lfloor \frac{a}{p}\rfloor }{b}$ ways to do this.

Let us say that two choices of $pb$ subset are equivalent if they agree on the leftover pile and their corresponding columns are cyclic shifts of each other. This latter condition can be stated more precisely as: for every $i\le k$, there is an $n$ so that $x_{j,i}=x_{j\oplus_p n,i}$, where the $\oplus_p$ indicates that the sum is reduced $\mod p$ to be between 1 and $p$.

A nonsmooth subset $A$ must have some column $i$ for which there is $j$ with $x_{j,i}\in A$ and $j'$ with $x_{j',i}\not\in A$. Now by cyclically shifting the column, we see that the equivalence class of $A$ has size dividing $p$. This completes the proof. $\Box$

Stanley's book had some other extensions of this result in a different direction. By a more careful counting technique one can prove the following identity:

• $\binom{pa}{pb}\equiv \binom{a}{b} (\mathrm{mod}\, p^2)$ for any prime $p$ and $a,b \in \mathbb{N}_+$.

In fact, I think this was also true for $p^3$ replacing $p^2$. I wonder: how can we strengthen this result further?