Modular arithmetic problem (mod $13$) $$\large2017^{(2020^{2015})} \pmod{13}$$
I am practicing for my exam and I can solve almost all problem, but this type of problem is very hard to me. In this case, I have to compute this by modulo $13$.
 A: As $2017\equiv2\pmod{13},$
$$2017^{2020^{2015}}\equiv2^{2020^{2015}}\pmod{13}$$
Now as $(2020,\phi(13))=4,$ let us find $2020^{2015-1}\pmod{\dfrac{12}4}$
As $2020\equiv1\pmod3\implies2020^{2015-1}\equiv1\pmod3$
$2020^{2015}\equiv2020\cdot1\pmod{3\cdot2020}\equiv2020\pmod{12}\equiv4$
$\implies2^{2020^{2015}}\equiv2^4\pmod{13}=?$
A: Let's try to see what we can infer from $2017\bmod{13}$:
$2017\equiv\color\red{2}\pmod{13}\implies$
$2017^{6}\equiv\color\red{2}^{6}\equiv\color\green{-1}\pmod{13}\implies$
$2017^{\color\orange{12}}\equiv(2017^6)^2\equiv(\color\green{-1})^2\equiv\color\magenta{1}\pmod{13}$

This means that we can find the answer by representing $2020^{2015}$ as $\color\orange{12}m+n$:
$2017^{2020^{2015}}\equiv2017^{\color\orange{12}m+n}\equiv(2017^{\color\orange{12}})^{m}\cdot2017^{n}\equiv\color\magenta{1}^{m}\cdot\color\red{2}^{n}\pmod{13}$

Let's show by induction that $2020^k\equiv\color\purple{4}\pmod{\color\orange{12}}$:


*

*Base case:      $2020^1\equiv\color\purple{4}\pmod{\color\orange{12}}$

*Assumption:     $2020^k\equiv\color\purple{4}\pmod{\color\orange{12}}$

*Inductive step: $2020^{k+1}\equiv2020^k\cdot2020^1\equiv\color\purple{4}\cdot\color\purple{4}\equiv\color\purple{4}\pmod{\color\orange{12}}$



Therefore $2020^{2015}=\color\orange{12}m+\color\purple{4}$, and this gives the final answer:
$2017^{2020^{2015}}\equiv2017^{\color\orange{12}m+\color\purple{4}}\equiv(2017^{\color\orange{12}})^{m}\cdot2017^{\color\purple{4}}\equiv\color\magenta{1}^{m}\cdot\color\red{2}^{\color\purple{4}}\equiv3\pmod{13}$
A: ${\rm mod}\ \color{#c00}{12}\!:\, (\overbrace{4\!+\!12k}^{\large \rm e.g.\  2020})^{\large 1+n}\!\equiv 4^{\large 1+n}\!\equiv\! \overbrace{4(4^{\large n}\!\bmod 3)}^{\rm\large mod\ Distribute}\!\equiv 4(1^{\large n}\!\bmod 3)\equiv \color{#c00}4,\ $ therefore
${\rm mod}\ 13\!:\,\ a^{\large (4+12k)^{\LARGE 1+n}}\!\equiv a^{\large\color{#c00}{4+12k}}\equiv \underbrace{a^{\large 4}(\color{#0a0}{a^{\large 12}})^{\large k}\!\equiv a^{\large 4} \color{#0a0}{\bf 1}^{\large k}\!}_{\large \rm by\ \color{#0a0}{\rm Fermat}\ \&\  13\ \nmid\ a}\equiv a^{\large 4},\, $  so $\,{a\equiv 2017\equiv  2}\Rightarrow\,a^{\large 4}\!\equiv 16$
