Binomial Coefficient involving Prime

Theorem

Let $p$ be a prime number.

Let $\displaystyle \binom n p$ be a binomial coefficient.

Then:

$\displaystyle \binom n p \equiv \left \lfloor {\frac n p}\right \rfloor \pmod p$

where:

$\displaystyle \left \lfloor {\frac n p}\right \rfloor$

denotes the floor function.

Proof

Follows directly from Lucas' Theorem:

$\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$

When $k = p$ we have that:

• $k \bmod p = 0$ and so:

$\displaystyle \binom {n \bmod p} {k \bmod p} = 1$

• $\left \lfloor {k / p} \right \rfloor = 1$ and so:

$\displaystyle \binom {\left \lfloor {n / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} = \left \lfloor {n / p} \right \rfloor$

$\blacksquare$

Sources

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