zbMATH — the first resource for mathematics

Characterizing pseudoprimes for third-order linear recurrences. (English) Zbl 0614.10005
Let \(f(x)=x^ 3-rx^ 2+sx-1=(x-\alpha)(x-\beta)(x-\gamma)\), and denote \(\alpha^ n+\beta^ n+\gamma^ n\) by \(A(n)\). The sextuple \(A(-n-1)\), \(A(-n)\), \(A(-n+1)\), \(A(n-1)\), \(A(n)\), \(A(n+1)\), reduced modulo \(n\), is called the signature of \(n\) and it was shown by the author and D. Shanks [ibid. 39, 255–300 (1982; Zbl 0492.10005)] that all primes, but very few composites (called pseudoprimes) have one of three signatures, depending on how \(f\) splits modulo \(n\).
In the present paper conditions for a composite to be a pseudoprime are given, and used to construct some pseudoprimes. A number of open questions remain, e.g. whether there exists an \(f\) giving an infinity of pseudoprimes, and whether there are pseudoprimes with given types of signature when \(r=0\) and \(s=-1\). There is a discussion of the probability that a randomly chosen \(n\) is a pseudoprime.
Reviewer: H.J.Godwin

11Y11 Primality
11A51 Factorization; primality
11B37 Recurrences
Full Text: DOI