Prueba de primalidad para una clase específica de números naturales utilizando factores de polinomios de Lucas

Question

Esta pregunta está relacionada con mi pregunta anterior .

¿Puede probar o refutar la siguiente afirmación:

Dejar $N=2n+1$ dónde $n$ es un número natural impar mayor que uno, sea $L_m(x)$ sea ​​el m-ésimo polinomio de Lucas y sea $F_m(x)$ denotar un factor de grado irreductible $\varphi(m)$ de $L_m(x)$. Si existe un entero$a$ tal que $F_{n}(a) \equiv 0 \pmod{N} $ entonces $N$ es un primo.

Puede ejecutar esta prueba aquí . He verificado esta afirmación solo para valores pequeños de$N$ , es decir $N \in [7,1000]$ con $a \in [1,100]$ , porque mi implementación de PARI / GP de la prueba es demasiado lenta.

EDITAR

Para valores de $n$que son números primos impares, esta prueba se ejecuta en tiempo polinomial ( implementación PARI / GP ). La lista de números primos de Sophie Germain se puede encontrar aquí .

Answer 1

Esta afirmación se puede probar esencialmente de la misma manera que la anterior . Tenemos$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ dónde $\zeta\in\mathbb{C}$ es un primitivo $2n$-ésima raíz de la unidad. El campo de división de$F_n(x)$ es el $n$-ésimo campo ciclotómico.

Asumir que $q\nmid n$ es un número primo tal que la reducción de $F_n(x)$ modificación $q$ tiene una raíz en $\mathbb{F}_q$. Las raices de$F_n(x)$ en $\overline{\mathbb{F}_q}$ son de la forma $\xi^m-\xi^{-m}$, dónde $\xi\in\overline{\mathbb{F}_q}$ es un primitivo $2n$-ésima raíz de la unidad. Por supuesto, el automorfismo de Frobenius$t\mapsto t^q$ corrige una de estas raíces, que solo es posible cuando $q\equiv 1\pmod{2n}$. De ello se deduce que, para cualquier$a\in\mathbb{Z}$, los factores primos de $F_n(a)$ coprime a $n$ son congruentes con $1$ modulo $2n$. En particular, si$2n+1$ divide $F_n(a)$, entonces el único factor primo de $2n+1$ puede ser él mismo, es decir, $2n+1$ es primordial.