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
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$
No comments:
Post a Comment