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$?
If $p$ is a prime number greater than $2$ and $k$ is a natural number so that k, how can I prove that?
1
$\begingroup$
binomial-coefficients
modular-arithmetic
-
1Note natural means $k \geq 1.$ This has probably been asked several times before, it's a standard and useful fact. – 2012-12-05
3 Answers
2
Hint: Do you know that ${p \choose k}=\frac {p!}{k!(p-k)!}?$
-
0@JackForest: then both $k$ and $p-k$ are less than $p$ so there is a factor of $p$ in the numerator and not in the denominator. It is fun to look at Pascal's triangle mod $p$. – 2012-12-05
1
So, you have: $\frac{p!}{k!(p-k)!}$ and you want to prove this is a multiple of $p$.
Hint: $n! = n(n-1)!$
0
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