How to solve $23^{{2020}^{2020}} \bmod 37$? Please see the body of the question.

Question

How to solve $$23^{{2020}^{2020}} \mod 37.$$ Below given is my understanding of trying to solve the problem.

From $$x^{p-1} = 1 \mod p$$ I deduce that $$23^{2020} \mod 37$$ would be $$23^{56.36+4} \mod 37$$ which is further simplified as $$23^{4} \mod 37$$ as $$23^{\alpha .36} = 1 \mod 37$$

Keeping the above in mind, I am wondering if there is anyway of solving $$23^{{2020}^{2020}} \mod 37.$$ I'm clueless about how to simplify the double exponent.

Answer 1

To explain in more detail what Ross Millikan suggested,

note that $2020^{2020}\equiv0\pmod4$ and $2020^{2020}\equiv 4^{336\times6+4}\equiv4^4\equiv4\pmod9$

($4^6\equiv1\pmod9$ by Euler's Theorem),

so $2020^{2020}\equiv4\pmod{36}$ by the Chinese Remainder Theorem.

Answer 2

From $x^{36} \equiv 1 \pmod {37}$ what you care about is the exponent $\bmod 36$. Now you need to evaluate (not solve) $2020^{2020} \pmod {36}$. The factors of $2$ are easy, as you quickly have two of them. Then you are only interested in evaluating it $\bmod 9$. Back to you.