5
$\begingroup$

Possible Duplicate:
Prove $\binom{p-1}{k} \equiv (-1)^k\pmod p$

The question is as follows:

Let $p$ be prime. Show that ${p \choose k}\bmod{p}=0$, for $0 \lt k \lt p,\space k\in\mathbb{N}$. What does this imply about the binomial co-efficients ${p-1 \choose k}$?

By the definition of binomial coefficients:

${p \choose k}=\frac{p!}{k!(p-k)!}$

Now if $0 \lt k \lt p$, then we have $p\mid{p\choose k}$, therefore ${p \choose k}\equiv0\pmod{p}, \space 0 \lt k \lt p. \space \blacksquare$

Note that we can write: ${p \choose k}={p-1 \choose k}+{p-1 \choose k-1}$, and therefore:

${p-1 \choose k}={p \choose k}-{p-1 \choose k-1}=\frac{p!}{k!(p-k)!}-\frac{(p-1)!}{(k-1)!(p-k)!}=\frac{(p-1)!}{(k-1)!(p-k)!}\left(\frac{p}{k}-1\right)$

However, I am unsure how to proceed with this question, the book I am working from states that:

${p-1 \choose k}\equiv(-1)^{k}\pmod{p}, \space 0 \le k \lt p$

But I am unsure how the authors have derived this congruence, so I'd appreciate any hints.

Thanks in advance.

  • 0
    @SaurabhHota Ahh, sorry, I didn't see that when I looked. Thanks. Anyone can feel free to close this question now.2012-06-11

2 Answers 2

4

Remember Wilson's Theorem for a prime $\,p\,$: $(p-1)!=-1\pmod p$and from what you already proved we get $\binom {p-1}{k}=\binom{p}{k}-\binom{p-1}{k-1}=\binom{p-1}{k-1}\pmod p$Now just observe $\frac{(p-1)!}{(p-k)!}=(p-k+1)(p-k+2)\cdot ...\cdot (p-1)\equiv(1-k)(2-k)\cdot ...\cdot (-1)(\text{mod } p)\Longrightarrow$$\Longrightarrow\binom{p-1}{k-1}=\frac{(1-k)(2-k)\cdot ...\cdot (-1)}{1\cdot 2\cdot ...\cdot (k-1)}=(-1)^k\pmod p $

  • 0
    Thanks for the prompt answer!2012-06-11
4

It turns out that we do not even need Wilson's Theorem. Note the identity $\binom{p-1}{k+1}(k+1)=\binom{p-1}{k}(p-k-1).$ This is easily obtained from the fact that $\binom{n}{m}=\frac{n!}{m!(n-m)!}$. Now note that $p-k-1\equiv -(k+1)\pmod p$. Thus $\binom{p-1}{k+1}(k+1)\equiv -\binom{p-1}{k}(k+1)\pmod p.$ If $0\le k \lt p-1$, then $k+1$ is not divisible by $p$, so we can cancel and obtain $\binom{p-1}{k+1}\equiv -\binom{p-1}{k}\pmod p.\tag{$1$}$ Thus $\binom{p-1}{k}$ changes sign modulo $p$ every time that we increment $k$. But $\binom{p-1}{0}=1$, and the result follows.

  • 0
    This is quite an old question, but I like your answer - but there is even a simpler one. Obviously, $p$ divides $\binom{p}{i}$ whenever 0 and for $i=0,p$, we have $\binom{p}{i}=1$. Now, the congruence in question for row $p-1$ follows from the fact that $\binom{p}{i}=\binom{p-1}{i}+\binom{p-1}{i-1}$, i.e. for $i=1$: $x+1=\binom{p-1}{i}+\binom{p-1}{i-1}=\binom{p}{i}\equiv 0\pmod{p}$, whence $x\equiv -1\pmod{p}$, etc.2014-03-23