On Euler Lehmer pseudoprimes and strong Lehmer pseudoprimes with parameters $L$, $Q$ in arithmetic progressions

Abstract:

Let ${U_n} = ({\alpha ^n} - {\beta ^n})/(\alpha - \beta )$ for n odd and ${U_n} = ({\alpha ^n} - {\beta ^n})/({\alpha ^2} - {\beta ^2})$ for even n, where $\alpha$ and $\beta$ are distinct roots of the trinomial $f(z) = {z^2} - \sqrt L z + Q$ and $L > 0$ and Q are rational integers. ${U_n}$ is the nth Lehmer number connected with $f(z)$. Let ${V_n} = ({\alpha ^n} + {\beta ^n})/(\alpha + \beta )$ for n odd, and ${V_n} = {\alpha ^n} + {\beta ^n}$ for n even denote the nth term of the associated recurring sequence. An odd composite number n is a strong Lehmer pseudoprime with parameters L, Q (or ${\text {slepsp}}(L,Q)$) if $(n,DQ) = 1$, where $D = L - 4Q \ne 0$, and with $\delta (n) = n - (DL/n) = d \cdot {2^s}$, d odd, where $(DL/n)$ is the Jacobi symbol, we have either ${U_d} \equiv 0 \pmod n$ or ${V_{d \cdot {2^r}}} \equiv 0 \pmod n$, for some r with $0 \leqslant r < s$. Let $D = L - 4Q > 0$. Then every arithmetic progression $ax + b$, where a, b are relatively prime integers, contains an infinite number of odd (composite) strong Lehmer pseudoprimes with parameters L, Q. Some new tests for primality are also given.