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} \text{ with } n \equiv 0 \pmod{4} \\ k \equiv 11,23 \pmod{30} \text{ with } n \equiv 1 \pmod{4} \\ k \equiv 13,19 \pmod{30} \text{ with } n \equiv 2 \pmod{4} \\ k \equiv 17,29 \pmod{30} \text{ 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.


2 Answers 2


Your criterion is equivalent to:

$$(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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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