EulerFermatTheorem CRT EndingDigits Difficult

Problem - 4515

Find the last $4$ digits of $2018^{2019^{2020}}$.


Answer     $0768$

Let $N=2018^{2019^{2020}}$, then the result equals $N\pmod{10^4}$.

Because $10^4=2^4\times 5^4$ and $\gcd(2^4,\ 5^4)=1$, it is sufficient to compute $N\pmod{2^4}$ and $N\pmod{5^4}$.

Because $2018 = 2\times 1009$ and $2019^{2020} > 4$, therefore $N\equiv 0\pmod{2^4}$.

Meanwhile $$N=2018^{2019^{2020}}\equiv 143^{2019^{2020}} \pmod{5^4}$$

Because $143$ and $5^4$ are co-prime and $\phi{5^4}=500$, applying Euler's theorem gives $$143^{500}\equiv 1\pmod{5^4}\implies N\equiv 143^{2019^{2020}\pmod{500}}\pmod{5^4}$$

Meanwhile, $19$ and $500$ are co-prime and $\phi{500}=200$, it follows that $$2019^{2020}\equiv 19^{2020}\equiv 19^{20}\pmod{500}$$

This expression can be evaluated using the binomial expansion method (note that $20^3\equiv 0\pmod{500}$. $$19^{20}=(20-1)^{20}\equiv\binom{20}{2}20^2 -\binom{20}{1} 20 +1\equiv 101\pmod{500}$$

Setting these results back yields $$N\equiv 143^{101} \pmod{5^4}$$

This can evaluated as follows. $$\begin{align*}143^{101} =\ & (5^2 \times 6 -7)^{100}\times 143\\=\ & \left((5^2\times 6-7)^2\right)^{50}\times 143\\ \equiv\ &(-5^2\times 84 + 49)^{50}\times 143\\ \equiv\ &\underbrace{(-5^2 \times 82 - 1)^{50}}_{A}\times 143\pmod{5^4}\end{align*}$$

Expanding part $A$ and discard any terms containing $5^4$ or higher power gives $$A\equiv \binom{50}{1}(5^2\times 84) +1\equiv 1\pmod{5^4}$$

Hence, we have $$N\equiv 0\pmod{2^4}\equiv\text{and}\quad N\equiv 143\pmod{5^4}$$

Solving this system (e.g. using CRT) gives the result as $$N\equiv \boxed{0768}\pmod{10^4}$$

report an error