7
$\begingroup$

I have this problem assigned for homework:

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

I've come up with a proof but I'm not sure if it's correct since I never end up using the fact that $p$ is an odd prime... Here it is:

Proof

Note that

$$\binom{p-1}{k}k!=\frac{(p-1)!}{(p-1-k)!k!}\cdot k!=\frac{(p-1)!}{(p-k-1)!}.$$

Since $1<k<p-1$, we have

\begin{align*} (p-1)! &=(p-1)(p-2)\cdots (p-k)(p-k-1)(p-k-2)\cdots 2\cdot 1\\ &=(p-1)(p-2)\cdots (p-k)(p-k-1)! \end{align*}

So,

\begin{align*} \binom{p-1}{k}k!&=\frac{(p-1)!}{(p-1-k)!}\\ &=\frac{(p-1)(p-2)\cdots (p-k)(p-k-1)!}{(p-k-1)!}\\ &=(p-1)(p-2)\cdots (p-k). \end{align*}

Note that,

\begin{align*} p-1&\equiv -1\pmod{p}\\ p-2&\equiv -2\pmod{p}\\ &\vdots\\ p-k&\equiv -k\pmod{p}. \end{align*} So, we have

\begin{align*} \binom{p-1}{k}k!&=(p-1)(p-2)\cdots (p-k)\\ &\equiv (-1)(-2)\cdots (-k)\\ &\equiv (-1)^k(1\cdot 2\cdots k)\\ &\equiv (-1)^k k!\pmod{p}. \end{align*}

So $\binom{p-1}{k}k!\equiv (-1)^k k!\pmod{p}\implies \binom{p-1}{k}\equiv (-1)^k \pmod{p}$. $\blacksquare$

$\endgroup$
2
  • 5
    $\begingroup$ The proof looks correct. You are using the fact that $p$ is prime in the last step. In general, $ab\equiv ac\mod n\Rightarrow b\equiv c\mod n$ is only true if $a$ is coprime to $n$, so you need $k!$ to be coprime to $p$. $\endgroup$ Oct 20 '15 at 1:00
  • $\begingroup$ Thank you very much! Just fixed it. $\endgroup$ Oct 20 '15 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.