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

for sequences R for which D = A

2 -4B>0 but D is not a perfect square. This lower bound was extended by P. Kiss (Ann. Univ. Sei. Budapest, Sect Math. 28,1986, 153—159) to all non-degenerate Lucas sequences R. Very recently P. Erdős, P. Kiss and A. Sárközy (Math. Comp. 51, 1988, 315—323) improved the lower bound for J?%R, x) extending Pomerance's result for Lucas pseudoprimes. They showed that there is a positive constant C

5 such that for all large x S%R,x) > exp {(logjef

3} for any non-degenerate Lucas sequence R. In the proof of this result they showed only the existence of the constant C

5 and they noted that it would be interesting to get a reasonable numerical estimate for this constant By using some results of Selberg's sieve and a new idea concerning some congruences of Lehmer sequences, in [10] we extended the above result of Pomerance, Erdős, Kiss and Sárközy for Lehmer pseudoprimes, furthermore we gave a numerical value for C

5

. Theorem 2.12. ([10]) Let U = U(L,M) be a non degenerate Lehmer sequence and let 3%U,x) denote the number of all Lehmer pseudoprimes with parameters L and M not exceeding x

. Then for all large x we have &(U

tx) >exp{(logx)

1/3

5} and (U, x)< X' exp{-log x • log log log x ! 2 log 138