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.

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

This is a partial answer.

This answer proves that if $F_n(b)$ is prime, then $S_{2^n-2} \equiv 0 \pmod{F_n(b)}$.

Proof :

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)}$$


Your Answer

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

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