1. ## Binomial Coefficients

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

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

Since p is prime, no number $\displaystyle n \leq k$ nor any number $\displaystyle 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 $\displaystyle 1 \leq k \leq p-1$, then p divides $\displaystyle \binom p k$
When I was much younger I found a proof of Fermat's Little Theorem using the following observation:

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

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

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

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