Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 10 down vote accepted

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

share|cite|improve this answer
A slightly more general version of this argument can be used to prove Lucas' theorem ('_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.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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