A lower bound for the counting function of Lucas pseudoprimes

Erdős, P.; Kiss, P.; Sárközy, A.

doi:10.1090/S0025-5718-1988-0942158-4

A lower bound for the counting function of Lucas pseudoprimes
HTML articles powered by AMS MathViewer

by P. Erdős, P. Kiss and A. Sárközy PDF

Math. Comp. 51 (1988), 315-323 Request permission

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

Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 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 10.4064/aa-39-2-163-179
H. Halberstam and H.-E. Richert, Sieve methods, London Mathematical Society Monographs, No. 4, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974. 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 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 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 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 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 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