Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
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$

share|cite|improve this answer

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

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.