= Solution
For integers $0\leq r\leq n$, the <binomial coefficient> is
$$
\binom nr=\frac{n!}{r!(n-r)!},
$$
the 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 $\binom nr$ choices, or contains it, leaving $\binom n{r-1}$ choices. These cases are disjoint and exhaustive, so
$$
\boxed{\binom{n+1}r=\binom nr+\binom n{r-1}\qquad(0<r\leq n).}
$$
If $p$ is a <prime number> and $0<r<p$, then
$$
r!\binom pr=p(p-1)\cdots(p-r+1).
$$
The right side is divisible by $p$, while $r!$ is <coprime> to $p$. Cancellation modulo $p$ proves the <prime-row binomial coefficient divisibility>
$$
\boxed{p\mid\binom pr\qquad(0<r<p).}
$$
Apply the <binomial theorem> in the polynomial ring modulo $p$. The intermediate coefficients just proved to vanish give
$$
(1+X)^p\equiv1+X^p\pmod p.
$$
Multiplying by $(1+X)^k$ yields
$$
(1+X)^{p+k}\equiv(1+X^p)(1+X)^k\pmod p.
$$
For $0\leq r\leq k<p$, the $X^p$ factor cannot contribute to the coefficient of $X^r$. Comparing coefficients proves the <binomial coefficient congruence across a prime row>
$$
\boxed{\binom{p+k}r\equiv\binom kr\pmod p.}
$$
This also covers $r=0$, when both sides are one.
Back to article page
