Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.

Solution 1:

The following is a combinatorial argument.

Draw $a$ concentric circles and divide them radially into $p$ parts each. There are then a total of $pa$ regions. There are $\binom{pa}{pb}$ ways to select $pb$ of these regions. Consider the action of rotation by $2\pi/p$ on these selections. There are $\binom{a}{b}$ selections which are fixed by the rotation: these are the selections that consist of $b$ complete annuli. All others fall into orbits of size $p$. The desired conclusion $$\binom{pa}{pb} \equiv \binom{a}{b}\, (\text{mod}\,p)$$ follows.

Solution 2:

$$(1+x)^{pa}= \sum_{n=0}^{pa} {pa \choose n} x^{n}$$

\begin{align} (1+x)^{pa}=\left ((1+x)^{p} \right )^a=\left (\sum_{k=0}^{p}{p \choose k}x^{k} \right )^{a} \Rightarrow\\ \end{align}

\begin{align} (1+x)^{pa}&\equiv\left (\sum_{k=0}^{p}{p \choose k}x^{k} \right )^{a} \mod p\\ &\equiv(1+x^p)^{a} \mod p\\ &\equiv \sum_{i=0}^{a} {a \choose i}x^{pi} \mod p \end{align}

Equating coefficients $\mod p$ it yields $$ { pa \choose pb} \equiv {a\choose b} \mod p$$