# How to solve $23^{{2020}^{2020}} \bmod 37$? Please see the body of the 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.

• Welcome to Mathematics Stack Exchange. Since $37$ is prime, you should reduce the exponent $(2020^{2020})$ modulo $36$ – J. W. Tanner Sep 15 at 2:36
• Hi @J.W.Tanner, Thank for the comment. Based on what you just said, is the following right? $$2020^{2020} \mod 36$$ = $$2020^{56 * 36+4} \mod 36$$ = $$2020^{56} * 2020^{4} \mod 36$$ as $$2020^{36} = 1 \mod 36$$ – Sphynx Sep 15 at 3:03
• No; for one thing, $2020^{36}$ is even; Euler's theorem applies when the base and modulus are relatively prime – J. W. Tanner Sep 15 at 3:09
• For the quickest way see here and here and here – Bill Dubuque Sep 15 at 8:59
• @BillDubuque Thank you so much! That helps break down the concepts! :) – Sphynx Sep 15 at 13:03

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.
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.