12
$\begingroup$

How to prove or disprove the claim given below ?

Let $$P_j(x)=2^{-j}\cdot \left((x-\sqrt{x^2-4})^{j}+(x+\sqrt{x^2-4})^{j}\right),$$ where $j$ and $x$ are nonnegative integers. Let $$N=k \cdot2^m+1$$ with $k$ odd , $0<k<2^m$ and $m>2$. Let $F_n$ be the $n$-th Fibonacci number and let $$S_i=S_{i-1}^2-2, \quad S_0=P_k(F_n),$$ then $N$ is prime iff there exists $F_n$ for which $$S_{m-2} \equiv 0 \pmod N.$$

You can run this test here .

$\endgroup$
  • $\begingroup$ Note that $P_j(x)$ is the unique solution to $P_j(x)=xP_{j-1}(x)-P_{j-2}(x)$ with $P_0(x)=2$ and $P_1(x)=x$. $\endgroup$ – vrugtehagel May 6 '17 at 23:44
  • $\begingroup$ Adapt the Lucas Lehmer test for Mersenne numbers. $\endgroup$ – reuns Aug 18 '17 at 13:27
2
+100
$\begingroup$

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$

$\endgroup$

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.