# 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: 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. – Michael Tong Mar 6 '14 at 1:01

Hint $\ \ \color{#c00}{A^J} \equiv A\equiv \color{#0a0}{A^K}\,\Rightarrow\, A^{\color{#c00}J\color{#0a0}K}\equiv (\color{#c00}{A^J})^{\color{#0a0}K}\equiv \color{#0a0}{A^K}\equiv A\,$ so the set $S$ of $\,n\,$ with $A^n\equiv A$

satsifies $\ \ \color{#c00}J,\color{#0a0}K\in S\ \Rightarrow\ \color{#c00}J\color{#0a0}K\in S,\$ i.e. $S\,$ is closed under multiplication, so under powers,

therefore $\,p\in S\,\Rightarrow\, p^k\in S$

-

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

-