0
$\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?

  • 0
    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?2012-11-28
  • 0
    can you explain more?2012-11-28
  • 1
    Be careful that $k>0$ since $\binom{p}{0}=1$ and then it is not true that $p|1$.2012-11-28
  • 1
    Also k < p for the same reason.2012-11-28
  • 0
    @GautamShenoy You are right, I had not seen that both the inequalities were large in the title.2012-11-28
  • 0
    Combinatorially, the set ${X\choose k}$ of $k$-subsets of an $n$-element set $X$ ($1) can be partitioned into $n$ disjoint equal-sized cells. The cells are $\Gamma_x=\left\{V:x\in V\in{X\choose k}\right\}$ for $x\in X$, which we may intuitively expect to be a partition by considering symmetry.2012-11-28

1 Answers 1

12

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.

  • 0
    To complete your argument you could say that $\binom{n}{k}$ is an integer : http://math.stackexchange.com/questions/11601/proof-that-a-combination-is-an-integer2012-11-28
  • 1
    @SebastienB I figured when one talks about divisibility problems, they talks about integers :P2012-11-28
  • 0
    Glad to be of use2012-11-28