Combinatorial Proof of $p \mid {p \choose k}$

Question

I found an 11 year old proof of the statement “if $p$ is prime and $ 0 < k < p$ then $p \mid {p \choose k}$” by Joriki here. It is as follows:

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 {p \choose k}$, since each element is in $k$ of the ${p \choose k}$ subsets. This is $p$ times the count for a single element, and since $p \nmid k$ for $0<k<p$, the factor $p$ must be in $p \choose k$.

I know that if $p$ is not prime, then the statement does not hold for general $n$ and $k$, only with $n$ and $k$ coprime. However, I don’t see how this fact is reflected within the proof itself. My understanding is:

• We take all $k$-subsets of a set of cardinality $p$, with the condition they have all the element $a$ in them. There are ${p-1 \choose k-1}$ of these, and if we do this once for each element we get $$p {p-1 \choose k-1} = \frac{p!}{(k-1)! (p-k)!} = k {p \choose k}$$ Which makes sense as we have looked at each $k$-subset once for each element.

• Next, we know that this was $p$ times the count of a single element, so $p \mid k {p \choose k}$, and as $0 < k < p$, we find $p \mid {p \choose k}$.

I think that the idea that depends on $p$ being prime is in the last step, and I also think that it is close to something like:

• if $n$ and $k$ are not relatively prime then we can take a common factor out, then it is not nessecarily the fact that $n \mid {n \choose k}$

but I don’t understand why it invalidates the conclusion even if that is true.

Answer 1

It's perhaps easiest to see what goes wrong by looking at a particular example. For $n=6$ we will get $6\mid k\binom 6k$, where $0<k<6$.

Now $6\mid\binom 6k$ is equivalent to $2\mid \binom 6k$ and $3\mid\binom 6k$. We know that $2\mid k\binom 6k$ and $3\mid k\binom 6k$, but we don't know that $2\not\mid k$ and $3\not\mid k$ - in fact we only know that at least one of these statements holds.

Answer 2

Let's sketch a way to combinatorialize that argument. Consider a string $s_0=a_0\dots a_{p-1}$ of length $p$ with $k$ $1$'s and $p-k$ $0$'s, along with all of its cyclic rotations $s_i=a_i\dots a_{p-1} a_0\dots a_{i-1}$ for $1\le i\le p-1$. We claim that if $s_0$ is nonconstant, then strings $s_0,s_1,\dots,s_{p-1}$ are all distinct.

If not, then let $i_0=\min\{1\le i\le p-1\mid s_i=s_0\}$. A version of the Euclidean algorithm shows then that $i_0$ divides $p$ (if not, then $0<i_1=i_0\left\lceil\frac{p}{i_0}\right\rceil-p<i_0$ and $s_{i_1}=s_0$, so $i_0\ne\min\{1\le i\le p-1\mid s_i=s_0\}$, a contradiction). But $p$ is prime, so $i_0=1$, and therefore, the string $s_0$ has period $1$, i.e. is constant, so $k=0$ or $k=p$. Thus, if $k\ne 0,p$, then the set of strings of length $p$ with exactly $k$ $1$'s can be partitioned into parts that each contain all cyclic rotations of a single string, with $p$ strings in each part. Thus, $p$ divides $\binom{p}{k}$.