I'm looking for a combinatorial proof to the following statement:
$ p\mid\binom{p}{k} \ \ \ , \ \ 0
Thank you.
I'm looking for a combinatorial proof to the following statement:
$ p\mid\binom{p}{k} \ \ \ , \ \ 0
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
A similar proof shows that $a^p \equiv a \pmod p$.
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$.