Let $p$ be a prime. Prove that $a^{p^{p-1}}\equiv a$ $(mod$ $p)$. My attempt:
From Fermat's Little Theorem, we have $a^{p}\equiv a$ $(mod$ $p)$, and by raising both sides to the power of $p-1$, we have $a^{p^{p-1}}\equiv a^{p-1}$ $(mod$ $p)$. But I don't see how $a^{p-1}\equiv a$ $(mod$ $p)$.
 A: You powered up wrong; $(a^b)^c\ne a^{b^c}$. Rather, note that
$$p^{p-1}\equiv1^{p-1}\equiv1\bmod p-1$$
and so by FLT
$$a^{p^{p-1}}\equiv a^1\equiv a\bmod p$$
A: As others have already indicated, you have made a mistake with the exponentiation. The phenomenon of interest here is described by the following:

Proposition. Let $p$ be a prime number and $m \in \mathbb{Z}$ an arbitrary integer. Then for any $n \in \mathbb{N}$ the congruence $m^{p^n} \equiv m\ (\mathrm{mod}\ p)$ holds.

Proof. The natural way to prove this universal statement concerning natural numbers is by induction. In the base case $n=0$ we trivially have $m^{p^0}=m^1=m$, so the congruence modulo $p$ trivially holds. Considering an arbitrary $n \in \mathbb{N}$ and assuming the claim to be valid for $n$, we raise the congruence $m^{p^n} \equiv m\ (\mathrm{mod}\ p)$ to the $p$-th in order to obtain:
$$m^{p^{n+1}}=\left(m^{p^n}\right)^p \equiv m^p \equiv m\ (\mathrm{mod}\ p),$$
where the latter congruence is justified by Fermat's little theorem. $\Box$

At this stage you might not be entirely familiar with the concepts I am about to mention, but in a more brief presentation what happens here is that the Frobenius automorphism of the residue field $\mathbb{Z}_p\colon=\mathbb{Z}/p\mathbb{Z}$ -- given by elevating to the $p$-th -- is the identity automorphism, and therefore any of its powers of generic exponent $n \in \mathbb{N}$ in the group of automorphisms are alse equal to the identity. These powers are however in general given by raising to the $p^n$-th, and this is precisely the content of the above proposition, in veiled form.
