1
$\begingroup$

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

how to prove that with direct proof?

$\endgroup$
6
  • $\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

13
$\begingroup$

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.

$\endgroup$
3
  • $\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

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.