¿Cómo calcula el $2^{47} \pmod{\! 65}$?

Question

Estoy tratando de calcular $2^{47}\pmod{\! 65}$, pero no sé cómo...

Sé que: $65=5\cdot 13$ y que:

$2^{47}\equiv 3 \pmod{\! 5}$ and $2^{47}\equiv 7\pmod{\! 13}$... (Yo usé de Euler)

Pero, ¿cómo debo seguir desde aquí? (Vi en WolframAlpha que el resultado es 33, pero no tengo ni idea cómo conseguirlo...)

Me gustaría recibir cualquier ayuda...

¡Gracias!

Answer 1

$\varphi(65)=(5-1)(13-1)=48$, así que por el Teorema de Euler (desde $(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

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

Answer 3

Es posible que estos dos hechos útiles. $$2^6 =64\equiv -1\ \ \pmod{65} $$ and $$(2^a)^b=2^{ab}$$

Answer 4

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

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

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

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

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