zbMATH — the first resource for mathematics

On Lucas pseudoprimes with a prescribed value of the Jacobi symbol. (English) Zbl 0951.11002
Let \(P, Q\) be rational integers, \(D= P^2- 4Q\) and define Lucas sequences \(U_n, V_n\) with parameters \(P\) and \(Q\) by \(U_0= 0\), \(U_1= 1\), \(U_n= PU_{n-1}- QU_{n-2}\) and \(V_0=2\), \(V_1= P\), \(V_n= PV_{n-1}- QV_{n-2}\), respectively. A composite \(n\) is called a strong Lucas pseudoprime with parameters \(P\) and \(Q\) if \((n,2QD)=1\), \(n- (D/n)= 2^sr\), \(r\) odd and either \(U_r\equiv 0\pmod n\) or \(V_{2^tr}\equiv 0\pmod n\) for some \(t\), where \(0\leq t< s\) and \((D/n)\) is the Jacobi symbol.
In the paper the following theorem is proved: “Given integers \(P,Q\) with \(D= P^2- 4Q\neq 0\), \(-Q\), \(-2Q\), \(-3Q\) and \(\varepsilon= \pm 1\), every arithmetic progression \(ax+b\), where \((a,b)= 1\) which contains an odd integer \(n_0\) with \((D/n_0)= \varepsilon\) contains infinitely many strong Lucas pseudoprimes \(n\) with parameters \(P\) and \(Q\) such that \((D/n)= \varepsilon\). The number \(N(X)\) of such strong pseudoprimes not exceeding \(X\) satisfies \[ N(X)> c(P,Q,a,b, \varepsilon) \frac{\log X}{\log\log X}, \] where \(c(P,Q,a,b, \varepsilon)\) is a positive constant depending on \(P,Q,a,b, \varepsilon\).” This result answers a question of C. Pomerance and completes some earlier results.
Reviewer: Peter Kiss (Eger)

11A07 Congruences; primitive roots; residue systems
11B39 Fibonacci and Lucas numbers and polynomials and generalizations