# Congruence involving CRT

I was working on a problem, I arrived at the point at which I have to find $$17^{{{17}^{17}}^{17}} \pmod {25}$$

My attempt: $$17^{{{17}^{17}}^{17}}\equiv 17^{{{{17}^{17}}^{17}} \pmod{\phi(25)}} \pmod {25}$$$$17^{{{17}^{17}}}\equiv 17^{{{{17}^{17}}} \pmod{\phi(20)}} \pmod{20}$$$$17^{17}\equiv1^{17}\equiv1\pmod{\phi(20)=8}$$ Thus:$$17^{{{17}^{17}}^{17}}\equiv 17^{17}\equiv17^{-8}\equiv(17^{-1})^{8}\pmod{25}$$ The inverse of $$17$$ modulo $$25$$ its $$3$$ since $$17\cdot3=51$$, so:$$17^{{{17}^{17}}^{17}}\equiv3^{8} \equiv3^3\cdot3^3\cdot3^2\equiv2\cdot2\cdot9\equiv36\equiv11\pmod{25}$$ I checked but the solutions says that it is actually congruent to $$2$$ and not $$11$$, everything before the inverse it's fine for sure since OP follows the same procedure, what did I do wrong?

There is a mistake. $$17^{{{17}^{17}}^{17}}\equiv 17^{17}\equiv17^{\color{red}{-8}}\equiv(17^{-1})^{\color{red}{8}}\pmod{25}$$ should be $$17^{{{17}^{17}}^{17}}\equiv 17^{17}\equiv17^{\color{red}{-3}}\equiv(17^{-1})^{\color{Red}{3}}\pmod{25}$$
• Wait, I know this might be a dumb question but... $17^{17} \neq 17^{17 \pmod {25}} \pmod{25}$ that's the error right? – Spasoje Durovic Dec 9 '18 at 12:25
• Yeah, CRT applied in a different part of the problem since i was evaluating that ugly $17^{17^{17^{17}}}$ thing in $\pmod{100}$ so I broke it down into two congruences, one modulo $4$ and the other modulo $25$ – Spasoje Durovic Dec 9 '18 at 14:26