I was solving a few problem in number theory in the book "elementary number theory" by David M. Burton, and i come across this question and yet i do not see how to think about it at all
Prove that if $p$ is an odd prime and $k$ is an integer satisfying $1 \leq k \leq p-1$, then the binomial coefficient
${p-1}\choose{k}$ $\equiv (-1)^k$ mod $p$.
Best Answer
We can do it by induction. Note that $$\binom{p}{k} = \binom{p-1}{k} + \binom{p-1}{k-1}$$ is divisible by $p$. Therefore, $$\binom{p-1}{k} \equiv -\binom{p-1}{k-1} \mod p$$ so for induction step, assuming that $$\binom{p-1}{k-1} \equiv (-1)^{k-1} \mod p$$ you easily deduce $$\binom{p-1}{k} \equiv (-1)^{k} \mod p.$$ The base case is trivial to check.