# Math Help - Binomial Coefficients

1. ## Binomial Coefficients

Show that if p is a prime and k is an integer such that $1 \leq k \leq p-1$, then p divides $\binom p k$

2. Originally Posted by EquinoX
Show that if p is a prime and k is an integer such that $1 \leq k \leq p-1$, then p divides $\binom p k$
Here's the basic idea. You can put this more exact language as you please.
$\binom p k = \frac{p!}{k!(p - k)!}$

Since p is prime, no number $n \leq k$ nor any number $n \leq p - k$ divides p. Thus no matter what cancellations we have in simplifying the factorials a p remains in the numerator. etc, etc.

-Dan

3. Okay I kind of get your idea here, because p here is prime in the numerator, but nothing in the denominator can divide p because p is a prime, therefore p still exists after the counting and because p still exists therefore it can be divided by p? right

4. Originally Posted by EquinoX
Okay I kind of get your idea here, because p here is prime in the numerator, but nothing in the denominator can divide p because p is a prime, therefore p still exists after the counting and because p still exists therefore it can be divided by p? right
That is correct.

-Dan

5. Originally Posted by EquinoX
Show that if p is a prime and k is an integer such that $1 \leq k \leq p-1$, then p divides $\binom p k$
When I was much younger I found a proof of Fermat's Little Theorem using the following observation:

"Every $n$-th number is divisible by $n$".

Now, ${p\choose k}=\frac{p(p-1)...(p-k+1)}{k!}$

We want to show that,
$\frac{p(p-1)...(p-k+1)}{pk!} = \frac{(p-1)...(p-k+1)}{k!}$
Is an integer.

Now $p$ is not a $2$-th number, nor a $3$-rd number , ... , nor a $k$-th number. Hence one of those numbers: $(p-1),...,(p-k+1)$ and one of those is a $k-1$-th thus,
$\frac{(p-1)(p-2)...(p-k+1)}{k!}$ is an integer.