# Prove that ${p-1}\choose{k}$ $\equiv (-1)^k$ mod $p$.

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$.

• As a side note, this is also true (but trivial) when $p=2.$ – Cameron Buie Nov 22 '19 at 12:55

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.

• in the third step i don't understand how you get this assumption – user146269 Nov 8 '15 at 0:38
• @user146269 This is proof by induction. To prove a property $P$ holds for all $k$, say $\binom{p-1}{k} \equiv (-1)^k \mod p$ for all $k$, you prove that it holds for $k = 0$ [base case] and then prove that if it holds for $k - 1$ then it holds for $k$ [induction]. – An Hoa Nov 8 '15 at 2:00

Note that $k!\equiv(-1)^k((p-1)(p-2)(\dots )(p-k)$ and then look at the factorial definition of the binomial coefficient.

• Thanks for the fix, had to look uo ellipses in latex. – bilaterus Nov 7 '15 at 23:23
• Where is Wilson's theorem used in this? – darij grinberg Nov 8 '15 at 0:13
• Oh, you're right that it isn't needed, since the $(p-1)!$ cancels from top and bottom. Thanks, I'll edit. – bilaterus Nov 8 '15 at 10:31

$$k!(p-1-k)!\equiv k\cdot (k-1)\cdots 1\cdot (p-1-k)!$$

$$\equiv (-1)^k(p-k)(p-(k-1))\cdots (p-1)\cdot (p-1-k)!$$

$$\equiv (-1)^k(p-1)!\pmod{p}$$

We have $\dbinom{p-1}{k+1}=\dfrac{p-k-1}{k+1}\dbinom{p-1}{k}$.

For example, $\dbinom{12}{4}=\dfrac94\dbinom{12}{3}$

We note that $(p-k-1)+(k+1)=p$.

Then $(-1)^k(p-k-1)\equiv (-1)^{k+1}(k+1)\mod p$,

or $(-1)^k\dfrac{p-k-1}{k+1}\equiv (-1)^{k+1}\mod p$.

Hint: $(-1)^k=\displaystyle{-1\choose k},~$ and $~p-1\equiv-1\bmod p.$