Exercise 9.1.9

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

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{\U}{\mathbb{U}}

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

ewcommand{\im}{\,\mathrm{Im}\,}

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

ewcommand{\Gal}{\mathrm{Gal}}

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

In proving Fermat's Little Theorem $a^p\equiv a \pmod p$, recall from the proof of Lemma 9.1.2 that we first proved $a^{p-1} \equiv 1 \pmod p$ when $a$ is relatively prime to $p$. For general $n>1$, Euler showed that $a^{\phi(n)} \equiv 1 \pmod n$ when $a$ is relatively prime to $n$. Prove this. What basic fact from group theory do you use?

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

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{\U}{\mathbb{U}}

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

ewcommand{\im}{\,\mathrm{Im}\,}

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

ewcommand{\Gal}{\mathrm{Gal}}

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

\begin{proof}
If $a \wedge n = 1$, $[a] \in (\Z/n\Z)^*$.
By Lagrange Theorem, the order of $[a]$ divides the order of the group $(\Z/n\Z)^*$, therefore the order of $a$ divides $ \phi(n) = \vert (\Z/n\Z)^* \vert$, and so $[a]^{\phi(n)} = [1]$.

$$a \wedge n = 1 \Rightarrow a^{\phi(n)} \equiv 1 \ \pmod n.$$
\end{proof}

Exercise 9.1.9

Answers

Comments

Exercise 9.1.9

Answers

Comments

Add answer