How do I calculate $2^{47} \pmod{\! 65}$?

Question

I'm trying to calculate $2^{47}\pmod{\! 65}$, but I don't know how...

I know that: $65=5\cdot 13$ and that:

$2^{47}\equiv 3 \pmod{\! 5}$ and $2^{47}\equiv 7\pmod{\! 13}$... (I used Euler)

But how should I continue from here? (I saw at WolframAlpha that the result is 33, but I don't have any idea how to get it...)

I'd like to get any help...

Thank you!

Answer 1

$\varphi(65)=(5-1)(13-1)=48$, so by Euler's theorem (since $(2,65)=1$):

$$2x\equiv 2\cdot 2^{47}\equiv 2^{48}\equiv 1\pmod{\! 65}$$

$$2x\equiv 66\stackrel{:2}\iff x\equiv 33\pmod{\! 65}$$

Answer 2

You might find these two facts helpful. $$2^6 =64\equiv -1\ \ \pmod{65} $$ and $$(2^a)^b=2^{ab}$$

Answer 3

$2^6=64$, so $\,2^6\equiv -1 \pmod{\! 65}\,$ and $47=6\cdot 7+5$; then $2^{47}\equiv (2^6)^7\cdot 2^5\equiv (-1)^7\cdot 32\equiv -32 \equiv 33 \pmod{\! 65}$

Answer 4

As $65=5\cdot13$ with $(5,13)=1,$

$2^6=64\equiv-1\pmod{13}$ and $2^6\equiv-1\pmod5$

$\implies2^6=64\equiv-1\pmod{13\cdot5}$

Now $47\equiv-1\pmod6\implies2^{47}\equiv2^{-1}\pmod{65}$

As $33\cdot2-65=1,2\cdot33\equiv1\pmod{65}\iff2^{-1}\equiv33$