Conjectured primality test for $F_n(28)=28^{2^n}+1$

362 Views Asked by At

How to prove that following conjecture is true ?


Definition

Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ ,

where $m$ and $x$ are nonnegative integers .


Conjecture

Let $F_n(28)=28^{2^n}+1$ with $n\ge 2$ .

Let $S_i=P_{28}(S_{i-1})$ with $S_0=P_{14}(P_{14}(8))$

thus ,

$F_n(28)$ is prime iff $S_{2^n-2} \equiv 0 \pmod{F_n(28)}$


PARI/GP implementation of test

T28(n)=
{ 
my(s=Mod(2*polchebyshev(14,1,polchebyshev(14,1,4)),28^2^n+1));
for(i=1,2^n-2, s=2*polchebyshev(28,1,s/2));
s==0 
}

Searching for counterexample (PARI/GP)

CE28(x,y)=
{
for(n=x,y,
N=28^2^n+1;
my(s=Mod(2*polchebyshev(14,1,polchebyshev(14,1,4)),N)); 
for(i=1,2^n-2, s=2*polchebyshev(28,1,s/2)); 
if(s==0 && !isprime(N),print(n)))
}

P.S.

There is Inkeri's primality test for Fermat numbers in the literature which is very similar to this test , but there is no freely available proof of his test .

1

There are 1 best solutions below

0
On

This is a partial answer.

This answer proves the following : $$\text{if $F_n(28)$ is prime, then $S_{2^n-2}\equiv 0\pmod{F_n(28)}$}$$

Proof :

First of all, we prove by induction that $$S_i=a^{28^i\times 14^2}+b^{28^i\times 14^2}\tag1$$ where $a=4-\sqrt{15},b=4+\sqrt{15}$ with $ab=1$.

Proof for $(1)$:

$$\begin{align}S_0&=P_{14}(P_{14}(8))\\&=P_{14}\left(2^{-14}\left(\left(8-\sqrt{60}\right)^{14}+\left(8+\sqrt{60}\right)^{14}\right)\right)\\&=P_{14}(a^{14}+b^{14})\\&=2^{-14}\left(\left(a^{14}+b^{14}-\sqrt{(a^{14}+b^{14})^2-4}\right)^{14}+\left(a^{14}+b^{14}+\sqrt{(a^{14}+b^{14})^2-4}\right)^{14}\right)\\&=2^{-14}\left(\left(a^{14}+b^{14}-\sqrt{(b^{14}-a^{14})^2}\right)^{14}+\left(a^{14}+b^{14}+\sqrt{(b^{14}-a^{14})^2}\right)^{14}\right)\\&=2^{-14}\left(\left(2a^{14}\right)^{14}+\left(2b^{14}\right)^{14}\right)\\&=a^{28^0\times{14}^{2}}+b^{28^0\times {14}^2}\end{align}$$

Supposing that $(1)$ holds for $i$ gives

$$\begin{align}S_{i+1}&=P_{28}(S_{i})\\&=P_{28}(a^{28^i\times{14}^{2}}+b^{28^i\times{14}^2})\\&=2^{-28}\left(\left(a^{28^i\times{14}^2}+b^{28^i\times{14}^2}-\sqrt{(a^{28^i\times{14}^{2}}+b^{28^i\times{14}^2})^2-4}\right)^{28}+\left(a^{28^i\times{14}^2}+b^{28^i\times{14}^2}+\sqrt{(a^{28^i\times{14}^{2}}+b^{28^i\times{14}^2})^2-4}\right)^{28}\right)\\&=2^{-28}\left(\left(a^{28^i\times{14}^2}+b^{28^i\times{14}^2}-\sqrt{(b^{28^i\times{14}^2}-a^{28^i\times{14}^2})^2}\right)^{28}+\left(a^{28^i\times{14}^2}+b^{28^i\times{14}^2}+\sqrt{(b^{28^i\times{14}^2}-a^{28^i\times{14}^2})^2}\right)^{28}\right)\\&=2^{-28}\left((2a^{28^i\times{14}^2})^{28}+(2b^{28^i\times{14}^2})^{28}\right)\\&=a^{28^{i+1}\times 14^2}+b^{28^{i+1}\times 14^2}\qquad\blacksquare\end{align}$$

Let $N=28^{2^n}+1$. Then, from $(1)$, we have

