Encontrar la factorización en primos de $2^{22}+1$ ?

Question

El problema es

Hallar la factorización en primos de $2^{22}+1$

Tengo una solución pero creo que debe haber mejores formas:

Mi solución:

$2^{22}+1 = (2^{22} + 2 \cdot 2^{11} +1) - 2 \cdot 2^{11} = (2^{11}+1)^2 - 2^{12}$

y podemos factorizar como

$(2^{11}+1-2^6)(2^11+1+2^6) = (2048+1-64)(2048+1+64)= 1985 \cdot 2113$

A partir de aquí no es inviable a mano, pero creo que debe haber un método mejor.

Answer 1

Supongamos que $p$ es un factor primo de $2^{22}+1$ superior a $5$ . Entonces $2^{22}\equiv -1 \pmod{p}$ . Así sabemos el orden de $2$ modulo $p$ es $44$ y, por tanto $44 \mid p-1$ . Concluimos que $p = 44n+1$ para algunos $n$ .

Usando su factorización, tenemos que $\sqrt{2113} = 45.96\ldots$ . No existen primos de la forma $44n+1$ en el intervalo comprendido entre $5$ y $45$ Así que $2113$ es primo. Para factorizar $1985$ El $5$ es fácil, y nos quedamos con $397$ . De nuevo, no hay primos de la forma $44n+1$ en la gama $5$ a $\sqrt{397}$ así que también es de primera.