Combinatorial Proof for a $p\mid\binom{p}{k} \ \ \ \ \ 0<k<p$ .

I'm looking for a combinatorial proof to the following statement:

$$p\mid\binom{p}{k} \ \ \ , \ \ 0<k<p \ \ \ \ \ \ \text{and} \ \ p \ \text{is prime}.$$

Thank you.

-

Consider the set of all $f \colon {\mathbb Z}_p \to \{0,1\}$ which take 1 at exactly $k$ points. This set has $p \choose k$ elements. You can think of putting 0-1's in a circle.

Any such labelling can be rotated in exactly $p$ different ways, so the cardinality of the set divides $p$.

[If rotating did not change a labelling, then $f(x+i)=f(x)$ for some $i$. Because $i,p$ are coprime, $ai+bp=1$ for some integers; therefore $f(x)=f(x+ai)=f(x+1-bp)=f(x+1)$ and the function is constant, but this is impossible when $0<k<p$.]

A similar proof shows that $a^p \equiv a \pmod p$.

-
Very nice! Thank you! –  Salech Alhasov Apr 3 '12 at 10:12

If you count the number of $k$-element subsets of a $p$-element set that contain a given element and then sum over all $p$ elements, you get $k\binom pk$, since each element is in $k$ of the $\binom pk$ subsets. This is $p$ times the count for a single element, and since $p\nmid k$ for $0\lt k\lt p$, the factor $p$ must be in $\binom pk$.

-