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

Author:
A. Rotkiewicz

Journal:
Math. Comp. **39** (1982), 239-247

MSC:
Primary 10A05; Secondary 10A35

DOI:
https://doi.org/10.1090/S0025-5718-1982-0658229-0

MathSciNet review:
658229

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let for *n* odd and for even *n*, where and are distinct roots of the trinomial and and *Q* are rational integers. is the *n*th Lehmer number connected with .

Let for *n* odd, and for *n* even denote the *n*th term of the associated recurring sequence. An odd composite number *n* is a *strong Lehmer pseudoprime with parameters L*, *Q* (or ) if , where , and with , *d* odd, where is the Jacobi symbol, we have either or , for some *r* with .

Let . Then every arithmetic progression , 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.

**[1]**Robert Baillie and Samuel S. Wagstaff Jr.,*Lucas pseudoprimes*, Math. Comp.**35**(1980), no. 152, 1391–1417. MR**583518**, https://doi.org/10.1090/S0025-5718-1980-0583518-6**[2]**D. H. Lehmer,*An extended theory of Lucas’ functions*, Ann. of Math. (2)**31**(1930), no. 3, 419–448. MR**1502953**, https://doi.org/10.2307/1968235**[3]**D. H. Lehmer, "On Lucas's test for the primality of Mersenne's numbers,"*J. London Math. Soc.*, v. 10, 1935, pp. 162-165.**[4]**D. H. Lehmer,*Strong Carmichael numbers*, J. Austral. Math. Soc. Ser. A**21**(1976), no. 4, 508–510. MR**417032**, https://doi.org/10.1017/s1446788700019364**[5]**Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr.,*The pseudoprimes to 25⋅10⁹*, Math. Comp.**35**(1980), no. 151, 1003–1026. MR**572872**, https://doi.org/10.1090/S0025-5718-1980-0572872-7**[6]**A. J. van der Poorten and A. Rotkiewicz,*On strong pseudoprimes in arithmetic progressions*, J. Austral. Math. Soc. Ser. A**29**(1980), no. 3, 316–321. MR**569519****[7]**Hans Riesel,*A note on the prime numbers of the forms 𝑁=(6𝑎+1)2²ⁿ⁻¹-1 and 𝑀=(6𝑎-1)2²ⁿ-1*, Ark. Mat.**3**(1956), 245–253. MR**76793**, https://doi.org/10.1007/BF02589411**[8]**Hans Riesel,*Lucasian criteria for the primality of 𝑁=ℎ⋅2ⁿ-1*, Math. Comp.**23**(1969), 869–875. MR**262163**, https://doi.org/10.1090/S0025-5718-1969-0262163-1**[9]**Raphael M. Robinson,*The converse of Fermat’s theorem*, Amer. Math. Monthly**64**(1957), 703–710. MR**98057**, https://doi.org/10.2307/2309747**[10]**André Rotkiewicz,*Sur les nombres pseudopremiers de la forme 𝑎𝑥+𝑏*, C. R. Acad. Sci. Paris**257**(1963), 2601–2604 (French). MR**162757****[11]**A. Rotkiewicz,*On the pseudoprimes of the form 𝑎𝑥+𝑏*, Proc. Cambridge Philos. Soc.**63**(1967), 389–392. MR**209220**, https://doi.org/10.1017/s030500410004130x**[12]**A. Rotkiewicz,*On the pseudoprimes of the form 𝑎𝑥+𝑏 with respect to the sequence of Lehmer*, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.**20**(1972), 349–354 (English, with Russian summary). MR**309843****[13]**A. Schinzel,*On primitive prime factors of Lehmer numbers. III*, Acta Arith.**15**(1968), 49–70. MR**232744**, https://doi.org/10.4064/aa-15-1-49-70**[14]**Morgan Ward,*The intrinsic divisors of Lehmer numbers*, Ann. of Math. (2)**62**(1955), 230–236. MR**71446**, https://doi.org/10.2307/1969677

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1982-0658229-0

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