Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Author: A. Rotkiewicz
Journal: Math. Comp. 39 (1982), 239-247
MSC: Primary 10A05; Secondary 10A35
MathSciNet review: 658229
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A05, 10A35

Retrieve articles in all journals with MSC: 10A05, 10A35

Additional Information

Keywords: Pseudoprime, Lucas sequence, Lucas pseudoprime, Lehmer numbers, Lehmer sequence, strong pseudoprime, Euler pseudoprime, Euler Lehmer pseudoprime, strong Lehmer pseudoprime, primality testing
Article copyright: © Copyright 1982 American Mathematical Society