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$
$\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$– Steven StadnickiNov 28, 2012 at 18:40
-
$\begingroup$ can you explain more? $\endgroup$– WorldNov 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$– Sebastien BNov 28, 2012 at 18:48
-
1$\begingroup$ Also k < p for the same reason. $\endgroup$– Gautam ShenoyNov 28, 2012 at 18:51
-
$\begingroup$ @GautamShenoy You are right, I had not seen that both the inequalities were large in the title. $\endgroup$– Sebastien BNov 28, 2012 at 19:41
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Nov 28, 2012 at 18:44
-
$\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
-