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?
Conceptual proof that $p\choose k$ (1 < k < p) is divisible by $p$ when $p$ is prime? (I.e., no equations).
4
$\begingroup$
combinatorics
elementary-number-theory
prime-numbers
binomial-coefficients
divisibility
-
0KCd Ah nevermind - you're counting roots, I see. – 2012-05-20
2 Answers
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\}$.
-
0Phira: 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.