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

IL PSEUDOPRIMES A problem, commonly attributed to the ancient Chinese, was to ascertain whether a natural number n must be a prime if it satisfies the congruence The question remained open until 1819, when Sarrus showed that 2

34

1 = 2 (mod 341), yet 341=11.31 is a composite number. In particular, a crude converse of Fermafs little theorem is false. In 1904, M. Cipolla (Annali di Matematica 9, 1904, 139—160) proved that there are infinitely many composite natural numbers n which satisfy the congruence Let c > 1 be an integer. A composite natural n is called pseudoprime to base c > 1 if If a composite natural n with (n,c) = 1 and satisfies the congruence (2.1) 2" =2 (mod«). (2-1). (2.2) c" = c (mod«). (2.3) c

("1)/

2 s(c/«) (mod»), 126