Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 4 / 2E / Solution

For integers $0\le r\le n$, the binomial coefficient isthe number of $r$-element subsets of an $n$-element set. It is zero outside that range. To obtain Pascal's identity, distinguish one element of an $(n+1)$-element set. An $r$-element subset either omits it, giving $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ choices, or contains it, leaving $\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$ choices. These cases are disjoint and exhaustive, so

If $p$ is a prime number and $0<r<p$, thenThe right side is divisible by $p$, while $r!$ is coprime to $p$. Cancellation modulo $p$ proves the prime-row binomial coefficient divisibilityApply the binomial theorem in the polynomial ring modulo $p$. The intermediate coefficients just proved to vanish giveMultiplying by $(1+X{)}^k$ yieldsFor $0\le r\le k<p$, the $X^p$ factor cannot contribute to the coefficient of $X^r$. Comparing coefficients proves the binomial coefficient congruence across a prime rowThis also covers $r=0$, when both sides are one.