On the greatest prime factor of $p-1$ with effective constants
Author:
G. Harman
Journal:
Math. Comp. 74 (2005), 2035-2041
MSC (2000):
Primary 11N13
DOI:
https://doi.org/10.1090/S0025-5718-05-01749-7
Published electronically:
February 16, 2005
MathSciNet review:
2164111
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: Let $p$ denote a prime. In this article we provide the first published lower bounds for the greatest prime factor of $p-1$ exceeding $(p-1)^{\frac 12}$ in which the constants are effectively computable. As a result we prove that it is possible to calculate a value $x_0$ such that for every $x > x_0$ there is a $p < x$ with the greatest prime factor of $p-1$ exceeding $x^{\frac 35}$. The novelty of our approach is the avoidance of any appeal to Siegel’s Theorem on primes in arithmetic progression.
- M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, http://www.cse.iitk.ac.in/primality.pdf.
- R. C. Baker and G. Harman, The Brun-Titchmarsh theorem on average, Analytic number theory, Vol. 1 (Allerton Park, IL, 1995) Progr. Math., vol. 138, Birkhäuser Boston, Boston, MA, 1996, pp. 39–103. MR 1399332
- R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361. MR 1610553, DOI https://doi.org/10.4064/aa-83-4-331-361
- D. Bernstein, Proving primality after Agrawal-Kayal-Saxena, http://cr.yp.to/papers/html#aks.
- E. Bombieri, J. B. Friedlander, and H. Iwaniec, Primes in arithmetic progressions to large moduli. III, J. Amer. Math. Soc. 2 (1989), no. 2, 215–224. MR 976723, DOI https://doi.org/10.1090/S0894-0347-1989-0976723-6
- Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931
- J.-M. Deshouillers and H. Iwaniec, On the Brun-Titchmarsh theorem on average, Topics in classical number theory, Vol. I, II (Budapest, 1981) Colloq. Math. Soc. János Bolyai, vol. 34, North-Holland, Amsterdam, 1984, pp. 319–333. MR 781145
- Kevin Ford, Vinogradov’s integral and bounds for the Riemann zeta function, Proc. London Math. Soc. (3) 85 (2002), no. 3, 565–633. MR 1936814, DOI https://doi.org/10.1112/S0024611502013655
- Morris Goldfeld, On the number of primes $p$ for which $p+a$ has a large prime factor, Mathematika 16 (1969), 23–27. MR 244176, DOI https://doi.org/10.1112/S0025579300004575
- H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134. MR 374060, DOI https://doi.org/10.1112/S0025579300004708
- Yoichi Motohashi, A note on the least prime in an arithmetic progression with a prime difference, Acta Arith. 17 (1970), 283–285. MR 268131, DOI https://doi.org/10.4064/aa-17-3-283-285
- N. M. Timofeev, The Vinogradov-Bombieri theorem, Mat. Zametki 38 (1985), no. 6, 801–809, 956 (Russian). MR 823418
- R. C. Vaughan, An elementary method in prime number theory, Acta Arith. 37 (1980), 111–115. MR 598869, DOI https://doi.org/10.4064/aa-37-1-111-115
Retrieve articles in Mathematics of Computation with MSC (2000): 11N13
Retrieve articles in all journals with MSC (2000): 11N13
Additional Information
G. Harman
Affiliation:
Department of Mathematics, Royal Holloway University of London, Egham, Surrey TW20 0EX, United Kingdom
Email:
G.Harman@rhul.ac.uk
Received by editor(s):
March 19, 2004
Received by editor(s) in revised form:
August 16, 2004
Published electronically:
February 16, 2005
Article copyright:
© Copyright 2005
American Mathematical Society