Primality test for Proth numbers using Fibonacci numbers

This is a partial answer.

This answer proves that if $N$ is prime, then $$2S_{m-2}^2\equiv (F_n+2)^{(N+1)/2}-(F_n-2)^{(N+1)/2}+4\pmod N\tag1$$

From $(1)$, we can see that in order to prove that $$\text{if $N$ is prime, then there exists $F_n$ for which $S_{m-2}\equiv 0\pmod N$}$$ it is sufficient to prove that $$\text{if $N$ is prime, then there exists $F_n$ such that $\left(\dfrac{F_n\pm 2}{N}\right)=-1$}$$ where $\left(\dfrac{q}{p}\right)$ denotes the Legendre symbol.

From $(1)$, we can get some partial results :

• For prime $N$ such that $N\equiv 2\pmod 3$ and $N\equiv 3,5,6\pmod 7$, we can take $F_5=5$ since $$\small 2S_{m-2}^2\equiv 7\cdot 7^{(N-1)/2}-3\cdot 3^{(N-1)/2}+4\equiv 7\cdot (-1)-3\cdot (-1)+4\equiv 0\implies S_{m-2}\equiv 0\pmod N$$

• For prime $N$ such that $N\equiv 2\pmod 3$ and $N\equiv 2,3\pmod 5$, we can take $F_6=8$ since $$\begin{align}2S_{m-2}^2&\equiv 10\cdot 2^{(N-1)/2}\cdot 5^{(N-1)/2}-6\cdot 2^{(N-1)/2}\cdot 3^{(N-1)/2}+4\\&\equiv 10\cdot 1\cdot (-1)-6\cdot 1\cdot (-1)+4\\&\equiv 0\pmod N\end{align}$$

• For prime $N$ such that $N\equiv 2,6,7,8,10\pmod{11}$ and $N\equiv 2,3,5,7,8,11,12,13,14\pmod{15}$, we can take $F_7=13$ since $$\small 2S_{m-2}^2\equiv 15\cdot 15^{(N-1)/2}-11\cdot 11^{(N-1)/2}+4\equiv 15\cdot (-1)-11\cdot (-1)+4\equiv 0\pmod N$$

• For prime $N$ such that $N\equiv 2,3,8,10,12,13,14,15,18\pmod{19}$ and $N\equiv 5,7,10,11,14,15,17,19,20,21,22\pmod{23}$, we can take $F_8=21$ since $$\small 2S_{m-2}^2\equiv 23\cdot 23^{(N-1)/2}-19\cdot 19^{(N-1)/2}+4\equiv 23\cdot (-1)-19\cdot (-1)+4\equiv 0\pmod N$$

In the following, let us prove $(1)$.

First of all, we prove by induction that $$S_i=\alpha_n^{2^ik}+\beta_n^{2^ik}\tag2$$ where$$\alpha_n=\frac{F_n-\sqrt{F_n^2-4}}{2},\quad\beta_n=\frac{F_n+\sqrt{F_n^2-4}}{2}$$ satisfying $\alpha_n+\beta_n=F_n$ and $\alpha_n\beta_n=1$.

$$S_0=P_k(F_n)=2^{-k}\cdot \left(\left(F_n-\sqrt{F_n^2-4}\right)^{k}+\left(F_n+\sqrt{F_n^2-4}\right)^{k}\right)=\alpha_n^{2^0k}+\beta_n^{2^0k}$$

Supposing that $(2)$ holds for $i$ gives $$S_{i+1}=S_i^2-2=(\alpha_n^{2^ik}+\beta_n^{2^ik})^2-2=\alpha_n^{2^{i+1}k}+\beta_n^{2^{i+1}k}\qquad\blacksquare$$

Now, from $(2)$, we have $$S_{m-2}=\alpha_n^{2^{m-2}k}+\beta_n^{2^{m-2}k}=\alpha_n^{(N-1)/4}+\beta_n^{(N-1)/4}$$

