1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ hat is $\bar U(p)$? What is $e$? $\endgroup$ Commented Apr 18, 2016 at 11:19

1 Answer 1

Reset to default
1
$\begingroup$

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

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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.