# If $p$ is a prime number greater than $2$ and $k$ is a natural number so that $k<p$, how can I prove that?

If $p$ is a prime number greater than 2 and $k\in \mathbb{N}$ so that $k < p$, how can I prove that $p\choose k$ is congruent to $0 \bmod p$?

-
Note natural means $k \geq 1.$ This has probably been asked several times before, it's a standard and useful fact. – Will Jagy Dec 5 '12 at 4:32

Hint: Do you know that ${p \choose k}=\frac {p!}{k!(p-k)!}?$

-
I do I'm having trouble with the congruency part of it, I haven't done congruences in a while and was shaky at best when I did do them. – Jack Forest Dec 5 '12 at 4:42
@JackForest: If $p$ is prime how can there be it a factor of the denominator? – Ross Millikan Dec 5 '12 at 4:43
There can not be a factor for the denominator since p is only divisible by 1 and itself. – Jack Forest Dec 5 '12 at 4:46
@JackForest: spot on. Do you think $0 \in \mathbb N$? Then you need one more piece. – Ross Millikan Dec 5 '12 at 4:50
0 is not ∈ N correct? – Jack Forest Dec 5 '12 at 4:52

So, you have: $$\frac{p!}{k!(p-k)!}$$ and you want to prove this is a multiple of $p$.

Hint: $n! = n(n-1)!$

-

For $\,1\leq k\leq p-1\,$:

$$\binom{p}{k}=\frac{p!}{k!(p-k)!}=\frac{(k+1)(k+2)\cdot\ldots\cdot (p-1)}{1\cdot 2\cdot\ldots\cdot (p-k)}\cdot\;p$$

Since the binomial coefficient is an integer and all the factors both in the numerator and in the denominator above are smaller than $\,p\,$, we're done

-