By the way, since $$\small\left(\frac{F_n\pm\sqrt{F_n^2-4}}{2}\right)^{1/2}=\left(\frac{2F_n\pm2\sqrt{F_n^2-4}}{4}\right)^{1/2}=\left(\frac{(\sqrt{F_n+2}\pm\sqrt{F_n-2})^2}{4}\right)^{1/2}=\frac{\sqrt{F_n+2}\pm\sqrt{F_n-2}}{2}$$ we have $$\small S_{m-2}=\alpha_n^{(N-1)/4}+\beta_n^{(N-1)/4}=\left(\frac{\sqrt{F_n+2}-\sqrt{F_n-2}}{2}\right)^{(N-1)/2}+\left(\frac{\sqrt{F_n+2}+\sqrt{F_n-2}}{2}\right)^{(N-1)/2}$$ Squaring the both sides gives $$S_{m-2}^2=\left(\frac{\sqrt{F_n+2}-\sqrt{F_n-2}}{2}\right)^{N-1}+\left(\frac{\sqrt{F_n+2}+\sqrt{F_n-2}}{2}\right)^{N-1}+2$$ Multiplying the both sides by $2^{N-1}$, $$2^{N-1}\cdot S_{m-2}^2=(\sqrt{F_n+2}-\sqrt{F_n-2})^{N-1}+(\sqrt{F_n+2}+\sqrt{F_n-2})^{N-1}+2^N$$ Multiplying the both sides by $4=(\sqrt{F_n+2}-\sqrt{F_n-2})(\sqrt{F_n+2}+\sqrt{F_n-2})$, $$\begin{align}&2^{N+1}\cdot S_{m-2}^2\\\\&=(\sqrt{F_n+2}+\sqrt{F_n-2})(\sqrt{F_n+2}-\sqrt{F_n-2})^N\\&\qquad\qquad\qquad +(\sqrt{F_n+2}-\sqrt{F_n-2})(\sqrt{F_n+2}+\sqrt{F_n-2})^N+2^{N+2}\\\\&=\sqrt{F_n+2}\ ((\sqrt{F_n+2}-\sqrt{F_n-2})^N+(\sqrt{F_n+2}+\sqrt{F_n-2})^N)\\&\qquad\qquad\qquad +\sqrt{F_n-2}\ ((\sqrt{F_n+2}-\sqrt{F_n-2})^N-(\sqrt{F_n+2}+\sqrt{F_n-2})^N)+2^{N+2}\tag3\end{align}$$

Using the binomial theorem, $$\begin{align}&\sqrt{F_n+2}\ ((\sqrt{F_n+2}-\sqrt{F_n-2})^N+(\sqrt{F_n+2}+\sqrt{F_n-2})^N)\\\\&=\sqrt{F_n+2}\ \sum_{i=0}^{N}\binom Ni(\sqrt{F_n+2})^i((-\sqrt{F_n-2})^{N-i}+(\sqrt{F_n-2})^{N-i})\\\\&=\sum_{j=1}^{(N+1)/2}\binom{N}{2j-1}(\sqrt{F_n+2})^{2j}\cdot 2(\sqrt{F_n-2})^{N-(2j-1)}\\\\&\equiv 2(F_n+2)^{(N+1)/2}\quad\pmod N\tag4\end{align}$$ where we use that $\binom Nr\equiv 0\pmod N$ for $1\le r\le N-1$.

Similarly, $$\begin{align}&\sqrt{F_n-2}\ ((\sqrt{F_n+2}-\sqrt{F_n-2})^N-(\sqrt{F_n+2}+\sqrt{F_n-2})^N)\\\\&=\sqrt{F_n-2}\ \sum_{i=0}^{N}\binom Ni(\sqrt{F_n+2})^i((-\sqrt{F_n-2})^{N-i}-(\sqrt{F_n-2})^{N-i})\\\\&=-\sum_{j=0}^{(N-1)/2}\binom{N}{2j}(\sqrt{F_n+2})^{2j}\cdot 2(\sqrt{F_n-2})^{N-2j+1}\\\\&\equiv -2(F_n-2)^{(N+1)/2}\quad\pmod N\tag5\end{align}$$

Now, it follows from $(3)(4)(5)$ that $$2^{N+1}\cdot S_{m-2}^2\equiv 2(F_n+2)^{(N+1)/2}-2(F_n-2)^{(N+1)/2}+2^{N+2}\pmod N$$ from which $(1)$ follows since $2^N\equiv 2\pmod N$. $\quad\blacksquare$