Let p be a composite, and let us apply the simple rule stated by Lucas' theorem to check whether p is prime (that is, involving the p base representation). Now, assume that the result is positive; would that mean that indeed p divides $n \choose k$, or the result is random, since the hypothesis of p being a prime is violated?
On Lucas' Theorem over composite
1
$\begingroup$
combinatorics
primality-test
-
0@ArturoMagidin He seems to only refer to the special case of Lucas' Theorem where the binomial coefficient is zero, but I guess Qiaochu can help us here after claiming "I know what you mean". – 2012-06-09