This question is related to my [previous question](https://mathoverflow.net/q/369144/88804).


Can you prove or disprove the following claim:



> 
> Let $N=2n+1$ where $n$ is an odd natural number greater than one , let $L\_m(x)$ be the mth Lucas polynomial and let $F\_m(x)$ denote an irreducible factor of degree $\varphi(m)$ of $L\_m(x)$ . If there exists an integer $a$ such that $F\_{n}(a) \equiv 0 \pmod{N} $ then $N$ is a prime.
> 
> 
> 


You can run this test [here](https://sagecell.sagemath.org/?z=eJw9zsFugzAMBuA7j9GTXTKNsKPnRygvUPWQtqFEQGKFhCFNffeFbtrJv-Rfn-35g6qO26OvNVVTvpkFZuRvabgl0bzRWMLX4CYL4yfPSng7iq6loVIRvXeExrpGijbl6EHwSVVvbgl8cTLvMUT4pcG_aXxvEWnlfFb6Qn3ZOdZqsv6RBlhRuR4kTHf7iNbCenYXZLZ5slEG9w-ov2uvfeGe1Q6ZAoWwC6dwhyVflwSvVzpUmzKoumI1SqLzCQ5lzPaAdI3WjMX4AXu0U7s=&lang=gp&interacts=eJyLjgUAARUAuQ==). I have verified this claim only for small values of $N$ , that is $N \in [7,1000]$ with $a \in [1,100]$ , because my PARI/GP implementation of the test is too slow.


**EDIT**


For values ​​of $n$ that are odd prime numbers this test runs in polynomial time ([PARI/GP implementation](https://sagecell.sagemath.org/?z=eJxFjE0KwjAQRvc5xdBVkg7YxOUwR_AEIULEFoLkh9pFiujZDV3o7uPx3lf5TCKz1XU0JFoKm8wYFDC4gGAIDMLk9aXcpUGr82gUibTHZ11jmg-XX2mXrfbkl1-zdl0_Bf9R1KqzHphhordYyioDGywF4yL_R7VX2Gfe5HCQQdFtncNDKfoC6ncwuw==&lang=gp&interacts=eJyLjgUAARUAuQ==)) . List of Sophie Germain primes can be found [here](https://oeis.org/A005384).



Primality test for specific class of natural numbers using factors of Lucas polynomials
This claim can be proved in essentially the same way as the [previous one](https://mathoverflow.net/q/369144/88804). We have
$$F\_n(x)=\prod\_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$
where $\zeta\in\mathbb{C}$ is a primitive $2n$-th root of unity. The splitting field of $F\_n(x)$ is the $n$-th cyclotomic field.


Assume that $q\nmid n$ is a prime number such that the reduction of $F\_n(x)$ mod $q$ has a root in $\mathbb{F}\_q$. The roots of $F\_n(x)$ in $\overline{\mathbb{F}\_q}$ are of the form $\xi^m-\xi^{-m}$, where $\xi\in\overline{\mathbb{F}\_q}$ is a primitive $2n$-th root of unity. By assumption, the Frobenius automorphism $t\mapsto t^q$ fixes one of these roots, which is only possible when $q\equiv 1\pmod{2n}$. It follows that, for any $a\in\mathbb{Z}$, the prime factors of $F\_n(a)$ coprime to $n$ are congruent to $1$ modulo $2n$. In particular, if $2n+1$ divides $F\_n(a)$, then the only prime factor of $2n+1$ can be itself, i.e., $2n+1$ is prime.


