Can someone provide me a simplest way to calculate:

Question

$42^{17} \pmod{3233}$

I know the answer is 2557 - But I need to know how to calculate this without help of a machine that generates the answer.

Thank you!

Answer 1

i have this here $$42^5\equiv 440 \mod 3233$$ and $$42^{10}=(42^{5})^2\equiv 2853 \mod 3233$$ and then we use that $$42^7\equiv 240 \mod 3233$$ then we get the searched result.

Answer 2

If you're proficeint with double-digit mental arithmetic then it can be done mentally as follows.

$3233 = 3249-16 = 57^2\!-4^2 = 53\cdot 61.\,$ Repeated squaring mod $61$ and $53$ we find

${\rm mod}\ 61\!:\,\ 42\equiv -19 \overset{x^2}\to\color{#c00}{ -5}\overset{x^2}\to 25\overset{x^2}\to 15\overset{x^2}\to -19,\ $ i.e. $\ 42^{16}\equiv -19,\,$ therefore

$42^{17}\equiv (-19)^2\equiv\color{#c00}{-5}\pmod{61}.\ $ Similarly $\,42^{17}\equiv \color{#0a0}{13}\pmod{53}.\ $ Applying CRT

${\rm mod}\ 53\!:\ \color{#0a0}{13} \equiv 42^{17} \equiv \color{#c00}{-5}+61k \equiv -5+8k \iff k \equiv \frac{18}8 = \frac{9}4 \equiv \frac{-44}4 \equiv \color{#c0f}{-11} $

Therefore $\ 42^{17} = -5 + 61(\color{#c0f}{-11} + 53n) = -676 + 3233n = 2557+3233(n\!-\!1)$