# Primality test for specific class of Proth numbers

Can you provide a proof or a counterexample for the following claim :

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

Let $N=k\cdot 2^n+1$ such that $n>2$ , $0< k <2^n$ and

$\begin{cases} k \equiv 1,7 \pmod{30} ~ with ~ n \equiv 0 \pmod{4} ~,or \\ k \equiv 11,23 \pmod{30} ~ with ~ n \equiv 1 \pmod{4} ~,or \\ k \equiv 13,19 \pmod{30} ~ with ~ n \equiv 2 \pmod{4} ~,or \\ k \equiv 17,29 \pmod{30} ~ with ~ n \equiv 3 \pmod{4} \end{cases}$

Let $S_i=S_{i-1}^2-2$ with $S_0=P_k(8)$ , then $N$ is prime iff $S_{n-2} \equiv 0 \pmod N$ .

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

Note that for $k=1$ we have Inkeri's primality test for Fermat numbers . Reference : Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I 279 (1960), 1-19.

$$(4+\sqrt{15})^{k2^{n-1}}\equiv (4+\sqrt{15})^{\frac{N-1}{2}}\equiv -1 (\bmod N \mathbb{Z}[\sqrt{15}]).$$

The point is that $P_m(8)=(4+\sqrt{15})^m+(4-\sqrt{15})^m$. Moreover, $S_i=(4+\sqrt{15})^{k2^i}+(4-\sqrt{15})^{k2^i}$, which one may prove by induction, using the fact that $x\mapsto x^2-2$ is semi-conjugate to $z\mapsto z^2$ under the relation $x=z+1/z$. Then the condition $S_{n-2} = (4+\sqrt{15})^{k2^{n-2}}+(4-\sqrt{15})^{k2^{n-2}} \equiv 0 (\bmod N)$ is equivalent to $(4+\sqrt{15})^{k2^{n-1}} \equiv -1 (\bmod N)$.

By Fermat's little theorem (see Theorem 1 of this paper) in the quadratic number field $\mathbb{Q}[\sqrt{15}]$, for any odd prime $p$, one has $(4+\sqrt{15})^{p-\left(\frac{15}{p}\right)}\equiv 1 (\bmod p)$, where $\left(\frac{15}{p}\right)$ is the Legendre symbol (note that $(4+\sqrt{15})(4-\sqrt{15})=1$, so $4+\sqrt{15}$ is a unit in the ring of integers $\mathbb{Z}[\sqrt{15}]$).

One also has by Theorem 2 of this paper that if $l$ is the smallest integer with $(4+\sqrt{15})^l \equiv -1 (\bmod p)$, and $(4+\sqrt{15})^K\equiv -1(\bmod p)$, then $K=lu$, where $u$ is odd. Also, the smallest integer with $(4+\sqrt{15})^e \equiv 1 (\bmod p)$ is $e=2l$.

Now, let's show that your criterion implies that $N$ is prime. For contradiciton, let $p < N$ be a prime factor of $N$, then by your criterion, $(4+\sqrt{15})^{k2^{n-1}}\equiv -1 (\bmod p)$. Then $k2^{n-1} = l u$, where $l$ is the smallest exponent $>0$ with $(4+\sqrt{15})^k\equiv -1(\bmod p)$, and $u$ is an odd integer by Theorem 2. So $l=2^{n-1}\delta$, with $\delta | k$, and hence $e \geq 2^n$.

Theorem 1 implies that $(4+\sqrt{15})^{p\pm 1}\equiv 1(\bmod p)$. Then $p\pm 1\geq 2^n$, for every prime $p | N$. $N$ is not a square from your congruence conditions on $k$ and $n$ (check $(\bmod 15)$), so it has a factorization $pq$ with $p\geq 2^n-1$, $q\geq p+2$. But then $N = p\cdot q \geq p(p+2)\geq (2^n-1)(2^n+1)=2^n\cdot 2^n-1 > k 2^n +1 =N$ since $k < 2^n$, a contradiction.

Going in the reverse direction (following the proof of Theorem 1 of this paper), your congruence conditions imply that $N\equiv 2,8 (\bmod 15)$ and $N\equiv 1(\bmod 8)$, hence $\left(\frac{15}{N}\right)=1, \left(\frac{2}{N}\right)=1,\left(\frac{5}{N}\right)=-1$. We have $(4+\sqrt{15})=\frac{5+\sqrt{15}}{5-\sqrt{15}}$. Hence $$(4+\sqrt{15})^{\frac{N-1}{2}}\equiv -1 (\bmod N)$$ if and only if $$(5+\sqrt{15})^{\frac{N-1}{2}}\equiv - (5-\sqrt{15})^{\frac{N-1}{2}} (\bmod N)$$ if and only if $$(5+\sqrt{15})^{N-1} \equiv - 10^{\frac{N-1}{2}} \equiv - 2^{\frac{N-1}{2}} 5^{\frac{N-1}{2}} \equiv - \left(\frac{2}{N}\right) \left(\frac{5}{N}\right ) \equiv 1 (\bmod N),$$ which holds by Theorem 1 and the properties of Legendre symbols.

This might end up being tautological, but your $S_{n-2} = V_{\frac{N-1}{4}}(8,1)$, where $V_m(P,Q)$ is the Lucas sequence. And so your question can be rephrased as $V_{\frac{N-1}{4}}(8,1) \equiv 0 \pmod{ N}$ iff $N$ is a prime number (where $N=2^nk+1$, etc. etc.). There are plenty of identities to choose from to try to make it work. Maybe have a look in "The Book of Prime Number Records" by Ribenboim.