# Primality test for specific class of generalized Fermat numbers

Can you provide a proof or a counterexample for the following claim :

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$F_{p,n}= (2p)^{2^n}+1$$ where $$p$$ is a prime number greater than $$5$$ , and $$n\ge2$$ . Let $$S_i=P_{2p}(S_{i-1})$$ with $$S_0=P_{p^2}(8)$$ , then $$F_{p,n} \text{ is prime iff } S_{2^n-2} \equiv 0 \pmod{F_{p,n}}$$ .

You can run this test here . A list of generalized Fermat primes sorted by base can be found here . I have verified this claim for $$p \in [7,5000]$$ with $$n \in [2,10]$$ and there were no counterexamples .

• Looks like a generalization of arxiv.org/abs/0705.3664 (which concerns $b=2$) – Max Alekseyev Apr 22 '18 at 13:09
• @MaxAlekseyev Actually this is a generalization of Inkeri's primality test for Fermat numbers...Reference : Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I 279 (1960), 1-19. – Peđa Terzić Apr 22 '18 at 13:43
• It might be worth noting that the $P_m$ satisfy a particularly straightforward linear recurrence. – Steven Stadnicki Apr 24 '18 at 21:46
• $P_m(x)=2T_m(x/2)$ where $T_m(x)$ is the Chebyshev polynomial of the first kind. The claim can be rephrased as $F_{p,n}$ is prime iff $T_{2^{2^n-2}p^{2^n}}(4)=0$ mod $F_{p,n}$. Since $T_m(T_n(x))=T_{mn}(x)$, the RHS can be computed efficiently as $T_{ (2p)}^{2^n-2}(T_{p^2}(4))$ mod $F_{p,n}$, where the $2^n-2$ in the power means iteration. – Chua KS Aug 15 '20 at 4:48
• It seems useful to state many of your tests in term of Chebyshev.Eg. Lucas-Lehmer for Mersenne prime $M_p=2^p-1$ can be rephrased as $M_p$ is prime iff $T_{2^{p-2}}(2)=0$ mod $M_p$ and the Chebyshev rule $T_m(T_n(x))=T_{mn}(x)$ implied many possible method for computing the residue. Since $2^{p-2}=4^{(p-3)/2}.2$, one can iterate with $T_4$ as $T_{2^{p-2}}(2)=T_4^{(p-3)/2}(T_2(2))$ mod $M_p$. This halfed the number of steps but evaluating $T_4$ is more expansive. Every partition of $p-2$ into positive parts give a different way to compute the residue. At least good for checking correctness – Chua KS Aug 18 '20 at 2:18