\newcommand{\Z}{\mathbb{Z}} \begin{proof} Since $p$ is a prime, then $\Z/p\Z$ is a field, so $(\Z/p\Z)^\times$ is a multiplicative group of order $p-1$. Let $\overline{a} \in (\Z/p\Z)^\times$, where $a \in \Z$. By Lagrange's Theorem, the order of $\overline{a}$ divides $|(\Z/p\Z)^\times| = p-1$, therefore $\overline{a}^{p-1} = \overline{1}$. Multiplying by $\overline{a}$, we obtain $\overline{a}^p = \overline{a}$ for all $\overline{a} \in (\Z/p\Z)^\times$. Moreover $\overline{0}^p = \overline{0}$, so $$\forall \overline{a} \in \Z/p\Z, \ \overline{a}^p = \overline{a}.$$ Hence, if $p$ is a prime, $$\forall a \in \Z,\ a^p \equiv a \pmod p.$$ \end{proof}

Homepage › Solution manuals › David S. Dummit › Abstract Algebra › Exercise 3.2.16 (Fermat's Little Theorem)

Exercise 3.2.16 (Fermat's Little Theorem)

Proof. Since $p$ is a prime, then $ℤ ∕ 𝑝ℤ$ is a field, so ${(ℤ ∕ 𝑝ℤ)}^{\times}$ is a multiplicative group of order $p - 1$ . Let $\bar{a} \in {(ℤ ∕ 𝑝ℤ)}^{\times}$ , where $a \in ℤ$ . By Lagrange’s Theorem, the order of $\bar{a}$ divides $| {(ℤ ∕ 𝑝ℤ)}^{\times} | = p - 1$ , therefore ${\bar{a}}^{p - 1} = \bar{1}$ . Multiplying by $\bar{a}$ , we obtain ${\bar{a}}^{p} = \bar{a}$ for all $\bar{a} \in {(ℤ ∕ 𝑝ℤ)}^{\times}$ . Moreover ${\bar{0}}^{p} = \bar{0}$ , so

\forall \bar{a} \in ℤ ∕ 𝑝ℤ, {\bar{a}}^{p} = \bar{a} .

Hence, if $p$ is a prime,

\forall a \in ℤ, a^{p} \equiv a (𝑚𝑜𝑑 p) .

□

Exercise 3.2.16 (Fermat's Little Theorem)

Add answer