Prove that: $$p \,\,\left|\, {p \choose k} \right., \quad 0< k \lt p$$ if $p$ is prime.

how to prove that with direct proof?

  • $\begingroup$ Hint: think of the explicit definition of $\displaystyle\binom{p}{k}$ as a fraction. How many times does $p$ divide the numerator? How many can it divide the denominator? $\endgroup$ Nov 28, 2012 at 18:40
  • $\begingroup$ can you explain more? $\endgroup$
    – World
    Nov 28, 2012 at 18:45
  • 1
    $\begingroup$ Be careful that $k>0$ since $\binom{p}{0}=1$ and then it is not true that $p|1$. $\endgroup$ Nov 28, 2012 at 18:48
  • 1
    $\begingroup$ Also k < p for the same reason. $\endgroup$ Nov 28, 2012 at 18:51
  • $\begingroup$ @GautamShenoy You are right, I had not seen that both the inequalities were large in the title. $\endgroup$ Nov 28, 2012 at 19:41

1 Answer 1


Write out what the binomial coefficient is: $$ {p\choose k}=\frac{p!}{k!(p-k)!}. $$ $p$ divides the numerator since it has a factor of $p$, but $p$ can't divide the denominator because it is the product of integers smaller than $p$ and $p$ is prime.

This means that $p$ does not appear in the prime factorisation of the denominator, thus you can't simplify the $p$ factor that is on the numerator.

  • $\begingroup$ To complete your argument you could say that $\binom{n}{k}$ is an integer : math.stackexchange.com/questions/11601/… $\endgroup$ Nov 28, 2012 at 18:55
  • 1
    $\begingroup$ @SebastienB I figured when one talks about divisibility problems, they talks about integers :P $\endgroup$ Nov 28, 2012 at 18:57
  • $\begingroup$ Glad to be of use $\endgroup$ Nov 28, 2012 at 19:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .