# Conceptual proof that $p\choose k$ ($1 < k < p$) is divisible by $p$ when $p$ is prime? (I.e., no equations).

If $n,k\in \mathbf{N}$, then one defines $n\choose k$ to be the number of ways to choose $k$ elements from a set of size $n$. One can then show (by a combinatorial argument) that $${n\choose k} = \frac{n!}{k!(n-k)!}$$ whenever $n\choose k$ is defined. In particular, since this expression is an integer for all $n$ and $k$, when $n=p$ is a prime, $p|{p\choose k}$ when $1< k<p$.

I've wondered sometimes if there is also a proof of this fact which does not use the formula above; i.e., maybe one can see it by using the definition of $n\choose k$? What do you think?

-
Let's start from Fermat's little theorem: $a^p \equiv a \bmod p$ for all integers $a$. Now consider the polynomial $(X+1)^p - X^p - 1$ in $({\mathbf Z}/p{\mathbf Z})[X]$. This polynomial has degree less than $p$, since after expanding $(X+1)^p$ the two $X^p$ terms cancel. But also it vanishes at all $p$ numbers in ${\mathbf Z}/p{\mathbf Z}$. Therefore $(X+1)^p - X^p - 1 = 0$ as a polynomial. Since the left side is $\sum_{k=1}^{p-1} \binom{p}{k}x^k$, we get $\binom{p}{k} \equiv 0 \bmod p$ for $1 \leq k \leq p-1$. –  KCd May 20 '12 at 21:47
KCd: Your claim that "if $P\in\mathbf{Z}/p\mathbf{Z}[X]$ is zero at every $\alpha\in \mathbf{Z}/p\mathbf{Z}$ then $P$ is the zero polynomial" is false in general; consider $X^p - X$. However it is the case that $(X+1)^p - X^p - 1$ is the zero polynomial; this just follows from the fact that $\mathbf{Z}/p\mathbf{Z}[X]$ is a ring of characteristic $p$, and thus the map $F\mapsto F^p$ is a ring homomorphism. However, to prove that it's a homomorphism you have to use that $p|{p\choose k}$... Correct me if I've misunderstood. –  vgty6h7uij May 20 '12 at 22:11
KCd Ah nevermind - you're counting roots, I see. –  vgty6h7uij May 20 '12 at 22:26

You can group your subsets of size $k$ in families of size $p$ when they differ only by a "translation".

That is, if one of your subsets contains $a_1, \dots, a_k$, the other contains exactly the elements $a_i+d$, but regarded modulo $p$ to be again in the set $\{1,2,\dots, p\}$.

-
A slightly more general version of this argument can be used to prove Lucas' theorem (en.wikipedia.org/wiki/Lucas'_theorem). –  Qiaochu Yuan May 20 '12 at 16:12
@QiaochuYuan Do you refer to the "main lemma" one usually uses in a proof of Lucas or to the whole factorisation? –  Phira May 20 '12 at 16:16
Phira: Nice! Thanks. –  vgty6h7uij May 20 '12 at 16:24
    p(choose)k= p! / (k! (p-k)!) = r


Since k and p-k are both less than p, and p is prime, there can be no factors of p in k! (p-k)! since this is a product of numbers strictly less than p, and none of those (other than 1) can divide p.

   Hence, since p! = r (k! (p-k)!) has a factor of p, r must have a factor of p.

-