Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 1993. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 21)

Bui Minh Phong: Recurrence sequences and pseudoprimes

II. 4. The distribution of Lehmer pseudoprimes Let x) be denote the number of pseudoprimes to base c not exceeding x. In the case c- 2 we denote 3\2,x

) by It is known that there exist positive constants C, and C

2 such that for all large x C

x • log x < &%x

) < x • exp[-C

2 (log x log log x)

1/

2}, where the lower and the upper bound is due to D. H. Lehmer (Amer. Math. Monthly 43, 1936, 347—354) and P. Erdős (Publ.Math. Debrecen. 4, 1956, 201—206), respectively. C. Pomerance improved these results showing that for all large x ^(x) > exp{(logx)

5/1

4} and S*(x) < x-exp{-logxlogloglogx/2 1ogx} (see Illinois j. Math. 26, 1982, 4—9 and Math. Comp. 37, 1981, 587—593). Let R = R(A,B) be non-degenerate Lucas sequence. Let 3\R,x) be denote the number of all Lucas pseudoprimes with parameteres A,B not exceeding x. R. Baillie and S. S. Wagstaff, Jr. (Math. Comp. 35.1980,1391—1417) proved that there are positive constants C

3 and C

4 such that for all large x ^(R, x) < x • expL-C

3 (log x log log x)

m } for any sequence R and &(R

9X) > C

4 - log x 137