Fermat's Little Theorem: exponents powers of p

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?

-
Well, exponentiating modulo $p$ is cyclic: the sequence $1,a,a^2,a^3,\dots$ must return to a previous value once because there are only $p$ possible values, and it turns out that the length of this cycle divides $p-1$. – Berci Mar 6 '14 at 0:29

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

-

Hint $\ \color{#c00}{A^J} \equiv A\equiv \color{#0a0}{A^K}\,\Rightarrow\, A^{JK}\equiv (\color{#c00}{A^J})^K\equiv \color{#0a0}{A^K}\equiv A$

-

Hint: Take $k = 2$. We have $$a^{p^2} \equiv (a^p)^p \equiv (a)^p \equiv a \pmod p$$

-
A bit of exponent excess. $a^{p^2} = (a^p)^p$. But good idea. – hardmath Mar 6 '14 at 0:51
you're right. Exponents on top of exponents always get me. – Soke Mar 6 '14 at 1:01

a^p = a(modp) ==> a^(p^2) = a^p = a(modp) ==> a^(p^3) = a^p = a(modp) ==> a^(p^k) = a^p = a(modp).

-
In case you don't know, your posts don't automagically format themselves after some time. People have to do that. – user2345215 Mar 6 '14 at 0:29

$a^{p^k}=(((a^p)^p)...) \equiv ... \equiv( (a^p)^p)^p \equiv (a^p)^p \equiv a^p \equiv a$ by simply iterating Fermat's Little Theorem within the delimeters.

-

When I encountered the same theorem I used induction on a: $(a+1)^{p} = a^{p} + p(\mathrm{something}) + 1 ≡ a + 1$

Since $p$ is prime, all $\binom {k} {p}$ are divisible by $p$.

-