Compute the reminder of 3^[(3^101 )] mod 23.

A hint says:You will first need to compute 3^101 (mod 22).

Why mod 22. I understand fermat's little thm. will be used.

Thanks!

By Fermat's Little Theorem, 3^(23 - 1) = 1 (mod 23).
----------
Since 3^101 is in the exponent, we want to see how many times this goes into 22.
This is easily done by computing 3^101 (mod 22).

Since φ(22) = φ(2)φ(11) = 1 * 10 = 10, Euler's Theorem yields 3^10 = 1 (mod 22).
==> 3^101 (mod 22) = 3^(10*10 + 1) = (3^10)^10 * 3^1 = 1^10 * 3 = 3 (mod 22).

So, 3^101 = 3 + 22n for some integer n.
-----------
Finally, 3^(3^101)
= 3^(22n + 3)
= (3^22)^n * 3^3
= 1^n * 27
= 4 (mod 23).

I hope this helps!