4
$\begingroup$

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

$ p\mid\binom{p}{k} \ \ \ , \ \ 0

Thank you.

2 Answers 2

5

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$.

  • 0
    Very nice! Thank you!2012-04-03
6

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$.