Friday, January 11, 2019

discrete mathematics - 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}$.


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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...