5
$\begingroup$

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 .

Improve this question
$\endgroup$
5
  • $\begingroup$ Looks like a generalization of arxiv.org/abs/0705.3664 (which concerns $b=2$) $\endgroup$
    – Max Alekseyev
    Commented Apr 22, 2018 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$
    – Pedja
    Commented Apr 22, 2018 at 13:43
  • $\begingroup$ It might be worth noting that the $P_m$ satisfy a particularly straightforward linear recurrence. $\endgroup$
    – Steven Stadnicki
    Commented Apr 24, 2018 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
    Commented Aug 15, 2020 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
    Commented Aug 18, 2020 at 2:18

0

Reset to default

You must log in to answer this question.