Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question

marked as duplicate by anon, Shaktal, Austin Mohr, t.b., Zev Chonoles Jun 12 '12 at 5:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Same as this… –  Saurabh Jun 11 '12 at 19:16
@SaurabhHota Ahh, sorry, I didn't see that when I looked. Thanks. Anyone can feel free to close this question now. –  Shaktal Jun 11 '12 at 19:17

2 Answers 2

up vote 3 down vote accepted

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)=(1-k)(2-k)\cdot ...\cdot (-1)\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 $$

share|cite|improve this answer
Thanks for the prompt answer! –  Shaktal Jun 11 '12 at 19:26

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.

share|cite|improve this answer
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<i<p$ 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. –  mathse Mar 23 '14 at 21:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.