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

BUI MINH PHONG Eötvös Loránd University, Computer Center RECURRENCE SEQUENCES AND PSEUDOPRIMES ABSTRACT: In this paper we will present a summary of the most improtant results on recurrence sequences and pseudoprimes which we have discovered between 1974—1988. L RECURRENCE SEQUENCES Let G = G(G

0,GJ,4,2?) = {G,

i}"

=

0 be a second order linear recurrence defined by integer constans G

0,G

{,A,B and the recurrence (1.1) G

n = AG

n_

x-BG

n_

2 (n> 1), where AB *0,D = A

2-4B*0 and |G

0|+|G,|*0. Let y and S be the roots of the characteristic polynomial x

2 - Ax+B - 0. The sequence G(G

0,G

1,y4,

Jß) is called non-degenerate if y 1

5 is not a root of unity. If G

0 = 0 and G

{ - 1, then we denote the sequence G(0,l,A,B) by R-R{A,B). The sequence R is called Lucas sequence and R

n is called a Lucas number. In ill