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.


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.


1 Answer 1


This claim can be proved in essentially the same way as the previous one. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.