Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Factors of Fermat numbers and large primes of the form $ k\cdot 2\sp{n}+1$


Author: Wilfrid Keller
Journal: Math. Comp. 41 (1983), 661-673
MSC: Primary 11Y05; Secondary 11A41, 11Y11
DOI: https://doi.org/10.1090/S0025-5718-1983-0717710-7
MathSciNet review: 717710
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new factor is given for each of the Fermat numbers $ {F_{52}},{F_{931}},{F_{6835}}$, and $ {F_{9448}}$. In addition, a factor of $ {F_{75}}$ discovered by Gary Gostin is presented. The current status for all $ {F_m}$ is shown in a table. Primes of the form $ k \cdot {2^n} + 1,k$ odd, are listed for $ 31 \leqslant k \leqslant 149$, $ 1500 < n \leqslant 4000$, and for $ 151 \leqslant k \leqslant 199$, $ 1000 < n \leqslant 4000$. Some primes for even larger values of n are included, the largest one being $ 5 \cdot {2^{13165}} + 1$. Also, a survey of several related questions is given. In particular, values of k such that $ k\cdot{2^n} + 1$ is composite for every n are considered, as well as odd values of h such that $ 3h\cdot{2^n} \pm 1$ never yields a twin prime pair.


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

  • [1] A. O. L. Atkin & N. W. Rickert, "On a larger pair of twin primes," Notices Amer. Math. Soc., v. 26, 1979, p. A-373.
  • [2] A. O. L. Atkin & N. W. Rickert, "Some factors of Fermat numbers," Abstracts Amer. Math. Soc., v. 1, 1980, p. 211.
  • [3] Robert Baillie, "New primes of the form $ k\cdot{2^n} + 1$," Math. Comp., v. 33, 1979, pp. 1333-1336. MR 80h: 10009. Table errata: MTE 585, Math. Comp., v. 38, 1982, p. 335. MR 82m: 10013. MR 537979 (80h:10009)
  • [4] Robert Baillie, G. Cormack & H. C. Williams, "The problem of Sierpiński concerning $ k\cdot{2^n} + 1$," Math. Comp., v. 37, 1981, pp. 229-231. MR 83a: 10006a. Corrigenda: Math. Comp., v. 39, 1982, p. 308. MR 83a: 10006b. MR 616376 (83a:10006a)
  • [5] Richard P. Brent, "Succinct proofs of primality for the factors of some Fermat numbers," Math. Comp., v. 38, 1982, pp. 253-255. MR 82k: 10002. MR 637304 (82k:10002)
  • [6] Richard P. Brent & John M. Pollard, "Factorization of the eighth Fermat number," Math. Comp., v. 36, 1981, pp. 627-630. MR 606520 (83h:10014)
  • [7] Ingo Büchel & Wilfrid Keller, Ein Programmsystem für Rationale Arithmetik: Einführung und Beispielsammlung, Bericht Nr. 8004, Rechenzentrum der Universität Hamburg, April 1980.
  • [8] G. V. Cormack & H. C. Williams, "Some very large primes of the form $ k\cdot{2^m} + 1$" Math. Comp., v. 35, 1980, pp. 1419-1421. MR 81i: 10011. Table Errata: MTE 586, Math. Comp., v. 38, 1982, p. 335. MR 82k: 10011. MR 583519 (81i:10011)
  • [9] Martin Gardner, "Mathematical games: Gauss's congruence theory was mod as early as 1801," Scientific American, v. 244, #2, February 1981, pp. 14-19.
  • [10] Gary B. Gostin & Philip B. McLaughlin, Jr., "Six new factors of Fermat numbers," Math. Comp., v. 38, 1982, pp. 645-649. MR 645680 (83c:10003)
  • [11] Richard K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, New York, 1981. MR 656313 (83k:10002)
  • [12] John C. Hallyburton, Jr & John Brillhart, "Two new factors of Fermat numbers," Math. Comp., v. 29, 1975, pp. 109-112. MR 51 #5460. Corrigendum: Math. Comp., v. 30, 1976, p. 198. MR 52 #13599. MR 0369225 (51:5460)
  • [13] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, Oxford, 1979. MR 568909 (81i:10002)
  • [14] G. Jaeschke, "On the smallest k such that all $ k\cdot{2^n} + 1$ are composite," Math. Comp., v. 40, 1983, pp. 381-384. MR 679453 (84k:10006)
  • [15] Donald E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [16] D. H. Lehmer, "On Fermat's quotient, base two," Math. Comp., v. 36, 1981, pp. 289-290. MR 595064 (82e:10004)
  • [17] G. Matthew & H. C. Williams, "Some new primes of the form $ k\cdot{2^n} + 1$," Math. Comp., v. 31, 1977, pp. 797-798. MR 55 #12605. MR 0439719 (55:12605)
  • [18] Michael A. Morrison & John Brillhart, "A method of factoring and the factorization of $ {F_7}$," Math. Comp., v. 29, 1975, pp. 183-205. MR 51 #8017. MR 0371800 (51:8017)
  • [19] P. Ribenboim, "On the square factors of the numbers of Fermat and Ferentinou-Nicolacopoulou," Bull. Soc. Math. Grèce (N. S.), v. 20, 1979, pp. 81-92. MR 642432 (83f:10016)
  • [20] Raphael M. Robinson, "A report on primes of the form $ k\cdot{2^n} + 1$ and on factors of Fermat numbers," Proc. Amer. Math. Soc., v. 9, 1958, pp. 673-681. MR 20 #3097. MR 0096614 (20:3097)
  • [21] W. Sierpiński, "Sur un problème concernant les nombres $ k\cdot{2^n} + 1$," Elem. Math., v. 15, 1960, pp. 73-74. MR 22 #7983. Corrigendum: Elem. Math., v. 17, 1962, p. 85. MR 0117201 (22:7983)
  • [22] R. G. Stanton, "Further results on covering integers of the form $ 1 + k{2^n}$ by primes," Lecture Notes in Math., Vol. 884: Combinatorial Mathematics VIII, Springer-Verlag, Berlin and Heidelberg, 1981, pp. 107-114. MR 641240 (84j:10009)
  • [23] Hiromi Suyama, "Searching for prime factors of Fermat numbers with a microcomputer," bit, v. 13, 1981, pp. 240-245. (Japanese) MR 82c: 10012. MR 610300 (82c:10012)
  • [24] H. C. Williams, "Primality testing on a computer," Ars Combin., v. 5, 1978, pp. 127-185. MR 80d: 10002. MR 504864 (80d:10002)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 11A41, 11Y11

Retrieve articles in all journals with MSC: 11Y05, 11A41, 11Y11


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1983-0717710-7
Keywords: Fermat numbers, numbers of Ferentinou-Nicolacopoulou, factoring, trial division, large primes, covering set of divisors, twin primes
Article copyright: © Copyright 1983 American Mathematical Society

American Mathematical Society