$$S_{2^n-2}=a^{28^{2^n-2}\times 14^2}+b^{28^{2^n-2}\times 14^2}=a^{(N-1)/4}+b^{(N-1)/4}$$

Now, in order to prove that $S_{2^n-2}\equiv 0\pmod N$, it is sufficient to prove that $S_{2^n-2}^2\equiv 0\pmod N$, i.e. $$a^{(N-1)/2}+b^{(N-1)/2}\equiv -2\pmod N.$$

We use $$a^{(N+3)/2}+b^{(N+3)/2}=(a+b)(a^{(N+1)/2}+b^{(N+1)/2})-(a^{(N-1)/2}+b^{(N-1)/2})\tag2$$

Using that $$\sqrt{4\pm\sqrt{15}}=\frac{\sqrt{10}\pm\sqrt 6}{2}$$ we have $$\begin{align}&2^{N+1}(a^{(N+1)/2}+b^{(N+1)/2})\\&=\left(\sqrt{10}-\sqrt 6\right)^{N+1}+\left(\sqrt{10}+\sqrt 6\right)^{N+1}\\&=\sum_{i=0}^{N+1}\binom{N+1}{i}(\sqrt{10})^i((-\sqrt 6)^{N+1-i}+(\sqrt 6)^{N+1-i})\\&=\sum_{j=0}^{(N+1)/2}\binom{N+1}{2j}(\sqrt{10})^{2j}\cdot 2(\sqrt{6})^{N+1-2j}\\&\equiv 2\cdot 6^{(N+1)/2}+10^{(N+1)/2}\cdot 2\qquad\pmod N\\&\equiv 2\cdot (-6)+(-10)\cdot 2\qquad\pmod N\\&\equiv -32\qquad\pmod N\end{align}$$ (because $6^{(N-1)/2}\equiv -1\equiv 10^{(N-1)/2}\pmod N$) from which we have $$a^{(N+1)/2}+b^{(N+1)/2}\equiv -8\qquad\pmod N$$ since $2^{N+1}\equiv 4\pmod N$ is coprime to $N$.

Also, $$\small\begin{align}&2^{N+3}(a^{(N+3)/2}+b^{(N+3)/2})\\&=\left(\sqrt{10}-\sqrt 6\right)^{N+3}+\left(\sqrt{10}+\sqrt 6\right)^{N+3}\\&=\sum_{i=0}^{N+3}\binom{N+3}{i}(\sqrt{10})^i((-\sqrt 6)^{N+3-i}+(\sqrt 6)^{N+3-i})\\&=\sum_{j=0}^{(N+3)/2}\binom{N+3}{2j}(\sqrt{10})^{2j}\cdot 2(\sqrt 6)^{N+3-2j}\\&\equiv 2\cdot 6^{(N+3)/2}+\frac{(N+3)(N+2)}{2}\cdot 10\cdot 2\cdot 6^{(N+1)/2}+\frac{(N+3)(N+2)}{2}\cdot 10^{(N+1)/2}\cdot 2\cdot 6+10^{(N+3)/2}\cdot 2\quad\pmod N\\&\equiv 2\cdot 6^{(N+3)/2}+6\cdot 10\cdot 6^{(N+1)/2}+6\cdot 10^{(N+1)/2}\cdot 6+10^{(N+3)/2}\cdot 2\qquad\pmod N\\&\equiv 2(-6^2)+60(-6)+6\cdot (-10)\cdot 6+(-10^2)\cdot 2\qquad\pmod N\\&\equiv -992\qquad\pmod N\end{align}$$ from which we have $$a^{(N+3)/2}+b^{(N+3)/2}\equiv -62\qquad\pmod N$$

Hence, from $(2)$, $$\begin{align}a^{(N-1)/2}+b^{(N-1)/2}&=8(a^{(N+1)/2}+b^{(N+1)/2})-(a^{(N+3)/2}+b^{(N+3)/2})\\&\equiv 8(-8)-(-62)\qquad\pmod N\\&\equiv -2\qquad\pmod N\end{align}$$

Thus, $$\begin{align}S_{2^n-2}^2&=(a^{(N-1)/4}+b^{(N-1)/4})^2\\&=a^{(N-1)/2}+b^{(N-1)/2}+2\\&\equiv 0\qquad\pmod N\end{align}$$ from which $S_{2^n-2}\equiv 0\pmod{F_n(28)}$ follows.