# Primality test for specific class of natural numbers using factors of Lucas polynomials

This question is related to my previous question.

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. 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) . List of Sophie Germain primes can be found here.

This claim can be proved in essentially the same way as the previous one. We have $$F_n(x)=\prod_{\substack{|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.