Exercise 2.1.44* (Binomial congruences 1)

Question

Show that if $p$ is prime then $\binom{p-1}{k} \equiv (-1)^k \pmod p$ for $0\leq k \leq p-1$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

\begin{proof}

{\bf First proof.} We use the result of Exercise 45:
$$\binom{p}{k} \equiv 0 \pmod p	ext{ for }1\leq k \leq p-1.$$
(I promise not to use the result of exercise 44 to prove exercise 45!)

By Pascal's formula, for all $k \in [\![0,p-2]\!]$,
$$\binom{p-1}{k} + \binom{p-1}{k+1} = \binom{p}{k+1} \equiv 0 \pmod p,$$
so
$$ \binom{p-1}{k+1} \equiv - \binom{p-1}{k}\pmod p,\qquad k = 0,1,2,\ldots, p-2.$$
Since $\binom{p-1}{0} = 1$, this gives by induction
$$ \binom{p-1}{k} \equiv (-1)^k,\qquad k = 0,1,2,\ldots,p-1.
$$

\bigskip
{\bf Second proof.}
The result of exercise 45 gives the equality in $\F_p[X]$, where $\F_p$ is the field with $p$ elements, and $X$ a variable (indeterminate),
$$(X+1)^p = X^p + 1.$$
Therefore
$$(X+1)^{p-1} = \frac{X^p+1}{X+1} = \sum_{k=0}^{p-1} (-1)^k X^k$$
is true if $p$ is an odd prime, and remains true if $p = 2$: in $\F_2$, the equality  $-1 = 1$ implies 
$$X+1= \frac{X^2-1}{X-1}  = \sum_{k=0}^{2-1} X^k =\sum_{k=0}^{p-1} (-1)^k X^k.$$

By the binomial formula,
$$\sum_{k=0}^{p-1} \binom{p-1}{k} X^k = \sum_{k=0}^{p-1} (-1)^k X^k.$$
This gives the equality in $\F_p$
$$\left[\binom{p-1}{k} ight]_p=\left [(-1)^kight]_p,$$
thus
$$\binom{p-1}{k} \equiv (-1)^k \pmod p.$$

\bigskip
{\bf Third proof.} (without Exercise 45.)
By Wilson's theorem,
\begin{align}
(p-1-k)! k ! \binom{p-1}{k} = (p-1)! \equiv -1 \pmod p.
\end{align}
We prove by induction the proposition
$$\mathscr{P}(k) \iff (p-1-k)! k ! \equiv (-1)^{k+1} \pmod p.$$

$\bullet$ For $k = 0$, $(p-1-k)! k ! = (p-1)! \equiv -1$ by Wilson' s theorem, thus $\mathscr{P}(0)$ is true.

$\bullet$ Assume $\mathscr{P}(k)$ for some $k$ such that $0 \leq k <p-1$. Then
\begin{align*}
(p-k-2)! (k+1)! (p-k -1) &\equiv (p-k-1)! k! (k+1)\pmod p,\
\end{align*}
therefore
$$ - (p-k-2)! (k+1)! (k+1) \equiv  (p-k-1)! k! (k+1) \pmod p.$$
Since $1 \leq k +1 < p$, $k\wedge p = 1$, so $k$ is invertible modulo $p$. Using the induction hypothesis,
\begin{align*} 
(p-k-2)! (k+1)! &\equiv  -(p-k-1)! k! \pmod p\
&\equiv  (-1)^{k+1} \pmod p.
\end{align*}

This shows $\mathscr{P}(k+1)$, and the induction is done.

$\bullet$ So, for all $k$ such that $0 \leq k \leq p-1$,
$$ (p-1-k)! k ! \equiv (-1)^{k+1} \pmod p.$$

Then (1) gives 
$$\binom{p-1}{k} \equiv (-1)^k \pmod p.$$
\end{proof}

Exercise 2.1.44* (Binomial congruences 1)

Answers

Comments

Exercise 2.1.44* (Binomial congruences 1)

Answers

Comments

Add answer