Last three digits of a large number

number theory

Find the last 3 digits of $2022^{{2023}^{2024}}$

I am stuck to find the last 3 digits using Fermat's Theorem because 2022 is not coprime to 1000.

Since gcd(2022, 1000) = 2, I cannot apply Fermat's Theorem directly.
So let $2022^{{2023}^{2024}} = a \mod 1000$

so that
$2022^{{2023}^{2024}} = a \mod 8$

$2022^{{2023}^{2024}} = a \mod 125$

I can find the a mod 125 because 2022 is coprime with 125 but I don't do the same with a mod 8 because it goes back the coprimeness problem. What can I do next or am I in the right direction. Any help is appreciated.

Best Answer

ANSWERING AFTER THE OP WAS EDITTED

Write $a = 2022^{2023^{2024}}$.

HINT 1: To find $a \pmod{125}$, note that:

  • Let us set $b = 2023^{2024}$. Then

$$a \pmod {125}$$ $$=(a \pmod{125})^{b \pmod{100}}$$ $$=22^{b \pmod{100}}.$$

  • Then $b \pmod{100}$ is a function of $b \pmod {25}$ and $b \pmod {4}$, where:

$$b \pmod{25} =$$ $$(2023 \pmod{25})^{2024\pmod{20}} \pmod{25}$$ $$=(-2)^4 \pmod{25}$$ and $$b \pmod{4} = 3^{2024} \pmod{4}$$ $$=1.$$

HINT 2: $a \pmod 8 = 0$. Indeed, if you take an even number [such as $2022$] and raise it to the $k$-th power, then it is a multiple of $2^k$, and thus a multiple of $2^j$ for each integer $j \le k$. I do think $k=2023^{2024}$ is at least $3$, and thus $2022^k$ a multiple of $8$...

Related Question