What is 333^333^333 in mod 17

Question

Is there an easier way to do this than finding cycles of different mods? Or can I just first do 333 (mod 17), it gives me 10. Then I could change all the 333's into 10s so it would be 10^10^10 and then do (10^10) first to get a remainder of 2 then 2^10 to get 4 in (mod 17), even though it might be time consuming?

Answer 1

Although $333\equiv10\bmod17$, it is not true that $333^{{333}^{333}}\equiv10^{{10}^{10}}\bmod17$.

Generally, $a\equiv b\bmod n$ does not imply that $c^a\equiv c^b\bmod n$.

Rather, $a\equiv b\bmod \phi(n)$ and $\gcd(c,n)=1$ implies $c^a\equiv c^b\bmod n$,

where $\phi(n)$ is Euler's totient function: $\phi(17)=16$ and $\phi(16)=8$.

Now $333\equiv13\bmod16$ and $333\equiv5\bmod8$, so $333^{333}\equiv13^5\bmod16$.

To reduce further, it helps to note that $13^4\equiv(-3)^4=81 \equiv1\bmod16$,

so $13^5\equiv13\bmod16$. Therefore, $333^{{333}^{333}}\equiv10^{{13}}\bmod17$.

Can you take it from here?