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\mid{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?

  • $\begingroup$ math.stackexchange.com/questions/127551 $\endgroup$ – sdcvvc May 20 '12 at 16:30
  • 1
    $\begingroup$ 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$. $\endgroup$ – KCd May 20 '12 at 21:47
  • $\begingroup$ 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. $\endgroup$ – vgty6h7uij May 20 '12 at 22:11
  • $\begingroup$ KCd Ah nevermind - you're counting roots, I see. $\endgroup$ – 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\}$.

  • 3
    $\begingroup$ A slightly more general version of this argument can be used to prove Lucas' theorem (en.wikipedia.org/wiki/Lucas'_theorem). $\endgroup$ – Qiaochu Yuan May 20 '12 at 16:12
  • $\begingroup$ @QiaochuYuan Do you refer to the "main lemma" one usually uses in a proof of Lucas or to the whole factorisation? $\endgroup$ – Phira May 20 '12 at 16:16
  • $\begingroup$ Phira: Nice! Thanks. $\endgroup$ – 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.