Use Lagrange’s Theorem to Prove Fermat’s Little Theorem

Problem 219

Use Lagrange’s Theorem in the multiplicative group $(\Zmod{p})^{\times}$ to prove Fermat’s Little Theorem: if $p$ is a prime number then $a^p \equiv a \pmod p$ for all $a \in \Z$.

Contents

Before the proof, let us recall Lagrange’s Theorem.

Lagrange’s Theorem

If $G$ is a finite group and $H$ is a subgroup of $G$, then the order $|H|$ of $H$ divides the order $|G|$ of $G$.

Proof.

If $a=0$, then we clearly have $a^p \equiv a \pmod p$.
So we assume that $a\neq 0$.
Then $\bar{a}=a+p\Z \in (\Zmod{p})^{\times}$.

Let $H$ be a subgroup of $(\Zmod{p})^{\times}$ generated by $\bar{a}$.
Then the order of the subgroup $H$ is the order of the element $\bar{a}$.

By Lagrange’s Theorem, the order $|H|$ divides the order of the group $(\Zmod{p})^{\times}$, which is $p-1$.
So we write $p-1=|H|m$ for some $m \in \Z$.

Therefore, we have
\begin{align*}
\bar{a}^{p-1}=\bar{a}^{|H|m}=\bar1^m=\bar1.
\end{align*}
(Note that this is a computation in $(\Zmod{p})^{\times}$.)

This implies that we have
$a^{p-1}\equiv 1 \pmod p.$ Multiplying by $a$, we obtain
$a^{p}\equiv a\pmod p,$ and hence Fermat’s Little Theorem is proved.

Let $G$ be a group. Suppose that the order of nonidentity element of $G$ is $2$. Then show that $G$...