Lucas pseudoprimes. (Q5933534)

In the paper under review, the author continues his investigation on the occurrence of various kinds of pseudoprimes with respect to a fixed Lucas sequence in arithmetical progressions. Recall that if \(a\) is an integer different from \(0,\pm1\), then a composite integer \(n\) which is coprime to \(a\) is called a base \(a\) pseudoprime if \(a^{n-1}\equiv 1\pmod a\). If \(n\) is odd, composite, and coprime to \(a\), and if \(a^{(n-1)/2}\equiv (a|n)\pmod n\) holds, then \(n\) is called an Euler pseudoprime to base \(a\). The analogous concepts of pseudoprimes with respect to Lucas sequences lead to four types of pseudoprimes. That is, Let \(P\) and \(Q\) be two integers with \(D= P^2-4Q\neq 0\), and let \((U_n)_{n\geq 0}\) and \((V_n)_{n\geq 0}\) be the Lucas sequences of first and second kind, respectively, with parameters \(P\) and \(Q\), and let \(n\) be composite and coprime to \(2QD\). Then, \(n\) is a Lucas pseudoprime, a Dickson pseudoprime, a Lucas pseudoprime of the second kind, or a Dickson pseudoprime of the second kind, according to whether \(n\) satisfies the congruence \(U_{n-(D|n)}\equiv 0\pmod n\), or \(U_n\equiv (D|n)\pmod n\), or \(V_n\equiv P\pmod n\) or \(V_{n-(D|n)}\equiv 2Q^{(1-(D|n))/2}\pmod n\), respectively. The odd composite number \(n\) is an Euler-Lucas pseudoprime if \(U_{(n-(D|n))/2}\equiv 0\pmod n\), when \((Q|n)=1\), or \(V_{(n-(D|n))/2}\equiv 0\pmod n\), when \((Q|n)=-1\).NEWLINENEWLINEThe author's first three theorems point out that some of the above pseudoprimality conditions imply some of the other ones. For example, if \(n\) is coprime to \(P\) and is simultaneously an Euler-Lucas pseudoprime (with parameters \(P\) and \(Q\)) and an Euler pseudoprime to base \(Q\), then \(n\) verifies all four pseudoprimality conditions (Theorem 1). If \(n\) is coprime to \(P\) and is simultaneously an Euler-Lucas pseudoprime and a Dickson pseudoprime (with parameters \(P\) and \(Q\)) then \(n\) is also an Euler pseudoprime to base \(Q\) (Theorem 2), while if \(n\) is square-free and is both a Dickson pseudoprime of the second kind and an Euler pseudoprime to base \(Q\), then \(n\) is a Lucas-Euler pseudoprime (Theorem 3). The proofs of these three theorems are elementary and rely on algebraic manipulations with the two Lucas sequences \((U_n)_{n\geq 0}\) and \((V_n)_{n\geq 0}\) in question.NEWLINENEWLINEFinally, using his Theorem 1, a result of \textit{R. Baillie} and \textit{S. S. Wagstaff jun.} [NEWLINEMath. Comput. 35, 1391--1417 (1980; Zbl 0458.10003)], and a result of the present author with \textit{A. Schinzel} [Bull. Pol. Acad. Sci., Math. 48, No.~1, 77--80 (2000; Zbl 0951.11002)], the author deduces that if \(Q=\pm1\), and for \(\varepsilon\in\{\pm1\}\), every arithmetic progression \(ax+b\) with \(a\) and \(b\) coprime containing an odd integer \(n_0\) with \((D|n_0)= \varepsilon\) contains infinitely many Lucas pseudoprimes \(n\) (in fact, even infinitely many strong Lucas pseudoprimes) satisfying \((D|n)= \varepsilon\) and which also satisfy all four types of pseudoprimality conditions, and, in fact, for a large positive real number \(x\), the number of such \(n\) is \(\gg\log x/\log\log n\), where the constant understood in \(\gg\) is computable and depends on \(a\), \(b\) and \(P\). The notion of a strong Lucas pseudoprime which we do not reproduce here is defined in the paper and it has been investigated by this author in some of his previous work [Math. Comput. 39, 239--247 (1982; Zbl 0492.10002)].