Exercise 3.12

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

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

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

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

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

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

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Let ${p \choose k} = \frac{p!}{k!(p-k)!}$ be a binomial coefficient, and suppose that $p$ is prime. If $1 \leq k \leq p-1$, show that $p$ divides ${p \choose k}$. Deduce $(a+b)^p \equiv a^p + b^p \pmod p$.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

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

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

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

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

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

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof}
$p \mid p! = k!(p-k)! {p \choose k}$.

If $1\leq k \leq p-1$, then  each $i$ such that $1\leq i \leq k$ satisfies $1\leq i < p$, so $i\wedge p=1$. Thus $ \left(\prod_{i=1}^k i ight) \wedge p = 1$, that is $k!\wedge p = 1$. Similarly, $p-k<p$, so $\left( \prod_{i=1}^{p-k} i ight)\wedge p = 1, (p-k)!\wedge p = 1$. Thus $p \wedge k!(p-k)! = 1$, and $p \mid p! = k!(p-k)! {p \choose k}$, so $p \mid {p \choose k}$.

Finally, from binomial formula
\begin{align*}
(a+b)^p &= a^p + \sum_{k=1}^{p-1} {p \choose k} a^k b^{n-k} + b^p\
&\equiv a^p + b^p \pmod p
\end{align*}
\end{proof}

Exercise 3.12

Answers

Comments

Exercise 3.12

Answers

Comments

Add answer