Binomial Coefficient of Prime Plus One Modulo Prime

Theorem

Let $p$ be a prime number.

Then:

$\displaystyle 2 \le k \le p-1 \implies \binom {p+1} k \equiv 0 \pmod p$

where $\displaystyle \binom {p+1} k$ is a binomial coefficient.

Proof

From Binomial Coefficient of Prime, we have:

$\displaystyle \binom p k \equiv 0 \pmod p$

when $1 \le k \le p-1$.

From Pascal's Rule we have:

$\displaystyle \binom {p+1} k = \binom p {k - 1} + \binom p k$

The result follows immediately.

$\blacksquare$

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.6$: Exercise $10 \ \text{d}$