Congruence between binomial coefficient and integer part.

Question

If $p$ is a prime number, prove that $\forall n \in \mathbb{N}$ we have:

$$\binom{n}{p} \equiv \Bigg[\frac{n}{p}\Bigg] \mod p ,$$

where $[m]$ denotes the integer part of a real number $m$.

Answer 1

Consider that: $$\binom{n}{p}=\frac{n(n-1)\cdot\ldots\cdot(n-p+1)}{p(p-1)\cdot\ldots\cdot 1}\tag{1}$$ and that among $n,(n-1),\ldots,(n-p+1)$ there is exacly one multiple of $p$, say $mp$, with $m=\left\lfloor\frac{n}{p}\right\rfloor$. The same obviously happens with $p,(p-1),\ldots,1$. So we get that after cancelling the terms that are multiples of $p$ in the numerator and in the denominator of the RHS of $(1)$, we are left with $m$ times an integer ratio of two integers $\equiv -1\pmod{p}$, since $$(p-1)!\equiv -1\pmod{p}$$ holds by Wilson's theorem. Since such a ratio is necessary $\equiv 1\pmod{p}$, $$\binom{n}{p}\equiv m\pmod{p}$$ follows.

Answer 2

A combinatorial solution: Divide $n$ by $p$ with remainder: write $n=ap+b$ where $0 \leq b < p$, such that $a = \lfloor \frac{n}{p} \rfloor$. We now divide the first $ap+b$ positive integers in $a$ groups of $p$ and one group of $b$: $$ \underbrace{\underbrace{1,2,\ldots,p}_p, \underbrace{p+1, \ldots, 2p}_{p}, \ldots, \underbrace{ap-p+1, \ldots, ap}_{p}}_a, \underbrace{ap+1, \ldots, ap+b}_b $$ The binomial coefficient $\binom{n}{p} = \binom{ap+b}{p}$, by definition, gives the number of ways to choose $p$ of these numbers. Define $f: \{1,2,\ldots,ap+b\} \to \{1,2,\ldots,ap+b\}$ as follows: $f(x)=x$ for $x>ap$, $f(x)=x+1$ for $x \leq ap$ such that $p \nmid x$ and $f(x)=x-p+1$ when $p \mid x$. It is easy to check that $f$ is a bijection (it keeps the numbers larger than $ap$ fixed and cyclically permutes the numbers in the sets $V_1 = \{1,2,\ldots,p\}$, $\ldots,$ $V_a = \{ap-p+1,\ldots,ap\}$). If $S$ is a set of $p$ of the numbers $\{1,2,\ldots,ap+b\}$, the set $f(S)$ is as well. We have $f^p(S)=S$. Consider the function $f$ acting on the set $\mathcal{T}$ of all $p$-element subsets of $\{1,2,\ldots,ap+b\}$ (we have $|\mathcal{T}| = \binom{ap+b}{p}$). The sets $V_1$, $\ldots$, $V_a$ are fixed under $f$, so each of them has an orbit of length one. All other sets have orbits of length $p$ (since $f$ does not fix them but $f^p$ does). It follows that $\binom{n}{p} - a = |\mathcal{T}| - a$ is divisible by $p$.

Answer 3

Notice that $$\binom{n+p}{p} \equiv \binom{n}{p}+1$$

Indeed:

$$\binom{n+p}{p} = \sum_{k+l=p}\binom{n}{k} \cdot \binom{p}{l}$$

For $0<l<p$ the factors $\binom{p}{l}$ are divisible by $p$.

Apply induction.

Obs:It's true in fact for all $n\ge 0$

Also check http://en.wikipedia.org/wiki/Lucas%27_theorem