Why can't I use Fermat's Small Theorem to calculate $12^{12^{12}} \pmod{13}$? 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}$.
 A: 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.
A: 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.
A: $12^{12}\equiv1\bmod13,$ so $12^{12q+r}\equiv({12}^{12})^q12^r\equiv12^r\bmod13$
A: 
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$
A: 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$.
