Binomial Coefficient of Prime Minus One Modulo Prime

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $p$ be a prime number.


Then:

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

where $\dbinom {p - 1} k$ denotes a binomial coefficient.


Proof

From Binomial Coefficient of Prime, we have:

$\dbinom p k \equiv 0 \pmod p$

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

From Pascal's Rule:

$\dbinom {p-1} k + \dbinom {p - 1} {k - 1} = \dbinom p k \equiv 0 \pmod p$

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

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

But from Binomial Coefficient with Zero:

$\dbinom {p - 1} 0 = 1 \equiv 1 \pmod p$

So:

$\dbinom {p - 1} 1 \equiv -1 \pmod p$

Then:

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

and so:

$\dbinom {p - 1} 2 \equiv 1 \pmod p$

The result follows.

$\blacksquare$


Sources