# Prove that if $p$ is a prime number then $\binom{p-1}{k}\equiv (-1)^k\pmod{p}$

Prove that if $p$ is a prime number then $\binom{p-1}{k}\equiv (-1)^k\pmod{p}$. What can be said about $\binom{p+1}{k} \pmod{p}$?

I thought about expanding $\dbinom{p-1}{k} = \dfrac{(p-1)!}{k!(p-1-k)!}$, but I don't see how that helps. Is there an easier way?

• Hint: $1+x^p=(1+x)^p=(1+x)^{p-1}(1+x) \pmod p$. Then proceed inductively. – lulu Jun 19 '16 at 18:44
• You're on the right track, just do some cancellation on $(p-1)!/(p-1-k)!$ and then compare the numerator and denominator. – Erick Wong Jun 19 '16 at 18:44
• How about induction on $k$? – Harald Hanche-Olsen Jun 19 '16 at 18:44
• Hint: Wilson's Theorem. Also, $p-j\equiv -j\pmod{p}$. – Batominovski Jun 19 '16 at 18:45
• @Batominovski What about the second expression? – user19405892 Jun 19 '16 at 18:48

If $k=0$ then it is trivially true. Otherwise:

$$\frac{(p-1)!}{k!(p-1-k)!}\equiv\frac{(p-1)\ldots(p-k)}{k!}\equiv\frac{(-1)\ldots(-k)}{1\ldots k}\equiv (-1)^k \frac{k!}{k!}\equiv(-1)^k,$$

with the appearance of divisions making sense because $\mathbb{Z}_p$ is a field.

• You don't need to make a separate case for $k=0$ since $0! = 1$. – user19405892 Jun 19 '16 at 18:59
• @user19405892 Yes, but I felt that the formula $(p-1)\ldots (p-k)$ for $k=0$, although understanable by convention as $1$, would need some (this) explanation, which I thought messier than just discarding the $k=0$ case. – Jose Brox Jun 19 '16 at 22:41

It is easy to show that $$\binom{p}{k}\equiv 0\pmod{p}$$ unless $k\in\{0,p\}$: in such cases $\binom{p}{k}=1$. Now just exploit the fact that: $$\binom{p}{k}=\binom{p-1}{k-1}+\binom{p-1}{k}$$ through induction. With the same approach we have $$\binom{p+1}{k}\equiv 0\pmod{p}$$ unless $k\in\{0,1,p,p+1\}$: in such cases $\binom{p+1}{k}\equiv 1\!\pmod{p}$.

• What about the second expression? – user19405892 Jun 19 '16 at 18:52
• @user19405892: it is well-known and easy to prove. – Jack D'Aurizio Jun 19 '16 at 18:53
• I am talking about in my question. – user19405892 Jun 19 '16 at 18:53
• @user19405892: The $(p+1)$-th row of the Pascal triangle $\!\!\pmod{p}$ is $1\; 1\; 0\; \ldots 0\; 1\; 1$ by the same argument. – Jack D'Aurizio Jun 19 '16 at 18:55
• So it's not $(-1)^k$ or something similar? It is the Legendre symbol? – user19405892 Jun 19 '16 at 18:56