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.

Thanks in advance.

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

The last step follows from repeated application of this general fact about congruences:

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.)

  • $\begingroup$ but you probably need the elementary proof of the Fermat little theorem for proving that $(\mathbb{Z}_p,\times)$ is cyclic ? $\endgroup$ – reuns Apr 18 '16 at 12:02
  • $\begingroup$ @user1952009, I don't see how $U_p$ being cyclic enters here. $\endgroup$ – lhf Apr 18 '16 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.