Lucasian criteria for the primality of $N=h\cdot 2^{n} 1$
Author:
Hans Riesel
Journal:
Math. Comp. 23 (1969), 869875
MSC:
Primary 10.08
DOI:
https://doi.org/10.1090/S00255718196902621631
MathSciNet review:
0262163
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
Abstract: Let $vi = v_{i  1}^2  2$ with ${v_0}$ given. If ${v_{n  2}} \equiv 0(\bmod N)$ is a necessary and sufficient criterion that $N = h \cdot {2^n}  1$ be prime, this is called a Lucasian criterion for the primality of $N$. Many such criteria are known, but the case $h = 3A$ has not been treated in full generality earlier. A theorem is proved that (by aid of computer) enables the effective determination of suitable numbers ${v_0}$ for any given $N$, if $h < {2^n}$. The method is used on all $N$ in the domain $h = 3(6)105,n \leqq 1000$. The Lucasian criteria thus constructed are applied, and all primes $N = h \cdot {2^n}  1$ in the domain are tabulated.

E. L. Ince, Cycles of Reduced Ideals in Quadratic Fields, British Association for the Advancement of Science, London, 1934.
D. H. Lehmer, โAn extended theory of Lucasโ functions,โ Ann. of Math., v. 31, 1930, pp. 419โ448.
 Edouard Lucas, Theorie des Fonctions Numeriques Simplement Periodiques. [Continued], Amer. J. Math. 1 (1878), no. 3, 197โ240 (French). MR 1505164, DOI https://doi.org/10.2307/2369311
 Hans Riesel, A note on the prime numbers of the forms $N=(6a+1)2^{2n1}1$ and $M=(6a1)2^{2n}1$, Ark. Mat. 3 (1956), 245โ253. MR 76793, DOI https://doi.org/10.1007/BF02589411
 H. C. Williams and C. R. Zarnke, A report on prime numbers of the forms $M=(6a+1)2^{2m1}1$ and $M^{\prime } =(6a1)2^{2m}1$, Math. Comp. 22 (1968), 420โ422. MR 227095, DOI https://doi.org/10.1090/S00255718196802270952
 Raphael M. Robinson, A report on primes of the form $k\cdot 2^{n}+1$ and on factors of Fermat numbers, Proc. Amer. Math. Soc. 9 (1958), 673โ681. MR 96614, DOI https://doi.org/10.1090/S00029939195800966147
Retrieve articles in Mathematics of Computation with MSC: 10.08
Retrieve articles in all journals with MSC: 10.08
Additional Information
Article copyright:
© Copyright 1969
American Mathematical Society