Binomial Coefficient involving Prime

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $p$ be a prime number.

Let $\dbinom n p$ be a binomial coefficient.


Then:

$\dbinom n p \equiv \floor {\dfrac n p} \pmod p$

where:

$\floor {\dfrac n p}$

denotes the floor function.


Proof

Follows directly from Lucas' Theorem:

$\dbinom n k \equiv \dbinom {\floor {n / p} } {\floor {k / p} } \dbinom {n \bmod p} {k \bmod p} \pmod p$

where $k = p$.


Then:

$k \bmod p = 0$

and so by Binomial Coefficient with Zero:

$\dbinom {n \bmod p} {k \bmod p} = 1$

Also:

$\floor {k / p} = 1$

and by Binomial Coefficient with One:

$\dbinom {\floor {n / p} } {\floor {k / p} } = \floor {\dfrac n p}$


Thus:

$\dbinom n p \equiv \floor {\dfrac n p} \times 1 \pmod p$

Hence the result.

$\blacksquare$


Sources