Encontrar un número de Fermat con un determinado factor principal

Question

Es sabido que si un número de Fermat $F(n) \triangleq 2^{2^n} + 1$ es compuesto, entonces cada uno de sus factores primos puede ser escrito como

$$p = 2^{n+2}k + 1\;,$$

para algún entero positivo $k$. Desde $p \leq F(n)$, podemos ver que $k < 2^{2^{n-1} - n - 2}$.

Ahora, yendo hacia atrás, dado que algunos de los números primos de esta forma, quiero saber si hay un número de Fermat que "contiene".

Es posible escribir $p$ $n+1$ maneras:

$$p = 2^{n+2}k + 1 = 2^{n+1}(2k) + 1 = 2^n(4k) + 1 = \ldots = 2^3(2^{n-1}k) + 1 = 2^2(2^{n}k) + 1\;,$$

lo que sugiere $n+1$ posible Fermat números para ser un múltiplo de $p$. Sin embargo, desde la $k$ no es arbitrariamente grande, se puede eliminar la $r$ más pequeños, donde

$$\begin{align} r &= \max_{s \in \mathbb{Z}} \left\{2^{s+1}(2^{n-s+1}k) + 1 \not \leq \sqrt{F(s-1)} \right\} =\\ &= \max_{s \in \mathbb{Z}} \{2^{s+1}(2^{n-s+1}k) + 1 \not \leq 2^{2^{s-2}}\} =\\ &= \max_{s \in \mathbb{Z}} \{2^{n-s+1}k \not< 2^{2^{s-2}-s-1}\} =\\ &= \max_{s \in \mathbb{Z}} \{2^{n+2}k \geq 2^{2^{s-2}}\} =\\ &= \max_{s \in \mathbb{Z}} \{s \leq \log_2(n + \log_2k + 2) + 2\}\\ &= \lfloor \log_2(n + \log_2k + 2) + 2 \rfloor\;. \end{align}$$

¿Cómo puedo ir en y por el tamiz el resto de los números de Fermat, $F(r)$$F(n)$?

Answer 1

Si usted tiene algunos de los números primos $p=2^{n+2}k+1$ $k$ impar, entonces usted sabe que si se divide algunos $F(m)$ debe ser en el caso de que $m\le n$. Así que usted puede simplemente calcular los números de $F(1),F(2),\dots,F(n)$ haciendo todos los cálculos modulo $p$, y a ver si alguna vez te has cero.

Me sorprendería si hubiera una mejor manera.

Answer 2

Respuesta corta: Simplemente marque los números

$$2,2^2,2^4,2^8,2^{16},\ldots,2^{2^n}$$

modulo $p$ y ver cuál, si alguna, es igual a $-1$ modulo $p$. Cada uno de ellos es la plaza de la anterior, así que esta es rápido para comprobar.

---

Deje $p>2$ ser cualquier extraño prime. Considerar el grupo multiplicativo $(\mathbb{Z}/p\mathbb{Z})^\times$ y tenga en cuenta que $2 \in (\mathbb{Z}/p\mathbb{Z})^\times$.

Ahora calcular la multiplicación el orden de $2$ modulo $p$, que nos llame a ese orden $r$. Ahora si $r$ es no es una potencia de 2, es decir, $r$ tiene una extraña primer factor, entonces nuestra $p$ no dividir cualquier número de Fermat (ejercicio fácil).

Por otro lado, si $r$ es en la forma $r=2^n$, luego en particular

$$2^{2^n} \equiv 1 \pmod p$$

y debido a que $r$ es mínima, tenemos necesariamente,

$$2^{2^{n-1}} \equiv -1 \pmod p$$

que es eqivalent a $2^{2^{n-1}}+1 \equiv 0 \pmod p$ o

$$p|F(n-1)$$

y por el fácil ejercer este es el único número de Fermat que $p$ divide (de ello se sigue que no $p$ puede dividir más de un número de Fermat).

Como ejemplo tomemos $p=641$, tenga en cuenta el orden de $2$ dentro $(\mathbb{Z}/641\mathbb{Z})^\times$. Sabemos que será algún divisor del orden de grupo $640$. Resulta que el orden es $r=64$. Una potencia de dos, $64=2^6$, llegamos a la conclusión de $641|F(5)$.

Normalmente para calcular el orden de $r$, sería de verificación

$$2,2^2,2^3,2^4,2^5,\ldots$$

modulo $641$, y sería garantía de que usted golpea $1$ más pronto o más tarde. Así que la multiplicación repetida por $2$. Pero para nuestro propósito sólo tenemos que comprobar

$$2,2^2,2^4,2^8,2^{16},\ldots$$

y si en algún momento nos golpea $1$, sabemos que el anterior número se $-1$, y tenemos nuestra respuesta. Si pasamos $2^{1024}$ o algo, somos pasado $2^{640}$ ya, y sabemos que nunca llegará a $1$ por repetir el cuadrado, por lo que llegamos a la conclusión de que el orden de $r$ no es una potencia de dos, y nuestro primer divide ningún número de Fermat.