Binomial Coefficient of Prime Minus One Modulo Prime

From ProofWiki

Jump to: navigation, search

Theorem

Let $p$ be a prime number.

Then:

$\displaystyle 0 \le k \le p-1 \implies \binom {p-1} k \equiv \left({-1}\right)^k \pmod p$

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

$\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-1} {k - 1} = \binom p k \equiv 0 \pmod p$

This certainly holds for $k = 1$, and so we have:

$\displaystyle \binom {p-1} 1 + \binom {p-1} 0 = \binom p 1 \equiv 0 \pmod p$

But $\displaystyle \binom {p-1} 0 = 1 \equiv 1 \pmod p$.

So $\displaystyle \binom {p-1} 1 \equiv -1 \pmod p$.

Then:

$\displaystyle \binom {p-1} 2 + \binom {p-1} 1 = \binom p 2 \equiv 0 \pmod p$

... and so $\displaystyle \binom {p-1} 2 \equiv 1 \pmod p$.

The result follows.

$\blacksquare$