Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

A lower bound for the counting function of Lucas pseudoprimes


Authors: P. Erdős, P. Kiss and A. Sárközy
Journal: Math. Comp. 51 (1988), 315-323
MSC: Primary 11B39; Secondary 11Y55
DOI: https://doi.org/10.1090/S0025-5718-1988-0942158-4
MathSciNet review: 942158
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that there is an absolute constant c such that, for any nondegenerate Lucas sequence, the number of Lucas pseudoprimes not exceeding x is greater than $ \exp \{ {(\log x)^c}\} $ if x is sufficiently large.


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

  • [1] R. Baillie & S. S. Wagstaff, Jr., "Lucas pseudoprimes," Math. Comp., v. 35, 1980, pp. 1391-1417. MR 583518 (81j:10005)
  • [2] P. Erdős, "On pseudoprimes and Carmichael numbers," Publ. Math. Debrecen, v. 4, 1956, pp. 201-206. MR 0079031 (18:18e)
  • [3] E. Fouvry & F. Grupp, "On the switching principle in sieve theory," J. Reine Angew. Math., v. 370, 1986, pp. 101-126. MR 852513 (87j:11092)
  • [4] S. Graham, "On Linnik's constant," Acta Arith., v. 39, 1981, pp. 163-179. MR 639625 (83d:10050)
  • [5] H. Halberstam & H.-E. Richert, Sieve Methods, Academic Press, London, 1974. MR 0424730 (54:12689)
  • [6] P. Kiss, "Some results on Lucas pseudoprimes," Ann. Univ. Sci. Budapest. Sect. Math., v. 28, 1986, pp. 153-159. MR 856986 (87m:11015)
  • [7] D. H. Lehmer, "An extended theory of Lucas' functions," Ann. of Math., v. 31, 1930, pp. 419-448. MR 1502953
  • [8] D. H. Lehmer, "On the converse of Fermat's theorem," Amer. Math. Monthly, v. 43, 1936, pp. 347-354. MR 1523680
  • [9] C. Pomerance, "A new lower bound for the pseudoprime counting function," Illinois J. Math., v. 26, 1982, pp. 4-9. MR 638549 (83h:10012)
  • [10] C. Pomerance, "On the distribution of pseudoprimes," Math. Comp., v. 37, 1981, pp. 587-593. MR 628717 (83k:10009)
  • [11] C. Pomerance, "Popular values of Euler's function," Mathematika, v. 27, 1980, pp. 84-89. MR 581999 (81k:10076)
  • [12] K. Prachar, Primzahlverteilung, Springer-Verlag, Berlin and New York, 1957. MR 0087685 (19:393b)
  • [13] A. Schinzel, "Primitive divisors of the expression $ {A^n} - {B^n}$ in algebraic number fields," J. Reine Angew. Math., v. 268/269, 1974, pp. 27-33. MR 0344221 (49:8961)
  • [14] C. L. Stewart, "Primitive divisors of Lucas and Lehmer numbers," Transcendence Theory: Advances and Applications (A. Baker and D. W. Masser, eds.), Academic Press, London and New York, 1977, pp. 79-92. MR 0476628 (57:16187)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11B39, 11Y55

Retrieve articles in all journals with MSC: 11B39, 11Y55


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1988-0942158-4
Keywords: Pseudoprime, Lucas sequence, Lucas pseudoprimes
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society