A number theory problem by Aditya Moger

The question translates to

$x\equiv 2017^{2017^{2017}} \mod{10000}\quad 0\leq x \leq 9999$

And in case add some $0$ s if $x$ is not a $4$ -digit number

We will split in modulo $16$ and modulo $625$

$x\equiv 2017^{2017^{2017}} \equiv (126\cdot 16+1)^{2017^{2017}} \equiv 1^{2017^{2017}}\equiv 1\mod{16}$

Now modulo $625$ :

$x\equiv 2017^{2017^{2017}}\equiv (3\cdot 625 +142)^{2017^{2017}}\equiv 142^{2017^{2017}} \mod{625}$

Now, using Euler's Theorem twice, with $\phi(625)=500$ and $\phi(\phi(625))=200$

$x\equiv 142^{2017^{2017}}\equiv 142^{(4\cdot 500+17)^{10\cdot 200+17}}\equiv 142^{17^{17}}\mod{625}$

Now, there is not really an easy way to find $y\equiv 17^{17}\mod{500}$ and then $x\equiv 142^y \mod{625}$ but I'll use as much shortcuts as I can

$\begin{aligned} y&\equiv 17^{17}\\ &\equiv 17(17^4)^4\\ &\equiv 17(83521)^4\\ &\equiv 17\cdot 21^4\\ &\equiv 17\cdot 194481\equiv 17(-19)\equiv -323\equiv 177 \mod{500} \end{aligned}$

Now we have $x\equiv 142^{177} \mod{625}$

$\begin{aligned} x&\equiv 142^{177}\\ &\equiv 142(142^2)^{88}\equiv 142(20164)^{88}\equiv 142\cdot 164^{88}\\ &\equiv 142(164^2)^{44}\equiv 142(26896)^{44}\equiv 142\cdot 21^{44}\\ &\equiv 142(21^4)^{11}\equiv 142\cdot 194481^{11}\equiv 142\cdot 106^{11} \mod{625} \end{aligned}$

Now to find $106^{11}\mod{625}$ I'll use the Binomial Theorem

$\begin{aligned} 106^{11}&\equiv (100+6)^{11}\\ &\equiv \binom{11}{0}\cdot 100^{11}+\binom{11}{1}\cdot 100^{10}\cdot 6+\ldots +\binom{11}{10}\cdot 100\cdot 6^{10}+\binom{11}{11}\cdot 6^{11}\\ &\equiv 1100\cdot 6^{10}+6^{11} \mod{625} \end{aligned}$

All the other terms vanished because they contained $4$ or more factors of $5$ , now

$\begin{aligned} 1100\cdot 6^{10}+6^{11}&\equiv 1106\cdot 6^{10}\\ &\equiv 481\cdot 36(6^4)^2\equiv 481\cdot 36\cdot 1296^2 \equiv 481 \cdot 36\cdot 46^2\\ &\equiv 481\cdot 36\cdot 2116\equiv 481\cdot 36\cdot 241\\ &\equiv 17316\cdot 241\equiv 441\cdot 241\equiv 106281 \equiv 31\mod{625} \end{aligned}$

We are nearly done, $x\equiv 142\cdot 31 \equiv 4402\equiv 27 \mod{625}$

We can now put things together using the CRT

$\begin{cases} x\equiv 1 \mod{16}\\ x\equiv 27 \mod{625} \end{cases}$

Since $\gcd(16,625)=1$ there is only one solution modulo $10000$ , namely

$x\equiv \boxed{3777}\mod{10000}$

2017^2017 mod 10000 = 8177

But we need 2017^(2017^2017) mod 10000

Which is the same as...{by using euler's totient} 2017^8177 mod 10000

Which is.... 3777....