2
$\begingroup$

I was solving a few problem in number theory in the book "elementary number theory" by David M. Burton, and i come across this question and yet i do not see how to think about it at all

Prove that if $p$ is an odd prime and $k$ is an integer satisfying $1 \leq k \leq p-1$, then the binomial coefficient

${p-1}\choose{k}$ $\equiv (-1)^k$ mod $p$.

$\endgroup$
  • $\begingroup$ As a side note, this is also true (but trivial) when $p=2.$ $\endgroup$ – Cameron Buie Nov 22 '19 at 12:55
4
$\begingroup$

We can do it by induction. Note that $$\binom{p}{k} = \binom{p-1}{k} + \binom{p-1}{k-1}$$ is divisible by $p$. Therefore, $$\binom{p-1}{k} \equiv -\binom{p-1}{k-1} \mod p$$ so for induction step, assuming that $$\binom{p-1}{k-1} \equiv (-1)^{k-1} \mod p$$ you easily deduce $$\binom{p-1}{k} \equiv (-1)^{k} \mod p.$$ The base case is trivial to check.

$\endgroup$
  • $\begingroup$ in the third step i don't understand how you get this assumption $\endgroup$ – user146269 Nov 8 '15 at 0:38
  • $\begingroup$ @user146269 This is proof by induction. To prove a property $P$ holds for all $k$, say $\binom{p-1}{k} \equiv (-1)^k \mod p$ for all $k$, you prove that it holds for $k = 0$ [base case] and then prove that if it holds for $k - 1$ then it holds for $k$ [induction]. $\endgroup$ – An Hoa Nov 8 '15 at 2:00
1
$\begingroup$

Note that $k!\equiv(-1)^k((p-1)(p-2)(\dots )(p-k)$ and then look at the factorial definition of the binomial coefficient.

$\endgroup$
  • $\begingroup$ Thanks for the fix, had to look uo ellipses in latex. $\endgroup$ – bilaterus Nov 7 '15 at 23:23
  • 1
    $\begingroup$ Where is Wilson's theorem used in this? $\endgroup$ – darij grinberg Nov 8 '15 at 0:13
  • $\begingroup$ Oh, you're right that it isn't needed, since the $(p-1)! $ cancels from top and bottom. Thanks, I'll edit. $\endgroup$ – bilaterus Nov 8 '15 at 10:31
0
$\begingroup$

$$k!(p-1-k)!\equiv k\cdot (k-1)\cdots 1\cdot (p-1-k)!$$

$$\equiv (-1)^k(p-k)(p-(k-1))\cdots (p-1)\cdot (p-1-k)!$$

$$\equiv (-1)^k(p-1)!\pmod{p}$$

$\endgroup$
0
$\begingroup$

We have $\dbinom{p-1}{k+1}=\dfrac{p-k-1}{k+1}\dbinom{p-1}{k}$.

For example, $\dbinom{12}{4}=\dfrac94\dbinom{12}{3}$

We note that $(p-k-1)+(k+1)=p$.

Then $(-1)^k(p-k-1)\equiv (-1)^{k+1}(k+1)\mod p$,

or $(-1)^k\dfrac{p-k-1}{k+1}\equiv (-1)^{k+1}\mod p$.

$\endgroup$
0
$\begingroup$

Hint: $(-1)^k=\displaystyle{-1\choose k},~$ and $~p-1\equiv-1\bmod p.$

$\endgroup$

Your Answer

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

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