Binomial Coefficient of Prime

Theorem

Let $p$ be a prime number.

Then:

$\displaystyle \forall k \in \Z: 0 < k < p: \binom p k \equiv 0 \pmod p$

where $\displaystyle \binom p k$ is defined as a binomial coefficient.

Proof

Since:

$\displaystyle \binom p k = \frac {p \left({p-1}\right) \left({p-2}\right) \cdots \left({p-k+1}\right)} {k!}$

is an integer, we have that:

$k! \backslash p \left({p-1}\right) \left({p-2}\right) \cdots \left({p-k+1}\right)$.

But since $k < p$ it follows that:

$k! \perp p$

i.e. that $\gcd \left\{{k!, p}\right\} = 1$.

So by Euclid's Lemma:

$k! \backslash \left({p-1}\right) \left({p-2}\right) \cdots \left({p-k+1}\right)$.

Hence:

$\displaystyle \binom p k = p \frac {\left({p-1}\right) \left({p-2}\right) \cdots \left({p-k+1}\right)} {k!}$

Hence the result.

$\blacksquare$

Alternative Proof

Lucas' Theorem gives:

$\displaystyle \binom n k \equiv \binom {\left \lfloor {n / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \binom {n \bmod p} {k \bmod p} \pmod p$

So, substituting $p$ for $n$:

$\displaystyle \binom p k \equiv \binom {\left \lfloor {p / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \binom {p \bmod p} {k \bmod p} \pmod p$

But $p \bmod p = 0$ by definition.

Hence, if $0 < k < p$, we have that $k \bmod p \ne 0$, and so:

$\displaystyle \binom {p \bmod p} {k \bmod p} = \binom 0 {k \bmod p} = 0$

by definition of binomial coefficients.

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{b}$
• George E. Andrews: Number Theory (1971): $\S 3.1$: Exercise $9$