Exercise 3.13

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}}

Use Ex. 3.12 to give another proof of Fermat's theorem, $a^{p-1} \equiv 1 \pmod p$ if $p$ does not divide $a$.

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}
If we make the induction hypothesis 
$${\cal P}(k) \iff \forall (a_1,a_2,\ldots,a_k) \in \Z^k,\  (a_1+a_2+\cdots+a_k)^p \equiv a_1^p+a_2^p+\cdots+a_k^p \pmod p$$
(which is true for $k=1,k=2$)
then, from induction hypothesis and the case $k=2$ already proved in Ex 3.12,
\begin{align*}
(a_1+a_2+\cdots+a_k+a_{k+1})^p &= ((a_1+a_2+\cdots+a_k) +a_{k+1})^p\
&\equiv (a_1+a_2+\cdots+a_k)^p + a_{k+1}^p \pmod p\
&\equiv a_1^p+a_2^p+\cdots+a_k^p+ a_{k+1}^p \pmod p\
\end{align*}
so ${\cal P}(k) \Rightarrow {\cal P}(k+1)$. We can conclude

$$\forall k \in \N^*, \forall (a_1,a_2,\ldots,a_k) \in \Z^k,\  (a_1+a_2+\cdots+a_k)^p \equiv a_1^p+a_2^p+\cdots+a_k^p \pmod p.$$
If we apply this result to the particular case $a_1=a_2=\cdots = a_k = 1$, we obtain
$$\forall k \in \N^*,\ k^p \equiv k \pmod p.$$
Moreover $(-k)^p \equiv - k^p \equiv -k \pmod p$ (even if $p=2$), and $0^p =0$, so
$$\forall k \in \Z,\ k^p \equiv k \pmod p.$$
If $p 
mid a, a \in \Z$, then $p\wedge a = 1$, and $p \mid a^p-a = a(a^{p-1} - 1)$, so $p \mid a^{p-1} - 1, a^{p-1} \equiv 1 \pmod p$ : this is another proof of Fermat's theorem.
\end{proof}

Exercise 3.13

Answers

Comments

Exercise 3.13

Answers

Comments

Add answer