4
$\begingroup$

Prove that if $p$ is a prime number then $\binom{p-1}{k}\equiv (-1)^k\pmod{p}$. What can be said about $\binom{p+1}{k} \pmod{p}$?

I thought about expanding $\dbinom{p-1}{k} = \dfrac{(p-1)!}{k!(p-1-k)!}$, but I don't see how that helps. Is there an easier way?

$\endgroup$
  • 1
    $\begingroup$ Hint: $1+x^p=(1+x)^p=(1+x)^{p-1}(1+x) \pmod p$. Then proceed inductively. $\endgroup$ – lulu Jun 19 '16 at 18:44
  • $\begingroup$ You're on the right track, just do some cancellation on $(p-1)!/(p-1-k)!$ and then compare the numerator and denominator. $\endgroup$ – Erick Wong Jun 19 '16 at 18:44
  • $\begingroup$ How about induction on $k$? $\endgroup$ – Harald Hanche-Olsen Jun 19 '16 at 18:44
  • 1
    $\begingroup$ Hint: Wilson's Theorem. Also, $p-j\equiv -j\pmod{p}$. $\endgroup$ – Batominovski Jun 19 '16 at 18:45
  • $\begingroup$ @Batominovski What about the second expression? $\endgroup$ – user19405892 Jun 19 '16 at 18:48
6
$\begingroup$

If $k=0$ then it is trivially true. Otherwise:

$$\frac{(p-1)!}{k!(p-1-k)!}\equiv\frac{(p-1)\ldots(p-k)}{k!}\equiv\frac{(-1)\ldots(-k)}{1\ldots k}\equiv (-1)^k \frac{k!}{k!}\equiv(-1)^k,$$

with the appearance of divisions making sense because $\mathbb{Z}_p$ is a field.

$\endgroup$
  • 1
    $\begingroup$ You don't need to make a separate case for $k=0$ since $0! = 1$. $\endgroup$ – user19405892 Jun 19 '16 at 18:59
  • $\begingroup$ @user19405892 Yes, but I felt that the formula $(p-1)\ldots (p-k)$ for $k=0$, although understanable by convention as $1$, would need some (this) explanation, which I thought messier than just discarding the $k=0$ case. $\endgroup$ – Jose Brox Jun 19 '16 at 22:41
4
$\begingroup$

It is easy to show that $$\binom{p}{k}\equiv 0\pmod{p} $$ unless $k\in\{0,p\}$: in such cases $\binom{p}{k}=1$. Now just exploit the fact that: $$ \binom{p}{k}=\binom{p-1}{k-1}+\binom{p-1}{k} $$ through induction. With the same approach we have $$ \binom{p+1}{k}\equiv 0\pmod{p} $$ unless $k\in\{0,1,p,p+1\}$: in such cases $\binom{p+1}{k}\equiv 1\!\pmod{p}$.

$\endgroup$
  • $\begingroup$ What about the second expression? $\endgroup$ – user19405892 Jun 19 '16 at 18:52
  • $\begingroup$ @user19405892: it is well-known and easy to prove. $\endgroup$ – Jack D'Aurizio Jun 19 '16 at 18:53
  • $\begingroup$ I am talking about in my question. $\endgroup$ – user19405892 Jun 19 '16 at 18:53
  • $\begingroup$ @user19405892: The $(p+1)$-th row of the Pascal triangle $\!\!\pmod{p}$ is $1\; 1\; 0\; \ldots 0\; 1\; 1$ by the same argument. $\endgroup$ – Jack D'Aurizio Jun 19 '16 at 18:55
  • $\begingroup$ So it's not $(-1)^k$ or something similar? It is the Legendre symbol? $\endgroup$ – user19405892 Jun 19 '16 at 18:56

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.