Number theory - prime numbers

Question

Prove that If $p$ is prime s.t. $0 \lt n \le p$ , then $p \vert \binom{p}{n}$ I know that if $p \vert q$, then $q = kp$, for some integer number $k$ . But I don’t know how to prove that $p$ divided like above

Answer 1

By Lucas's Theorem (which you can easily reprove for $k=p$),

$$\binom{n}{p}\equiv\binom{\lfloor{n/p}\rfloor}{1}\binom{n\pmod p}{0}\pmod{p}\equiv \lfloor n/p\rfloor \pmod{p}.$$

It follows that $p|\binom{n}{p}$ iff $p|\lfloor n/p\rfloor$. Otherwise it's not true.

Answer 2

Let $s_p(n)$ be the sum of digits of $n$ when written in base $p$, $k = v_p(n)$ be the highest integer such that $p^k|n$, we can find $v_p\left(\binom{n}{p}\right)$ from this identity: $$v_p\left(\binom{n}{p}\right)=s_p(n-p) + s_p(p) - s_p(n) = s_p(n-p) + 1 - s_p(n)$$ So if you have special properties of $n,p$ then you can even compute $v_p\left(\binom{n}{p}\right)$. As you can see, we cannot always choose $n$ such that $s_p(n-p)+1>s_p(n)$. If the second digit from right to left in base $p$ representation is non-zero, then $s_p(n-p) = s_p(n)-1$, thus we have to choose $n$ such that $[n/p]\equiv 0 (mod p)$

Answer 3

${n \choose p} = \frac {n!}{(n-p)!p!} = \frac {\prod\limits_{j= n- p + 1}^n j}{p!}$ is an integer.

The numerator is a product of $n- p + 1, n-p+2,...... , n$ which are $p$ terms. So exactly on of the terms is divisible by $p$ and the rest are not. Assume the term that is divisible by $p$ is $M$. Likewise the denominator is a product of $1,2,3,....,p$ terms only only of which one term, $p$, is divisible by $p$.

So ${n \choose p} = \frac {\prod\limits_{j= n- p + 1}^n j}{p!}= \frac {(\prod\limits_{j = n - p +1; j \ne M}^n j) \times M}{(p-1)!\times p} = \frac {\prod\limits_{j = n - p +1; j \ne M}^n j }{(p-1)!}\times \frac M p$.

Now none of the $n-p+1, n-p+2,.....,M-1, M+1, ....n$ are divisible by $p$ so $p$ does not divide $\frac {\prod\limits_{j = n - p +1; j \ne M}^n j }{(p-1)!}$[1].

So $p|{n \choose p}$ if and only if $p|\frac Mp$. Which can only happen if $p^2|M$.

So this statement is true if $n-p+1, .... ,n$ will contain a multiple of $p^2$ but will not be true of it does not.

So for example $13| {174 \choose 13}$ because $13^2|169$. But $13 \not \mid {187 \choose 13}$ because $13^2\not \mid 182$.

.....

[1] Note, that $p$ is prime is a necessary requirement. If $p$ were noot prime then some of those terms could be divisible by factors of $p$ and thus $p$ could divide the product. But as $p$ is prime that is not possible.