Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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 at 0:29

6 Answers 6

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|improve this answer

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$

share|improve this answer

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

share|improve this answer
1  
A bit of exponent excess. $a^{p^2} = (a^p)^p$. But good idea. –  hardmath Mar 6 at 0:51
    
you're right. Exponents on top of exponents always get me. –  Michael T Mar 6 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).

share|improve this answer
6  
In case you don't know, your posts don't automagically format themselves after some time. People have to do that. –  user2345215 Mar 6 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|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|improve this answer

Your Answer

 
discard

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.