8
$\begingroup$

Prove that if $p$ is an odd prime and $k$ is an integer satisfying $1\leq k \leq p-1$,then the binomial coefficient
$$\binom{p-1}{k} \equiv (-1)^k\pmod p$$

I have tried basic things like expanding the left hand side to $\frac{(p-1)(p-2).........(p-k)}{k!}$ but couldn't get far enough.

3 Answers 3

11

Hint: $(p-1)(p-2)\cdots(p-k)\equiv(-1)(-2)\cdots(-k)$ because $p\equiv 0$.

  • 0
    Got it .Thanks for the hint .2012-06-08
4

Hint: For the first few odd primes $p$, write down the $p$th row of Pascal's Triangle modulo $p$; you'll notice a pattern that should be straightforward to prove. Now use the relation $$\binom{p-1}{k-1}+\binom{p-1}{k}=\binom{p}{k}$$ and an induction argument.

  • 0
    I couldn't get the hint.I noticed $\binom{p}{k} \equiv 0 \pmod p$ but then I couldn't proceed.2012-06-08
  • 2
    We know that $\binom{p-1}{0}=1$, hence $\binom{p-1}{0}\equiv (-1)^0\bmod p$. If $\binom{p-1}{k}\equiv (-1)^k\bmod p$, then $$\binom{p-1}{k}+\binom{p-1}{k+1}=\binom{p}{k+1}$$ and therefore $$(-1)^k+\binom{p-1}{k+1}\equiv 0\bmod p$$ hence $\binom{p-1}{k+1}\equiv (-1)^{k+1}\bmod p$.2012-06-08
  • 0
    @SaurabhHota: It is complete.2012-06-08
3

Recall that we have $(x + 1)^p \equiv x^p + 1 \bmod p$. The ring $\mathbb{F}_p[x]$ is an integral domain, so we can divide and it follows that $$(x + 1)^{p-1} \equiv \frac{x^p + 1}{x + 1} \equiv x^{p-1} - x^{p-2} \pm ... - x + 1 \bmod p.$$