Teste de primazia para uma classe específica de números naturais usando fatores de polinômios de Lucas

Question

Essa pergunta está relacionada à minha pergunta anterior .

Você pode provar ou refutar a seguinte afirmação:

Deixei $N=2n+1$ Onde $n$ é um número natural ímpar maior que um, deixe $L_m(x)$ seja o mésimo polinômio de Lucas e deixe $F_m(x)$ denotam um fator irredutível de grau $\varphi(m)$ do $L_m(x)$. Se existe um inteiro$a$ de tal modo que $F_{n}(a) \equiv 0 \pmod{N} $ então $N$ é um primo.

Você pode executar este teste aqui . Eu verifiquei esta afirmação apenas para pequenos valores de$N$ , isso é $N \in [7,1000]$ com $a \in [1,100]$ , porque minha implementação PARI / GP do teste é muito lenta.

EDITAR

Para valores de $n$que são números primos ímpares, este teste é executado em tempo polinomial ( implementação PARI / GP ). A lista dos primos de Sophie Germain pode ser encontrada aqui .

Answer 1

Esta afirmação pode ser provada essencialmente da mesma forma que a anterior . Nós temos$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ Onde $\zeta\in\mathbb{C}$ é um primitivo $2n$-ésima raiz da unidade. O campo de divisão de$F_n(x)$ é o $n$-º campo ciclotômico.

Assuma isso $q\nmid n$ é um número primo tal que a redução de $F_n(x)$ mod $q$ tem uma raiz em $\mathbb{F}_q$. As raízes de$F_n(x)$ dentro $\overline{\mathbb{F}_q}$ são da forma $\xi^m-\xi^{-m}$, Onde $\xi\in\overline{\mathbb{F}_q}$ é um primitivo $2n$-ésima raiz da unidade. Por suposição, o automorfismo de Frobenius$t\mapsto t^q$ fixa uma dessas raízes, o que só é possível quando $q\equiv 1\pmod{2n}$. Segue-se que, para qualquer$a\in\mathbb{Z}$, os principais fatores de $F_n(a)$ coprime para $n$ são congruentes com $1$ modulo $2n$. Em particular, se$2n+1$ divide $F_n(a)$, então o único fator principal de $2n+1$ pode ser ele mesmo, ou seja, $2n+1$ é principal.