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 .

  • $\begingroup$ Looks like a generalization of arxiv.org/abs/0705.3664 (which concerns $b=2$) $\endgroup$ – Max Alekseyev Apr 22 '18 at 13:09
  • $\begingroup$ @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. $\endgroup$ – Peđa Terzić Apr 22 '18 at 13:43
  • $\begingroup$ It might be worth noting that the $P_m$ satisfy a particularly straightforward linear recurrence. $\endgroup$ – Steven Stadnicki Apr 24 '18 at 21:46
  • $\begingroup$ $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. $\endgroup$ – Chua KS Aug 15 '20 at 4:48
  • 1
    $\begingroup$ 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 $\endgroup$ – Chua KS Aug 18 '20 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.