I was working with congruence classes and encountered Fermat's little theorem:
$$a^{p } \equiv a \mod p$$
But I noticed that a$^{p^{k}} \equiv a \mod p$.
I used induction on $k$ but I'm still not convinced. Can anyone give an intuitive way to see why this is?
Best Answer
If $a$ is divisible by $p$, it is obvious.
If not, Fermat's Little Theorem is equivalent to $a^{p-1}\equiv 1\bmod p$.
Raising both sides to any power shows that $a^x\equiv 1\bmod p$ for any $x$ a multiple of $p-1$.
$p^k-1$ is a multiple of $p-1$: $(p-1)(p^{k-1}+p^{k-2}+\ldots+1)$.