Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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
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)^{\frac12}$ 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^{\frac35}$. The novelty of our approach is the avoidance of any appeal to Siegel's Theorem on primes in arithmetic progression.

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

  • 1. M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, primality.pdf.
  • 2. R. C. Baker, G. Harman, The Brun-Titchmarsh theorem on average, Analytic Number Theory (Proceedings in honor of Heini Halberstam), Birkhauser, Boston, 1996, 39-103. MR 1399332 (97h:11096)
  • 3. R. C. Baker, G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), 331-361. MR 1610553 (99b:11104)
  • 4. D. Bernstein, Proving primality after Agrawal-Kayal-Saxena, html#aks.
  • 5. E. Bombieri, J. B. Friedlander and H. Iwaniec, Primes in arithmetic progressions to large moduli III, J. American Math. Soc. 2 (1989), 215-224. MR 0976723 (89m:11087)
  • 6. H. Davenport, Multiplicative Number Theory (second edition revised by H. L. Montgomery), Springer-Verlag, New York, 1980. MR 0606931 (82m:10001)
  • 7. J.-M. Deshouillers and H. Iwaniec, On the Brun-Titchmarsh theorem on average in Topics in classic number theory (ed. G. Halász), vol. 1 (Budapest, 1981), 319-333. MR 0781145 (86e:11085)
  • 8. K. Ford, Vinogradov's Integral and bounds for the Riemann zeta-function, Proc. London Math. Soc. (3) 85 (2002), 565-633. MR 1936814 (2003j:11089)
  • 9. M. Goldfeld, On the number of primes $p$ for which $p+a$ has a large prime factor, Mathematika 16 (1969), 23-27. MR 0244176 (39:5493)
  • 10. H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119-134. MR 0374060 (51:10260)
  • 11. Y. Motohashi, A note on the least prime in an arithmetic progression with a prime difference, Acta Arith. 17 (1970), 283-285. MR 0268131 (42:3030)
  • 12. N. M. Timofeev, The Vinogradov-Bombieri theorem, (English) Math. Notes 38 (1985), 947-951. MR 0823418 (87f:11073)
  • 13. R. C. Vaughan, An elementary method in prime number theory, Acta Arith. 37 (1980), 111-115. MR 0598869 (82c:10055)

Similar Articles

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

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

American Mathematical Society