# Explanation to Fermat's little theorem proof

Fermat's little theorem $\forall a \in \mathbb{Z}$ and every prime p. Then, $a^{p}\equiv a\pmod p$

$a=pm+r$

$\forall 0 \leq r<p$

Proof for $r\not\equiv 0:$

Then, $\forall r \in \bar{U}\left ( p \right )$ and $\left | \bar{U}\left ( p \right ) \right |=p-1$

$r^{\left | \bar{U}\left ( p \right ) \right |}=e$ by a certain theorem in Cosets.

But this is really just $r^{p-1} \equiv 1\pmod p$

How does the last equivalence follows? My knowledge of number theory is almost non-existant. A verbose explanation would really help.

• hat is $\bar U(p)$? What is $e$? – Bernard Apr 18 '16 at 11:19

If $a \equiv a' \bmod m$ and $b \equiv b' \bmod m$, then $ab \equiv a'b' \bmod m$.
Indeed, $r^{p-1} \equiv 1\pmod p$ is the same as $[r^{p-1}] = [r]^{p-1} = [1]$ in $U(p)$.
(Here, $[r]$ means the class of $r \bmod p$.)
As you've noted, $[r]^{p-1} = [1]$ is a consequence of Lagrange's theorem for $U(p)$. (But it can be proved without using Lagrange's theorem since $U(p)$ is abelian.)
• but you probably need the elementary proof of the Fermat little theorem for proving that $(\mathbb{Z}_p,\times)$ is cyclic ? – reuns Apr 18 '16 at 12:02
• @user1952009, I don't see how $U_p$ being cyclic enters here. – lhf Apr 18 '16 at 12:31