On Euler Lehmer pseudoprimes and strong Lehmer pseudoprimes with parameters $L$, $Q$ in arithmetic progressions
HTML articles powered by AMS MathViewer
- by A. Rotkiewicz PDF
- Math. Comp. 39 (1982), 239-247 Request permission
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
- Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
- D. H. Lehmer, An extended theory of Lucas’ functions, Ann. of Math. (2) 31 (1930), no. 3, 419–448. MR 1502953, DOI 10.2307/1968235 D. H. Lehmer, "On Lucas’s test for the primality of Mersenne’s numbers," J. London Math. Soc., v. 10, 1935, pp. 162-165.
- D. H. Lehmer, Strong Carmichael numbers, J. Austral. Math. Soc. Ser. A 21 (1976), no. 4, 508–510. MR 417032, DOI 10.1017/s1446788700019364
- Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, DOI 10.1090/S0025-5718-1980-0572872-7
- 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, DOI 10.1017/S1446788700021315
- Hans Riesel, A note on the prime numbers of the forms $N=(6a+1)2^{2n-1}-1$ and $M=(6a-1)2^{2n}-1$, Ark. Mat. 3 (1956), 245–253. MR 76793, DOI 10.1007/BF02589411
- Hans Riesel, Lucasian criteria for the primality of $N=h\cdot 2^{n} -1$, Math. Comp. 23 (1969), 869–875. MR 262163, DOI 10.1090/S0025-5718-1969-0262163-1
- Raphael M. Robinson, The converse of Fermat’s theorem, Amer. Math. Monthly 64 (1957), 703–710. MR 98057, DOI 10.2307/2309747
- André Rotkiewicz, Sur les nombres pseudopremiers de la forme $ax+b$, C. R. Acad. Sci. Paris 257 (1963), 2601–2604 (French). MR 162757
- A. Rotkiewicz, On the pseudoprimes of the form $ax+b$, Proc. Cambridge Philos. Soc. 63 (1967), 389–392. MR 209220, DOI 10.1017/s030500410004130x
- A. Rotkiewicz, On the pseudoprimes of the form $ax+b$ 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
- A. Schinzel, On primitive prime factors of Lehmer numbers. III, Acta Arith. 15 (1968), 49–70. MR 232744, DOI 10.4064/aa-15-1-49-70
- Morgan Ward, The intrinsic divisors of Lehmer numbers, Ann. of Math. (2) 62 (1955), 230–236. MR 71446, DOI 10.2307/1969677
Additional Information
- © Copyright 1982 American Mathematical Society
- 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