4
$\begingroup$

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.

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?

  • 0
    KCd Ah nevermind - you're counting roots, I see.2012-05-20

2 Answers 2

12

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

  • 0
    Phira: Nice! Thanks.2012-05-20
-2
    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.