1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Mathematics Stack Exchange. Since $37$ is prime, you should reduce the exponent $(2020^{2020})$ modulo $36$ $\endgroup$ – J. W. Tanner Sep 15 at 2:36
  • $\begingroup$ 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$$ $\endgroup$ – Sphynx Sep 15 at 3:03
  • $\begingroup$ No; for one thing, $2020^{36}$ is even; Euler's theorem applies when the base and modulus are relatively prime $\endgroup$ – J. W. Tanner Sep 15 at 3:09
  • $\begingroup$ For the quickest way see here and here and here $\endgroup$ – Bill Dubuque Sep 15 at 8:59
  • $\begingroup$ @BillDubuque Thank you so much! That helps break down the concepts! :) $\endgroup$ – Sphynx Sep 15 at 13:03
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! that explains! $\endgroup$ – Sphynx Sep 15 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.