[Math] Fermat’s Little Theorem: exponents powers of p

congruenceselementary-number-theorymodular arithmetic

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

Related Question