Effective primality tests for some integers of the forms 𝐴5ⁿ-1 and 𝐴7ⁿ-1

Williams, H. C.

doi:10.1090/S0025-5718-1987-0866123-X

Effective primality tests for some integers of the forms $A5\sp n-1$ and $A7\sp n-1$

Author: H. C. Williams
Journal: Math. Comp. 48 (1987), 385-403
MSC: Primary 11Y11; Secondary 11A51
DOI: https://doi.org/10.1090/S0025-5718-1987-0866123-X
MathSciNet review: 866123
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown how polynomial time prime tests, which are both fast and deterministic, can be developed for many numbers of the form $A{r^n} - 1\;(r = 5,7;A < {r^n})$ . These tests, like the Lucas-Lehmer test for the primality of the Mersenne numbers, are derived by using the properties of the Lucas functions. We exemplify these ideas by using numbers of the form $2 \cdot {10^n} - 1$ .

[1] C. Cailler, "Sur les congruences du troisième degrée," Enseign. Math., v. 10, 1908, pp. 474-487.
[2] L. Carlitz and H. H. Ferns, Some Fibonacci and Lucas identities, Fibonacci Quart. 8 (1970), no. 1, 61–73. MR 263733
[3] L. E. Dickson, History of the Theory of Numbers, Vol. 1, Chelsea, New York, 1952.
[4] John H. Halton, On a general Fibonacci identity, Fibonacci Quart. 3 (1965), 31–43. MR 186613
[5] K. Inkeri, Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I No. 279 (1960), 19. MR 0117202
[6] Dov Jarden, Recurring sequences: A collection of papers, Second edition. Revised and enlarged, including numerous new factorizations of Fibonacci and Lucas numbers by John Brillhart, Riveon Lematematika, Jerusalem (Israel), 1966. MR 0197383
[7] 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
[8] D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. Amer. (distributed by Prentice-Hall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR 0246815
[9] Emma Lehmer and H. S. Vandiver, On the computation of the number of solutions of certain trinomial congruences, J. Assoc. Comput. Mach. 4 (1957), 505–510. MR 93908, https://doi.org/10.1145/320893.320906
[10] 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
[11] 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
[12] H. C. Williams, An algorithm for determining certain large primes, Proceedings Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971) Louisiana State Univ., Baton Rouge, La., 1971, pp. 533–556. MR 0319874
[13] H. C. Williams, The primality of 𝑁=2𝐴3ⁿ-1, Canad. Math. Bull. 15 (1972), 585–589. MR 311559, https://doi.org/10.4153/CMB-1972-101-7
[14] H. C. Williams, Some properties of a special set of recurring sequences, Pacific J. Math. 77 (1978), no. 1, 273–285. MR 507635
[15] H. C. Williams, The primality of certain integers of the form 2𝐴𝑟ⁿ-1, Acta Arith. 39 (1981), no. 1, 7–17. MR 638738, https://doi.org/10.4064/aa-39-1-7-17
[16] H. C. Williams, A class of primality tests for trinomials which includes the Lucas-Lehmer test, Pacific J. Math. 98 (1982), no. 2, 477–494. MR 650024
[17] C. R. Zarnke & H. C. Williams, "Computer determination of some large primes," Congressus Numerantium III, Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing, Utilitas Math., Winnipeg, 1971, pp. 563-570.