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

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?

share|cite|improve this question
What do you mean by "the simple rule stated by Lucas' theorem"? (I know what you mean, but others might not.) – Qiaochu Yuan Jun 6 '12 at 21:29
"Let $p$ be composite" --- words I thought I'd never see. – Gerry Myerson Jun 6 '12 at 22:50
You are asking whether the congruence stated in Lucas's Theorem holds if and only if the modulus is prime, that is, whether Lucas's Theorem can be used as a primality test, the way Wilson's Theorem can? – Arturo Magidin Jun 7 '12 at 2:21
@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". – Phira Jun 9 '12 at 11:28

Your Answer


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

Browse other questions tagged or ask your own question.