# Primality test for generalized Fermat numbers

This question is successor of Primality test for specific class of generalized Fermat numbers .

Can you provide a proof or a counterexample for the claim given below?

Inspired by Lucas–Lehmer–Riesel primality test I have formulated the following claim:

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$F_n(b)= b^{2^n}+1$$ where $$b$$ is an even natural number and $$n\ge2$$ . Let $$a$$ be a natural number greater than two such that $$\left(\frac{a-2}{F_n(b)}\right)=-1$$ and $$\left(\frac{a+2}{F_n(b)}\right)=-1$$ where $$\left(\frac{}{}\right)$$ denotes Jacobi symbol. Let $$S_i=P_b(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{b/2}(P_{b/2}(a))\phantom{5} \text{mod} \phantom{5} F_n(b)$$. Then $$F_n(b)$$ is prime if and only if $$S_{2^n-2} \equiv 0 \pmod{F_n(b)}$$ .

You can run this test here. A list of generalized Fermat primes sorted by base $$b$$ can be found here. I have tested this claim for many random values of $$b$$ and $$n$$ and there were no counterexamples.

A command line program that implements this test can be found here.

Android app that implements this test can be found here .

Python script that implements this test can be found here.

Mathematica notebook that implements this test can be found here.

• There are no counterexamples for $b \in [2,10000]$ with $n \in [2,10]$ . – Peđa Terzić Nov 16 '19 at 14:19

This answer proves that if $$F_n(b)$$ is prime, then $$S_{2^n-2} \equiv 0 \pmod{F_n(b)}$$.
Let $$N:=F_n(b)=b^{2^n}+1$$. It can be proven by induction that $$S_i\equiv 2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4})\pmod N\tag1$$ where $$p=a-\sqrt{a^2-4},q=a+\sqrt{a^2-4}$$.
From $$(1)$$, we get, using $$\sqrt{a\pm\sqrt{a^2-4}}=\frac 1{\sqrt 2}(\sqrt{a+2}\pm\sqrt{a-2})$$,
\begin{align}&2^{N+1}\cdot S_{2^n-2}^2-2^{N+2} \\\\&\equiv \left(\sqrt{a+2}+\sqrt{a-2}\right)\left(\sqrt{a+2}-\sqrt{a-2}\right)^{N} \\&\qquad\qquad +\left(\sqrt{a+2}-\sqrt{a-2}\right)\left(\sqrt{a+2}+\sqrt{a-2}\right)^{N}\pmod N \\\\&\equiv \sqrt{a+2}\left(\left(\sqrt{a+2}-\sqrt{a-2}\right)^{N} +\left(\sqrt{a+2}+\sqrt{a-2}\right)^{N}\right) \\&\qquad\qquad-\sqrt{a-2}\left(\left(\sqrt{a+2}+\sqrt{a-2}\right)^{N} -\left(\sqrt{a+2}-\sqrt{a-2}\right)^{N}\right)\pmod N \\\\&\equiv \sqrt{a+2}\sum_{k=0}^{N}\binom Nk(\sqrt{a+2})^{N-k}((-\sqrt{a-2})^k+(\sqrt{a-2})^k) \\&\qquad\qquad -\sqrt{a-2}\sum_{k=0}^{N}\binom Nk(\sqrt{a+2})^{N-k}((\sqrt{a-2})^k-(-\sqrt{a-2})^k)\pmod N \\\\&\equiv \sum_{j=0}^{(N-1)/2}\binom{N}{2j}(a+2)^{(N-2j+1)/2}\cdot 2(a-2)^j \\&\qquad\qquad -\sum_{j=1}^{(N+1)/2}\binom{N}{2j-1}(a+2)^{(N-2j+1)/2}\cdot 2(a-2)^j\pmod N \\\\&\equiv 2(a+2)\cdot\left(\frac{a+2}{N}\right)-2(a-2)\cdot\left(\frac{a-2}{N}\right)\pmod N \\\\&\equiv 2(a+2)\cdot (-1)-2(a-2)\cdot (-1)\pmod N \\\\&\equiv -8\pmod N \end{align} So, we get $$2^{N+1}\cdot S_{2^n-2}^2-2^{N+2}\equiv -8\pmod N$$ It follows from $$2^{(N-1)/2}\equiv 1\pmod N$$ that $$S_{2^n-2}\equiv 0\pmod{F_n(b)}$$