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

then n is called an Euler-pseudoprime to base c, where {cIn) denotes the Jacobi symbol. We simply say n is a pseudoprime (or an Euler-pseudoprime) if it is one to base 2. The properties of pseudoprimes and their generalizations have been studied intensively, since they can be used for primality tests. For results and problems concerning pseudoprimes and their generalizations we refer to the works by A. Rotkiewicz (Pseudoprime numbers and their generalizations, Univ. of Novi Sad, 1972), E. Lieuwens (.Termát pseudoprimes, Doctor thesis, Delft, 1971), C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr. (The pseudoprimes to 25.1CP, Math. Comp. 35, 1980, 1003—1026), further to the references there. II. 1. Lucas and Lehmer pseudoprimes Let R = R(A

yB) be a Lucas sequence defined by integers RQ = 0, R

x = 1, A and B. Let D = A

2 -4B * 0, and we assume that the sequence R is non-degenerate. Let S = S(A,B) be the sequence G(2,A,A,B), that is S

0 = 2, S

} = A and S

n+

] - AS

n - BS

n_

x (n > 0). For odd primes n with (n,D

) = 1, as it is well-known, we have (2.4) (2.5) (2.6) Rn-(D/n) — 0 X. HD In) S

n = S j (mod«), (mod n)

y (mod«) and for odd prime n with (n,BD

) = 1 127