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 if *x* is sufficiently large.

**[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 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)**

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