Demuestre que todos los números de Fermat pasan la base $2$ prueba (pseudoprima).

Question

Me doy cuenta de que hay un post similar a este, pero ese post incluía una pista que no se nos dio. También con respecto a esa pista, me pregunto cómo alguien podría descubrirla por sí mismo. Aquí está el post relacionado:

Demuestre que todo número compuesto de Fermat es un pseudoprimo de base 2.

Sé que $F_n = 2^{2^n} + 1$ y por lo tanto $\,2^{2^n} \equiv -1 \pmod{F_n}$ .

Pero no sé intuir el siguiente paso a dar para demostrar que $\ 2^{F_n}\equiv 2\pmod{\!F_n},\,$ es decir, que $$2^{2^{2^n} + 1} \equiv 2 \pmod{2^{2^n}+1}$$

Así que en esencia, me gustaría saber cómo resolverlo sin conocer la pista. Gracias.

Answer 1

Tenemos que demostrar $$2^{2^{2^n}+1}\equiv 2 \mod 2^{2^n}+1$$

Ver que $2^{2^n}\equiv -1\mod 2^{2^n}+1$ y elevando ambos lados al poder $2^{2^n-n}$ vemos

$$(2^{2^n})^{2^{2^n-n}}\equiv 1\mod 2^{2^n}+1$$

y así

$$2^{2^n\cdot2^{2^n-n}}\equiv 2^{2^{2^n}}\equiv 1\mod 2^{2^n}+1$$

Ahora multiplique por $2$ y hemos terminado.