# How do I calculate $2^{47} \pmod{\! 65}$? [duplicate]

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!

• What is $2^6$? How does that help? Jun 20, 2015 at 23:03
• @Yoar, just to use fermat little theorem Jun 20, 2015 at 23:03
• Hint: $65=64+1$
– anon
Jun 20, 2015 at 23:03
• @whacka - but 65 is not prime...
– CS1
Jun 20, 2015 at 23:04
• but you can write it as sum of primes number such that :65=47+7+11 Jun 20, 2015 at 23:06

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

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

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

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$