Encontrar $x$ tal que $2^{4370} \equiv x \ (\mathrm{mod} \ 31)$

Question

Cómo encontrar $x$ tal que $2^{4370} \equiv x \ (\mathrm{mod} \ 31)$ ?

La tarea consiste en calcular $2^{4370} \ (\mathrm{mod} \ 4371$ ).

Sé que es $4371=3 \cdot 31 \cdot 47$ , por lo que es $2 \equiv -29 \ (\mathrm{mod} \ 31)$ .

Con el pequeño teorema de Fermat es $-29^{30} \equiv 1 \ (\mathrm{mod} \ 31)$

$\Rightarrow 2^{4370} \equiv -29^{4370} \equiv -29^{145 \cdot 30+20} \equiv -29^{20} \ (\mathrm{mod} \ 31)$ .

Pero, ¿cómo continuar?

Quiero encontrar un número menor que $-29^{20}$ sin calculadora. La calculadora dice $x=1$ ¿pero cómo encontrarlo sin?

Answer 1

Una forma de proceder es encontrar un $n$ para obtener $2^n$ cerca (a la izquierda o a la derecha) de $31$ .

Bien

$\quad 2^5 = 32 \equiv 1 \;(\text{ mod 31})$

No podría salir mucho mejor; sí, $0 \lt 1$ pero...

Así que

$\quad \displaystyle 2^{4370} = ({2^5})^{874} \equiv (1)^{874} \;(\text{ mod 31}) \equiv 1 \;(\text{ mod 31})$

---

El pequeño teorema de Fermat funciona a las mil maravillas para el módulo $3$ (resp. $47$ ) ya que $3 -1 = 2$ divide $4370$ (resp. $47 - 1 = 46$ divide $4370$ ). Pero aunque $30$ no divide $4370$ podemos seguir utilizándolo cuando trabajemos en módulo $31$ . Copia el comentario de J.W.Tanner,

$\quad 2^{4370}\equiv2^{4350}2^{20}\equiv(2^{30})^{145}2^{20}\equiv 2^{20} \bmod31$

Aplicando cualquier táctica de "divide y vencerás" descubrirás que

$\quad 2^{20} \equiv1\bmod31$