10
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Berci Mar 6 '14 at 0:29
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

Hint $\ $ By an obvious induction, any set closed under multiplication is closed under powers.

Note that $\ \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.

In particular $\ a^P\equiv a\,\Rightarrow\, p\in S\,\Rightarrow\, p^k\in S\,$ for all $\,k\ge 1$.

Remark $\ $ Note how bringing to the fore the innate monoid structure (closure under product) serves to reduce the induction to a trivial induction, that monoids are closed under powering. Such simplifications are often possible in common inductive proofs, so it is worthwhile to first search for such simplifying structure before diving head-first into brute-force inductions.

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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