Exponential Modular Arithmetic Calculation

Question

How to calculate $32^{61} \bmod 85$ by hand ?

85 = 5 * 17

can anyone show me the steps in detail ?

Answer 1

Note that: $$32^{61}=(2^5)^{61}=2^{305};\\ 2^8\equiv 1 \pmod{85} \Rightarrow (2^8)^{38}\cdot 2\equiv 1^{38}\cdot 2\equiv 2 \pmod{85}.$$

Answer 2

Use Euler's theorem:

$\varphi(85)=\varphi(5)\,\varphi(17)=64$, so as $32$ and $85$ are coprime, $$32^{61}\equiv32^{-3}=(32^{-1})^3.$$ Now the extended Euclidean algorithm yields the Bézout's identity: $$8\cdot 32 -3\cdot 85=1,$$ so $32^{-1}\equiv8\mod85$, so $$32^{61}\equiv 2^9=512\equiv 2 \mod 85.$$

Answer 3

$\!\bmod 5\ \&\ 17\!:\ \color{#c00}{2^{\large 4}}\equiv \pm1\Rightarrow 2^{\large 1+8n}\!\equiv 2(\color{#c00}{2^{\large 4}})^{\large 2n}\!\equiv 2,\,$ so $\,5,17\mid 2^{\large 1+8n}\!-\!2\,$ so lcm $=85$ divides it too