Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Lucasian criteria for the primality of $ N=h\cdot 2\sp{n} -1$


Author: Hans Riesel
Journal: Math. Comp. 23 (1969), 869-875
MSC: Primary 10.08
DOI: https://doi.org/10.1090/S0025-5718-1969-0262163-1
MathSciNet review: 0262163
Full-text PDF

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.


References [Enhancements On Off] (What's this?)

  • [1] E. L. Ince, Cycles of Reduced Ideals in Quadratic Fields, British Association for the Advancement of Science, London, 1934.
  • [2] D. H. Lehmer, ``An extended theory of Lucas' functions,'' Ann. of Math., v. 31, 1930, pp. 419-448.
  • [3] E. Lucas, ``Théorie des fonctions numériques simplement périodiques,'' Amer. J. Math., v. 1, 1878, pp. 184-239, pp. 289-321. MR 1505164
  • [4] H. Riesel, ``A note on the prime numbers of the forms $ N = (6a + 1){2^{2n - 1}} - 1$ and $ M = (6a - 1){2^{2n}} - 1$,'' Ark. Mat., v. 3, 1956, pp. 245-253. MR 17, 945. MR 0076793 (17:945d)
  • [5] H. C. Williams & C. R. Zarnke, ``A report on prime numbers of the forms $ M = (6a + 1){2^{2m - 1}} - 1$ and $ M' = (6a - 1){2^{2m}} - 1$,'' Math. Comp., v. 22, 1968, pp. 420-422. MR 37 #2680. MR 0227095 (37:2680)
  • [6] R. M. Robinson, ``A report on primes of the form $ k \cdot {2^n} + 1$ and on factors of Fermat numbers,'' Proc. Amer. Math. Soc., v. 9, 1958, pp. 673-681. MR 20 #3097. MR 0096614 (20:3097)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10.08

Retrieve articles in all journals with MSC: 10.08


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1969-0262163-1
Article copyright: © Copyright 1969 American Mathematical Society

American Mathematical Society