# 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)

##### MSC:
 11A07 Congruences; primitive roots; residue systems 11B39 Fibonacci and Lucas numbers and polynomials and generalizations
##### Keywords:
pseudoprime; strong Lucas pseudoprime; Lucas sequences