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 $p$ is a prime number greater than 2 and $k\in \mathbb{N}$ so that $k < p$, how can I prove that $p\choose k$ is congruent to $0 \bmod p$?

share|cite|improve this question
Note natural means $k \geq 1.$ This has probably been asked several times before, it's a standard and useful fact. – Will Jagy Dec 5 '12 at 4:32

Hint: Do you know that ${p \choose k}=\frac {p!}{k!(p-k)!}?$

share|cite|improve this answer
I do I'm having trouble with the congruency part of it, I haven't done congruences in a while and was shaky at best when I did do them. – Jack Forest Dec 5 '12 at 4:42
@JackForest: If $p$ is prime how can there be it a factor of the denominator? – Ross Millikan Dec 5 '12 at 4:43
There can not be a factor for the denominator since p is only divisible by 1 and itself. – Jack Forest Dec 5 '12 at 4:46
@JackForest: spot on. Do you think $0 \in \mathbb N$? Then you need one more piece. – Ross Millikan Dec 5 '12 at 4:50
0 is not ∈ N correct? – Jack Forest Dec 5 '12 at 4:52

So, you have: $$\frac{p!}{k!(p-k)!}$$ and you want to prove this is a multiple of $p$.

Hint: $n! = n(n-1)!$

share|cite|improve this answer

For $\,1\leq k\leq p-1\,$:

$$\binom{p}{k}=\frac{p!}{k!(p-k)!}=\frac{(k+1)(k+2)\cdot\ldots\cdot (p-1)}{1\cdot 2\cdot\ldots\cdot (p-k)}\cdot\;p$$

Since the binomial coefficient is an integer and all the factors both in the numerator and in the denominator above are smaller than $\,p\,$, we're done

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.