Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Squarefree smooth numbers and Euclidean prime generators


Authors: Andrew R. Booker and Carl Pomerance
Journal: Proc. Amer. Math. Soc. 145 (2017), 5035-5042
MSC (2010): Primary 11A41; Secondary 11A15, 11B25, 11L40
DOI: https://doi.org/10.1090/proc/13576
Published electronically: August 31, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that for each prime $ p>7$, every residue mod $ p$ can be represented by a squarefree number with largest prime factor at most $ p$. We give two applications to recursive prime generators akin to the one Euclid used to prove the infinitude of primes.


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

  • [1] Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173-206. MR 683806, https://doi.org/10.2307/2006975
  • [2] N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65-72. MR 0045159
  • [3] Andrew R. Booker, On Mullin's second sequence of primes, Integers 12 (2012), no. 6, 1167-1177. MR 3011555, https://doi.org/10.1515/integers-2012-0034
  • [4] Andrew R. Booker, A variant of the Euclid-Mullin sequence containing every prime, J. Integer Seq. 19 (2016), no. 6, Article 16.6.4, 6. MR 3546618
  • [5] Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
  • [6] J. Feitsma, Pseudoprimes, http://www.janfeitsma.nl/math/psp2/index.
  • [7] D. A. Frolenkov and K. Soundararajan, A generalization of the Pólya-Vinogradov inequality, Ramanujan J. 31 (2013), no. 3, 271-279. MR 3081668, https://doi.org/10.1007/s11139-012-9462-y
  • [8] Glyn Harman, Integers without large prime factors in short intervals and arithmetic progressions, Acta Arith. 91 (1999), no. 3, 279-289. MR 1735677
  • [9] Christopher Hooley, On Artin's conjecture, J. Reine Angew. Math. 225 (1967), 209-220. MR 0207630
  • [10] Youness Lamzouri, Xiannan Li, and Kannan Soundararajan, Conditional bounds for the least quadratic non-residue and related problems, Math. Comp. 84 (2015), no. 295, 2391-2412. MR 3356031, https://doi.org/10.1090/S0025-5718-2015-02925-1
  • [11] H. W. Lenstra Jr., Galois theory and primality testing, Orders and their applications (Oberwolfach, 1984) Lecture Notes in Math., vol. 1142, Springer, Berlin, 1985, pp. 169-189. MR 812498, https://doi.org/10.1007/BFb0074800
  • [12] Vsevolod F. Lev, Optimal representations by sumsets and subset sums, J. Number Theory 62 (1997), no. 1, 127-143. MR 1430006, https://doi.org/10.1006/jnth.1997.2012
  • [13] Mariana Levin, Carl Pomerance, and K. Soundararajan, Fixed points for discrete logarithms, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 6-15. MR 2969346, https://doi.org/10.1007/978-3-642-14518-6_5
  • [14] A. A. Mullin, Recursive function theory, Bull. Amer. Math. Soc. 69 (1963), 737.
  • [15] Paul Pollack and Enrique Treviño, The primes that Euclid forgot, Amer. Math. Monthly 121 (2014), no. 5, 433-437. MR 3193727, https://doi.org/10.4169/amer.math.monthly.121.05.433
  • [16] Carl Pomerance, Remarks on the Pólya-Vinogradov inequality, Integers 11 (2011), no. 4, 531-542. MR 2988079, https://doi.org/10.1515/integ.2011.039
  • [17] Kenneth Rogers, The Schnirelmann density of the squarefree integers, Proc. Amer. Math. Soc. 15 (1964), 515-516. MR 0163893
  • [18] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94. MR 0137689
  • [19] Samuel S. Wagstaff Jr., Computing Euclid's primes, Bull. Inst. Combin. Appl. 8 (1993), 23-32. MR 1217356
  • [20] T. D. Wooley, A superpowered Euclidean prime generator, 2016, arXiv:1607.05267, preprint.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 11A41, 11A15, 11B25, 11L40

Retrieve articles in all journals with MSC (2010): 11A41, 11A15, 11B25, 11L40


Additional Information

Andrew R. Booker
Affiliation: School of Mathematics, Bristol University, University Walk, Bristol, BS8 1TW, United Kingdom
Email: andrew.booker@bristol.ac.uk

Carl Pomerance
Affiliation: Mathematics Department, Dartmouth College, Hanover, New Hampshire 03755
Email: carl.pomerance@dartmouth.edu

DOI: https://doi.org/10.1090/proc/13576
Received by editor(s): July 6, 2016
Received by editor(s) in revised form: July 7, 2016, and November 4, 2016
Published electronically: August 31, 2017
Communicated by: Matthew A. Papanikolas
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society