2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$
  • 1
    $\begingroup$ Wait, I know this might be a dumb question but... $17^{17} \neq 17^{17 \pmod {25}} \pmod{25}$ that's the error right? $\endgroup$ – Spasoje Durovic Dec 9 '18 at 12:25
  • $\begingroup$ How silly of me!... I had used the same logic more than once, then I completely messed it up at the end, Thanks! $\endgroup$ – Spasoje Durovic Dec 9 '18 at 12:30
  • $\begingroup$ Haha happens sometimes :) I don't see how CRT applies here though, you've just used lil fermat $\endgroup$ – rsadhvika Dec 9 '18 at 12:32
  • $\begingroup$ 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$ $\endgroup$ – Spasoje Durovic Dec 9 '18 at 14:26

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.