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 Free Access

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.

- Robert Baillie and Samuel S. Wagstaff Jr.,
*Lucas pseudoprimes*, Math. Comp.**35**(1980), no. 152, 1391–1417. MR**583518**, DOI https://doi.org/10.1090/S0025-5718-1980-0583518-6 - P. Erdös,
*On pseudoprimes and Carmichael numbers*, Publ. Math. Debrecen**4**(1956), 201–206. MR**79031** - É. Fouvry and F. Grupp,
*On the switching principle in sieve theory*, J. Reine Angew. Math.**370**(1986), 101–126. MR**852513** - S. Graham,
*On Linnik’s constant*, Acta Arith.**39**(1981), no. 2, 163–179. MR**639625**, DOI https://doi.org/10.4064/aa-39-2-163-179 - H. Halberstam and H.-E. Richert,
*Sieve methods*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1974. London Mathematical Society Monographs, No. 4. MR**0424730** - Péter Kiss,
*Some results on Lucas pseudoprimes*, Ann. Univ. Sci. Budapest. Eötvös Sect. Math.**28**(1985), 153–159 (1986). MR**856986** - D. H. Lehmer,
*An extended theory of Lucas’ functions*, Ann. of Math. (2)**31**(1930), no. 3, 419–448. MR**1502953**, DOI https://doi.org/10.2307/1968235 - D. H. Lehmer,
*On the Converse of Fermat’s Theorem*, Amer. Math. Monthly**43**(1936), no. 6, 347–354. MR**1523680**, DOI https://doi.org/10.2307/2301798 - Carl Pomerance,
*A new lower bound for the pseudoprime counting function*, Illinois J. Math.**26**(1982), no. 1, 4–9. MR**638549** - Carl Pomerance,
*On the distribution of pseudoprimes*, Math. Comp.**37**(1981), no. 156, 587–593. MR**628717**, DOI https://doi.org/10.1090/S0025-5718-1981-0628717-0 - Carl Pomerance,
*Popular values of Euler’s function*, Mathematika**27**(1980), no. 1, 84–89. MR**581999**, DOI https://doi.org/10.1112/S0025579300009967 - Karl Prachar,
*Primzahlverteilung*, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR**0087685** - A. Schinzel,
*Primitive divisors of the expression $A^{n}-B^{n}$ in algebraic number fields*, J. Reine Angew. Math.**268(269)**(1974), 27–33. MR**344221**, DOI https://doi.org/10.1515/crll.1974.268-269.27 - C. L. Stewart,
*Primitive divisors of Lucas and Lehmer numbers*, Transcendence theory: advances and applications (Proc. Conf., Univ. Cambridge, Cambridge, 1976) Academic Press, London, 1977, pp. 79–92. MR**0476628**

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

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

Additional Information

Keywords:
Pseudoprime,
Lucas sequence,
Lucas pseudoprimes

Article copyright:
© Copyright 1988
American Mathematical Society