Proving ${n \choose p} \equiv \Bigl[\frac{n}{p}\Bigr] \ (\text{mod} \ p)$

Hint $\ $ If $\rm\ n\equiv j\ \: (mod\ p)\: $ and $\rm\: \bigl[\frac{n}{p}\bigr] = k, \: $ then pairing factors so that top $\equiv$ bottom $\rm\:(mod\ p)\:$ in the binomial coefficient fractions below makes the result obvious. For example

$${17\choose 7}\ =\ \frac{17}3 \frac{16}2 \frac{15}1 \color{#c00}{\frac{14}7}\frac{13}6\frac{12}5\frac{11}4\,\equiv\, \color{#c00}2\, =\, \left\lfloor\frac{17}7\right\rfloor\pmod 7\qquad\qquad\ $$

since all of the fractions with bottom $\rm\ne p\,$ are $\,\rm\equiv 1\pmod p\,$ by top $\equiv$ bottom, and the red term with the bottom = $\rm \,p = 7\,$ is just $\rm\,\color{#c00}{kp/p = k}.\,$ Generally we have

$$\begin{eqnarray}\rm {n \choose p}\ &=&\rm\ \frac{n\:(n-1)\:\cdots\:(n-p+1)}{p\:(p-1)\:\cdots\: 1} \\ \\ &=&\ \rm \frac{n}{j}\ \frac{n-1}{j-1}\cdots\frac{kp+1}{1}\ \color{#c00}{\frac{kp}p}\ \frac{kp-1}{p-1}\:\cdots\frac{n-p+2}{j+2}\ \frac{n-p+1}{j+1}\end{eqnarray}$$

This is a very special case of much more general arithmetical results on binomial coefficients. For example, see Andrew Granville's very interesting survey The Arithmetic Properties of Binomial Coefficients

Remark The above proof is a special case of a very simple purely arithmetical proof that I devised to show that binomial coefficients are integral. Namely, the same idea of exploiting the innate symmetry by aligning the numerators and denominators $\rm\:(mod\ p)\:$ extends to yield a simple algorithm that, given a binomial coefficient and a prime $\rm p$, rewrites the binomial coefficient as a product of fractions whose denominators are all coprime to $\rm p$. This implies that no prime divides the lowest-terms denominator, so that we may therefore conclude that the binomial coefficient is integral. For an example and further discussion see my post here.

A useful result in such problems is Lucas's Theorem which states that

If $p$ is a prime and if $a = \sum_{i=0}^{k} a_{i} p^{i}, \ 0 \le a_i < p \ $ i.e. the $a_i$ are digits of $a$ in base $p$ and similarly $b = \sum_{i=0}^{k} b_{i}p^{i}$ (pad with zeroes if required) then

$${a \choose b} = \prod_{i=0}^{k} {a_i \choose b_i} \mod p$$

In our case $n=a$ and $b=p$. Since $b = p$ we have $b_1 = 1$ and rest of the $b_i = 0$.

Thus

$${a \choose p} = {a_1 \choose 1} = a_1 \mod p$$

It is easy to see that $a_1 = [\frac{a}{p}] \mod p$.

Here's another way to look at it. Suppose $n=kp+j,$ for $0 \le j \le p-1.$ Then

$$ (p-1)! {n \choose p} = \frac{n(n-1) \cdots (n-p+1)}{p} = \left( {n-j \over p} \right) \prod_{i=0,i\ne j }^{p-1} (n-i)$$ $$ \equiv k(p-1)! (\textrm{ mod } p). $$ Since the product runs through a complete set of non-zero residues mod p.