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$ – Steven Stadnicki Nov 28 '12 at 18:40
  • $\begingroup$ can you explain more? $\endgroup$ – World Nov 28 '12 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$ – Sebastien B Nov 28 '12 at 18:48
  • 1
    $\begingroup$ Also k < p for the same reason. $\endgroup$ – Gautam Shenoy Nov 28 '12 at 18:51
  • $\begingroup$ @GautamShenoy You are right, I had not seen that both the inequalities were large in the title. $\endgroup$ – Sebastien B Nov 28 '12 at 19:41

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$ – Sebastien B Nov 28 '12 at 18:55
  • 1
    $\begingroup$ @SebastienB I figured when one talks about divisibility problems, they talks about integers :P $\endgroup$ – Jean-Sébastien Nov 28 '12 at 18:57
  • $\begingroup$ Glad to be of use $\endgroup$ – Jean-Sébastien Nov 28 '12 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.