Why can't I use Fermat's Small Theorem to calculate $12^{12^{12}} \pmod{13}$?

Question

The answer says it is 1, and I understand why. But why can't I use Fermat's Little Theorem on the exponent like this (by "exponent" I mean the entire $12^{12}$):

$$12^{12} \equiv 1 \pmod{13}$$ Is this not a correct use of Fermat's small theorem? In such case the original problem becomes

$$12^1 \equiv 12 \pmod{13}$$ But this is clearly the wrong answer to $12^{12^{12}} \pmod{13}$.

Answer 1

But why can't I use Fermat's Little Theorem on the exponent like this:

$$\begin{align} &\ \ \,\color{#0a0}{12^{12} \equiv\, 1}\!\! \pmod{\color{#c00}{\!\!13}}\\ \Rightarrow\ &a^{\Large \color{#0a0}{12^{12}}}\!\!\equiv a^{\Large \color{#0a0}1} \equiv a\!\!\!\pmod{\!13}\end{align}\qquad\qquad$$

You used the wrong modulus $\color{#c00}{13\ {\rm vs.}\ 12\,}$ in the $\rm\color{#0a0}{exponent}$. Correct is, by modular order reduction

by Fermat $\bmod 13\!:\ a\not\equiv0\,\Rightarrow\, a^{\large\color{#c00}{12}}\equiv 1\,\Rightarrow\, a^{\large\color{0a0} N}\!\equiv a^{\large\color{#0a0}N\bmod \color{#c00}{12}}\!\equiv a^{\large\color{#0a0}{12^{12}}\bmod 12}\!\equiv a^{\large\color{#0a0}0}\!\equiv 1$

by using the correct exponent reduction calculation: $\bmod\color{#c00}{12}\!:\ N = \color{#0a0}{12^{\large 12}\!\equiv 0^{\large12}\!\equiv\color{#0a0}0}$

Easier: $\bmod 13\!:\ a\equiv 12\equiv -1\,\Rightarrow\,a^{\large\color{#90f} 2}\equiv (-1)^{\large 2}\equiv 1\,$ so we can take $\,N\bmod\color{#90f} 2\,$ vs. $\!\bmod 12$

Answer 2

You can use Fermat's theorem in the form $a^{p-1} \equiv 1 \bmod p$ for $a$ not a multiple of $p$. Then $a^{(p-1)k} \equiv 1 \bmod p$ for all $k$ and so $a^{n} \equiv a^{n \bmod (p-1)} \bmod p$.

In your example, this leads you to compute $12^{12} \bmod 12$, which is easy.

Answer 3

You can, but actually, you're missing that there are two different moduli in using Fermat:

For any $a\not\equiv 0\bmod13$, and any exponent $n$, one has $$a^n\equiv a^{n\bmod 12}\pmod{13}$$ since $a^{12}\equiv 1\bmod 13$, so that, in particular $$12^{12^{12}}\equiv 12^{12^{12}\bmod 12}=12^0=1\pmod{13}.$$ Another way to see it without Fermat is to observe that, since $12\equiv -1\pmod{13}$, one has $12^n\equiv (-1)^n=1\pmod{13}\;$ if $n$ is even.

Answer 4

$12^{12}\equiv1\bmod13,$ so $12^{12q+r}\equiv({12}^{12})^q12^r\equiv12^r\bmod13$

Answer 5

When you use Fermat's little theorem, the exponent gets reduced $\pmod{p-1}$, not $\pmod p$.

According to Euler's theorem, a generalization of Fermat's little theorem, you reduce the exponent $\pmod {\varphi (n)}$, where $\varphi $ is Euler's totient function. When $n=p$, we get $\varphi (p)=p-1$.

The reason is that $a^{\varphi (n)}\cong1\pmod n$, in case $(a,n)=1$.