Lucas's criterion for the primality of numbers of the form $N=h2^n-1$

S. B. Stechkin

Matematičeskie zametki, Tome 10 (1971) no. 3, pp. 259-268

Résumé

The following theorem is proved. Let $N=h2^n-1$, where $n\geqslant2$, $h$ is odd, $1\leqslant h<2^n$, and suppose that $v$ is a positive integer, $v\geqslant3$, $\alpha$ is a root of the equation $$ (v^2-4, N)=1,\qquad \left(\frac{v-2}N\right)=1, \qquad \left(\frac{v+2}N\right)=-1. $$ Then for $N$ to be prime, it is necessary and sufficient that $$ S_{n-2}\equiv\pmod{N}, \text{ where }S_{k+1}=S_k^2-2\quad(k=0,1,\dots),\quad S_0=\alpha^h+\alpha^{-h}. $$ For given $N$, an algorithm is described for the construction of the smallest $v$ satisfying the conditions of this theorem.