Squarefree smooth numbers and Euclidean prime generators

Booker, Andrew; Pomerance, Carl

doi:10.1090/proc/13576

Squarefree smooth numbers and Euclidean prime generators
HTML articles powered by AMS MathViewer

by Andrew R. Booker and Carl Pomerance

Proc. Amer. Math. Soc. 145 (2017), 5035-5042

DOI: https://doi.org/10.1090/proc/13576

Published electronically: August 31, 2017

PDF | Request permission

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

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, DOI 10.2307/2006975
N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 45159, DOI 10.2307/1969420
Andrew R. Booker, On Mullin’s second sequence of primes, Integers 12 (2012), no. 6, 1167–1177. MR 3011555, DOI 10.1515/integers-2012-0034
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
Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
J. Feitsma, Pseudoprimes, http://www.janfeitsma.nl/math/psp2/index.
D. A. Frolenkov and K. Soundararajan, A generalization of the Pólya-Vinogradov inequality, Ramanujan J. 31 (2013), no. 3, 271–279. MR 3081668, DOI 10.1007/s11139-012-9462-y
Glyn Harman, Integers without large prime factors in short intervals and arithmetic progressions, Acta Arith. 91 (1999), no. 3, 279–289. MR 1735677, DOI 10.4064/aa-91-3-279-289
Christopher Hooley, On Artin’s conjecture, J. Reine Angew. Math. 225 (1967), 209–220. MR 207630, DOI 10.1515/crll.1967.225.209
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, DOI 10.1090/S0025-5718-2015-02925-1
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, DOI 10.1007/BFb0074800
Vsevolod F. Lev, Optimal representations by sumsets and subset sums, J. Number Theory 62 (1997), no. 1, 127–143. MR 1430006, DOI 10.1006/jnth.1997.2012
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, DOI 10.1007/978-3-642-14518-6_{5}
A. A. Mullin, Recursive function theory, Bull. Amer. Math. Soc. 69 (1963), 737.
Paul Pollack and Enrique Treviño, The primes that Euclid forgot, Amer. Math. Monthly 121 (2014), no. 5, 433–437. MR 3193727, DOI 10.4169/amer.math.monthly.121.05.433
Carl Pomerance, Remarks on the Pólya-Vinogradov inequality, Integers 11 (2011), no. 4, 531–542. MR 2988079, DOI 10.1515/integ.2011.039
Kenneth Rogers, The Schnirelmann density of the squarefree integers, Proc. Amer. Math. Soc. 15 (1964), 515–516. MR 163893, DOI 10.1090/S0002-9939-1964-0163893-X
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Samuel S. Wagstaff Jr., Computing Euclid’s primes, Bull. Inst. Combin. Appl. 8 (1993), 23–32. MR 1217356
T. D. Wooley, A superpowered Euclidean prime generator, 2016, arXiv:1607.05267, preprint.